Дискретная математика: Рабочая учебная программа дисциплины

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Уральский государственный педагогический университет» Факультет ____математический___ Кафедра __алгебры и теории чисел УТВЕРЖДАЮ: Проректор по учебной работе УрГПУ ____________________ Т.Н. Шамало «____» _____________________2007 г.

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

по дисциплине ___«Дискретная математика» для направления «540201 – Физико-математическое образование» по циклу___«Дисциплины предметной подготовки» Очная форма обучения

Заочная форма обучения

Курс – 4 Семестр – 8 Объѐм в часах всего – 78 в т. ч.: лекции – 20 практические занятия – 18 лабораторные занятия – 0 самостоятельная работа – 40 Зачет – 8 семестр

Курс – 4 Семестр – 7 Объѐм в часах всего – 78 в т. ч.: лекции – 8 практические занятия – 6 лабораторные занятия – 0 самостоятельная работа – 64 Зачет – 8 семестр

Екатеринбург 2007

Рабочая учебная программа по дисциплине «Дискретная математика» ГОУ ВПО «Уральский государственный педагогический университет» Екатеринбург, 2007, 7 с. Составитель: Ильиных А.П., зав кафедрой алгебры и теории чисел, д.ф.-м.н. Рабочая программа обсуждена на заседании кафедры алгебры и теории чисел УрГПУ Протокол от_7 апреля 2006__ г. № __8__ . Зав. кафедрой А.П. Ильиных Отделом нормативного обеспечения образовательного процесса УрГПУ выдан сертификат № ____ от ________ г. Начальник отдела ______________Р.Ю. Шебалов

2

1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА В настоящее время под дискретной математикой понимают обширный круг разнородных математических дисциплин. Среди круга вопросов, которые изучаются в этих дисциплинах можно отметить следующие основные направления: комбинаторика без повторений и с повторениями, рекуррентные соотношения, комбинаторные конфигурации и конечные геометрии, графы и алгоритмы на графах. В данном курсе рассматриваются указанные основные разделы дискретной математики. По курсу дискретной математики предусматривается проведение двух контрольных работ.

2. УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ 2.1. Учебно-тематический план очной формы обучения

№ п/п

1 2 3 4 5 6 7 8

Аудиторные Всего занятия труПрадоем- Все- Лек- ктикость го ции ческие 16 8 4 4

Наименование раздела, темы Комбинаторика без повторений и с повторениями Рекуррентные соотношения. Суммы и рекуррентности. Введение в асимптотические методы. Основные понятия теории графов. Связные графы. Эйлеровы графы. Деревья. Плоские графы. Раскраска графа. Итого

Лабораторные

Самостоятельная работа 8

8

4

2

2

4

8

4

2

2

4

12 8 8 10 8 78

6 4 4 4 4 38

4 2 2 2 2 20

2 2 2 2 2 18

6 4 4 6 4 40

Учебно-тематический план заочной формы обучения

№ п/п

1 2 3 4

Аудиторные Всего занятия труПрадоем- Все- Лек- ктикость го ции ческие 16 2 2

Наименование раздела, темы Комбинаторика без повторений и с повторениями. Рекуррентные соотношения. Суммы и рекуррентности. Введение в асимптотические методы. Основные понятия теории графов. 3

8

2

8

2

12

2

2 2

Лабораторные

Самостоятельная работа 14 6 6

2

10

5 6 7 8

Связные графы. Эйлеровы графы. Деревья. Плоские графы. Раскраска графа. Итого

8 8 10 8 78

2 2 2

2

14

8

2 2 6

6 6 8 8 64

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 1. Комбинаторика без повторений и с повторениями. Размещения, сочетания, перестановки без повторений. Размещения, сочетания, перестановки с повторениями. 2. Рекуррентные соотношения. Суммы и рекуррентности. Рекуррентные соотношения. Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Целочисленные функции. 3. Введение в асимптотические методы. Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. 4. Основные понятия теории графов. Псевдограф, мультиграф, граф и их ориентированные аналоги. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл. 5. Связные графы. Компоненты связности графа, их число. Число различных графов с p вершинами. Изоморфные графы. 6. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы. 7. Деревья. Плоские графы. Деревья. Характеризационная теорема. Укладка графа. Планарные графы. Плоские графы. Теорема Эйлера и ее следствия. Непланарность графов K5 и K3,3. 8. Раскраска графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.

