Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Уральский государственный педагогический университет»
Математический факультет
Кафедра алгебры и теории чисел
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
по дисциплине
«Дискретная математика»
для специальности «050201.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. | Андерсон математика и комбинаторика. Пер. с англ. ; под ред. и -Аметова. – М.: Изд. дом. «Вильямс», 2004. – 960 с. | 5 экз. |
2. | Гончарова дискретной математики: учеб. пособ. для студентов учреждений сред. проф. образования по спец. информатики и вычислит. техники. – М.: ФОРУМ: ИНФРА, 2004. – 128 с. | 10 экз. |
3. | Мурзинова математика: учеб. пособие [для студентов пед. вузов]. Урал. гос. пед. ун-т. - Екатеринбург: 2008. – 85 с. | 91 экз. |
4. | Дискретная математика: курс лекций для студентов-механиков: учеб. пособие для студентов вузов по спец. "Математика", "Приклад. математика". - СПб.: Лань, 2006. – 96 с. | 49 экз. |
5. | Балюкевич, математика [Электронный ресурс] : учеб.–практ. пособие / , , . – М. : Евразийский открытый ин–т, 2012. – 173 с. Режим доступа: http://www. *****/book/93277/ | |
6. | Гаврилов, и упражнения по дискретной математике [Электронный ресурс] : сб. задач и упражнений / , . – М. : Физматлит, 2005. – 211 с. Режим доступа: http://www. *****/book/68128/ | |
7. | Иванов, математика. Алгоритмы и программы. Полный курс [Электронный ресурс] : учеб. пособие / . – М. : Физматлит, 2007. – 407 с. Режим доступа: http://www. *****/book/75502/ | |
8. | Ковалева, математика в задачах [Электронный ресурс] : учеб. пособие / . – М. : Евразийский открытый ин–т, 2011. – 142 с. Режим доступа: http://www. *****/book/93273/ |
Дополнительная
1. | , , Виленкин . - М. : ФИМА, МЦНМО, 20с. | 2 экз. |
2. | Москинова, математика. – М.: Логос, 2004. – 240 с. | 9 экз. |
3. | Плотников математика: учеб. пособие для студентов вузов. - М. : Новое знание, 20с. | 10 экз. |
4. | Макоха, математика [Электронный ресурс] / , , . – М : Физматлит,2005.– 184с. Режим доступа: http://www. *****/book/68366/ | |
5. | Редькин, математика [Электронный ресурс] : учеб. / . – М. : Физматлит, 2009. – 134 с. Режим доступа: http://www. *****/book/75709/ | |
6. | Сачков, в комбинаторные методы дискретной математики [Электронный ресурс] / . – Изд. 2–е, испр. и доп. – М. : МЦНМО, 2004. – 424 с. Режим доступа: http://www. *****/book/61989/ | |
7. | Тюрин, математика : практическая дискретная математика и математическая логика [Электронный ресурс] / , . – М. : Финансы и статистика, 2010. – 385 с. Режим доступа: http://www. *****/book/63603/ | |
8. | Хаггарти, Р. Дискретная математика для программистов [Электронный ресурс] : учеб. пособие / Р. Хаггарти. – Изд. 2–е, испр. – М. : РИЦ «Техносфера», 2012. – 400 с. – (Мир программирования). Режим доступа: http://www. *****/book/89024/ |
7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ И ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Карточки-задания для организации и контроля самостоятельной работы
8. СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ
Составитель:
,
к. ф.-м. н.,
доцент каф. алгебры и теории чисел УрГПУ
Рабочий телефон: (3
