Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Уральский государственный педагогический университет»
Факультет математический
Кафедра алгебры и теории чисел
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
по дисциплине
«Дискретная математика»
для специальности «050202.65 – Информатика»
по циклу ДПП. Ф.12 – Дисциплины предметной подготовки
(федеральный компонент)
Очная форма обучения Заочная форма обучения
Курс - 4 Курс - 4
Семестр – 8 Семестр – 7
Объем в часах всего – 78 Объем в часах всего – 78
в т. ч.: лекции – 20 в т. ч.: лекции – 8
практические занятия – 18 практические занятия – 4
самостоятельная работа – 40 самостоятельная работа - 66
Зачет – 8 семестр Зачет – 8 семестр
Контрольная работа – 7 семестр
Екатеринбург 2012
Рабочая учебная программа по дисциплине
«Дискретная математика»
ФГБОУ ВПО «Уральский государственный педагогический университет»
Екатеринбург, 2012. – 7 с.
Составитель:
, доцент кафедры алгебры и теории чисел, к. ф.-м. н., доцент, математический факультет УрГПУ
Рабочая учебная программа обсуждена на заседании кафедры алгебры и теории чисел УрГПУ
Протокол № 9 от 01.01.2001.
Зав. кафедрой
Согласовано с методической комиссией математического факультета
Председатель методической комиссии
Декан математического факультета
1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
В настоящее время под дискретной математикой понимают обширный круг разнородных математических дисциплин. Среди круга вопросов, которые изучаются в этих дисциплинах можно отметить следующие основные направления: комбинаторика без повторений и с повторениями, рекуррентные соотношения, комбинаторные конфигурации и конечные геометрии, графы и алгоритмы на графах. В данном курсе рассматриваются указанные основные разделы дискретной математики. По курсу дискретной математики предусматривается проведение двух контрольных работ.
2. УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ
2.1 . Учебно-тематический план очной формы обучения
№ п/п | Наименование раздела, темы | Всего трудоемкость | Аудиторные занятия | Самостоятельная работа | ||
Всего | Лекции | Практические | ||||
1. | Комбинаторика без повторений и с повторениями | 16 | 8 | 4 | 4 | 8 |
2. | Рекуррентные соотношения. Суммы и рекуррентности | 8 | 4 | 2 | 2 | 4 |
3. | Введение в асимптотические методы | 8 | 4 | 2 | 2 | 4 |
4. | Основные понятия теории графов | 12 | 6 | 4 | 2 | 6 |
5. | Связные графы | 8 | 4 | 2 | 2 | 4 |
6. | Эйлеровы графы. | 8 | 4 | 2 | 2 | 4 |
7. | Деревья. Плоские графы | 10 | 4 | 2 | 2 | 6 |
8. | Раскраска графа | 8 | 4 | 2 | 2 | 4 |
Итого: | 78 | 38 | 20 | 18 | 40 |
2.2 Учебно-тематический план заочной формы обучения
№ п/п | Наименование раздела, темы | Всего трудоемкость | Аудиторные занятия | Самостоятельная работа | ||
Всего | Лекции | Практические | ||||
1. | Комбинаторика без повторений и с повторениями | 14 | 2 | 1 | 1 | 12 |
2. | Рекуррентные соотношения. Суммы и рекуррентности | 8 | 2 | 1 | 1 | 6 |
3. | Введение в асимптотические методы | 8 | 2 | 1 | 1 | 6 |
4. | Основные понятия теории графов | 10 | 2 | 1 | 1 | 8 |
5. | Связные графы | 7 | 1 | 1 | 6 | |
6. | Эйлеровы графы | 7 | 1 | 1 | 6 | |
7. | Деревья. Плоские графы | 9 | 1 | 1 | 8 | |
8. | Раскраска графа | 15 | 1 | 1 | 14 | |
Итого: | 78 | 12 | 8 | 4 | 66 |
3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
1. Комбинаторика без повторений и с повторениями
Размещения, сочетания, перестановки без повторений. Размещения, сочетания, перестановки с повторениями.
2. Рекуррентные соотношения. Суммы и рекуррентности
Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи. Способы решения рекуррентных соотношений.
Суммы и рекуррентности.
Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Целочисленные функции.
3. Введение в асимптотические методы
Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера.
4. Основные понятия теории графов
Псевдограф, мультиграф, граф и их ориентированные аналоги. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл.
5. Связные графы
Компоненты связности графа, их число. Число различных графов с вершинами. Изоморфные графы.
6. Эйлеровы графы
Критерий эйлеровости. Гамильтоновы графы.
7. Деревья. Плоские графы.
Характеризационная теорема. Укладка графа. Планарные графы. Плоские графы. Теорема Эйлера и ее следствия. Непланарность графов K5 и K3,3.
8. Раскраска графа
Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.
4. САМОСТОЯТЕЛЬНАЯ РАБОТА И ОРГАНИЗАЦИЯ
КОНТРОЛЬНО-ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ
4.1 . Темы, вынесенные на самостоятельное изучение
Раскрашиваемость вершин планарного графа пятью красками.
4.2. Вопросы для экзамена
1. Рекуррентные соотношения. Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи.
2. Способы решения рекуррентных соотношений.
3. Суммы и рекуррентности. Преобразования сумм. Кратные суммы. Некоторые методы суммирования.
4. Целочисленные функции.
5. Введение в асимптотические методы. Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера.
6. Основные понятия теории графов: псевдограф, мультиграф, граф и их ориентированные аналоги.
7. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл.
8. Связные графы. Компоненты связности графа, их число. Число различных графов с p вершинами. Изоморфные графы.
9. Двудольные графы.
10. Эйлеровы графы. Критерий эйлеровости.
11. Гамильтоновы графы.
12. Деревья. Характеризационная теорема.
13. Укладка графа. Планарные графы. Плоские графы. Теорема Эйлера и ее следствия. Непланарность графов K5 и K3,3.
14. Раскраска вершин и ребер графа. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.
5. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ
Студент, изучивший дисциплину, должен знать:
– основные определения и теоремы из комбинаторики и теории графов;
– методы дискретной математики;
– новейшие достижениях в дискретной математике.
Студенты, изучивший дисциплину, должен уметь:
–преобразовывать и вычислять конечные суммы;
– составлять простейшие рекуррентные соотношения;
– решать типовые комбинаторные задачи;
– решать задачи на размещения, сочетания, перестановки.
6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
6.1.Рекомендуемая литература
Основная
1. Андерсон, математика и комбинаторика [Текст] / ; пер. с англ. ; под ред. и -Аметова. – М.: Изд. дом. «Вильямс», 2003. – 960 с.
2. Виленкин, . Комбинаторика [Текст]: пособие для учителей / . – М.: Просвещение, 1976. – 48 с.
3. Виленкин, [Текст] / . - М.: Физматгиз, 1969. – 328 с.
4. Гаврилов, и упражнения по курсу дискретной математики [Текст]: учеб. пособ. для вузов по спец. «Прикладная математика» / , . - М.: Наука, 1977. – 368 с
5. Гончарова, дискретной математики [Текст]: учеб. пособ. для студентов учреждений сред. проф. образования по спец. информатики и вычислит. техники / . – М.: ФОРУМ:ИНФРА, 2004. – 128 с.
6. Емеличев, по теории графов [Текст] / , , . - М.: Наука, 1990. – 268 с.
7. Матросов, по дискретной математике [Текст]: учеб. пособие для магистрантов мат. фак. пед. ун-тов / , . – М.: Прометей, 1997. – 220 с.
8. Введение в теорию графов [Текст] / Р. Уилсон; пер. с англ. ; под ред. . – М.:Мир, 1977. – 208 с.
Дополнительная
1. Горбатов, дискретной математики [Текст]: учеб. пособие для вузов / . – М.: Высш. шк., 1986. – 312 с.
2. Ежов, комбинаторики [Текст] / , , . – М.: Наука, 1977. – 80 с.
3. Замятин, и сети [Текст]: учеб. пособие / ; Урал. гос. ун-т. – Екатеринбург: Изд-во Урал. ун-та, 2004. – 160 с.
4. Кузьмин, комбинаторика [Текст]: учеб. пособ. для студентов вузов / . – М.: Дрофа, 2005. – 110 с.
5. Москинова, математика [Текст] / . – М.: Логос, 2004. – 240 с.
6. Яблонский, в дискретную математику [Текст]: уч. пособие для вузов / ; под ред. . – 3-е изд. – М.: Высш. шк., 2001. – 384 с.
7. СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ
Составитель:
,
к. ф.-м. н.,
доцент каф. алгебры и теории чисел УрГПУ
Рабочий телефон: (3
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
по дисциплине «Дискретная математика»
для специальности «050202.65 – Информатика»
по циклу ДПП. Ф.12 – Дисциплины предметной подготовки
(федеральный компонент)
Подписано в печать Формат 60х84/16
Бумага для множительных аппаратов. Усл. печ. л. 0,5
Тираж экз. Заказ.
Уральский государственный педагогический университет.
620017 Екатеринбург, пр. Космонавтов, 26