4. САМОСТОЯТЕЛЬНАЯ РАБОТА И ОРГАНИЗАЦИЯ КОНТРОЛЬНО-ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ Темы, вынесенные на самостоятельное обучение: Раскрашиваемость вершин планарного графа пятью красками. Вопросы для зачета: 1. Рекуррентные соотношения. Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи. 2. Способы решения рекуррентных соотношений. 3. Суммы и рекуррентности. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. 4. Целочисленные функции. 4

5. Введение в асимптотические методы. Символы ~, о, О. Основные правила использования этих символов. 6. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. 7. Основные понятия теории графов: псевдограф, мультиграф, граф и их ориентированные аналоги. 8. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. 9. Подграф. Путь, цепь, простая цепь, цикл, простой цикл. 10. Связные графы. Компоненты связности графа, их число. Число различных графов с p вершинами. 11. Изоморфные графы. 12. Двудольные графы. 13. Эйлеровы графы.Критерий эйлеровости 14. Гамильтоновы графы. 15. Деревья. Характеризационная теорема. 16. Укладка графа. Планарные графы. Плоские графы. 17. Теорема Эйлера и ее следствия. Непланарность графов K5 и K3,3. 18. Раскраска вершин и ребер графа. Теорема Кенига. 19. Раскрашиваемость вершин планарного графа пятью красками. 20. Гипотеза четырех красок.

5. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ Студент, изучивший дисциплину, должен знать: основные определения и теоремы из комбинаторики и теории графов; иметь представление о методах дискретной математики; знать о новейших достижениях в дискретной математике.

Студент, изучивший дисциплину, должен уметь: преобразовывать и вычислять конечные суммы, составлять простейшие рекуррентные соотношения, решать типовые комбинаторные задачи, уверенно решать задачи на

размещения, сочетания, перестановки.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ 6.1. Рекомендуемая литература Основная 1. Андерсон Д.А. Дискретная математика и комбинаторика [Текст] / Д.А. Андерсон; пер. с англ. М.М. Беловой; под ред. С.С. Шкильняка и М.Р. Саит-Аметова. – М.: Изд. дом. «Вильямс», 2003. – 960 с. 2. Виленкин Н.Я. Индукция. Комбинаторика [Текст]: пособие для учителей / Н.Я. Виленкин. – М.: Просвещение, 1976. – 48 с. 3. Виленкин Н.Я. Комбинаторика [Текст] / Н.Я. Виленкин. - М.: Физматгиз, 1969. – 328 с. 4. Гаврилов Г.П. Задачи и упражнения по курсу дискретной математики [Текст]: учеб. пособ. для вузов по спец. «Прикладная математика» / Г.П. Гаврилов, А.А. Сапоженко. - М.: Наука, 1977. – 368 с 5

5. Гончарова Г.А. Элементы дискретной математики [Текст]: учеб. пособ. для студентов учреждений сред. проф. образования по спец. информатики и вычислит. техники / Г.А. Гончарова. – М.: ФОРУМ:ИНФРА, 2004. – 128 с. 6. Емеличев В.А. Лекции по теории графов [Текст] / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - М.: Наука, 1990. – 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 с.

6.2. Информационное обеспечение дисциплины Локальная сеть математического факультета УрГПУ, сайт кафедры алгебры и теории чисел, «Информационная обучающая среда».

7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ И ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ Компьютерные классы математического факультета.

8. СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ Ильиных Анатолий Петрович, д.ф.м.н., зав каф. алгебры и теории чисел УрГПУ. Рабочий телефон:

371-12-61

6

РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА

по дисциплине ___« Дискретная математика » для направления «540201 – Физико-математическое образование» по циклу______«Дисциплины предметной подготовки»

Подписано в печать

Формат 60х84/16

Бумага для множительных аппаратов. Усл. печ. л. Тираж

экз.

Заказ

Уральский государственный педагогический университет. 620017 Екатеринбург, пр. Космонавтов, 26.

7