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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное

образовательное учреждение высшего образования

«Уральский государственный педагогический университет»

Институт математики, информатики и информационных технологий

Кафедра высшей математики

РАБОЧАЯ ПРОГРАММА

по дисциплине «Дискретная математика»

для ОПОП 44.03.05 «Педагогическое образование»

(с двумя профилями подготовки)

ИНФОРМАТИКА И МАТЕМАТИКА

Уровень бакалавриата

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

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

Составитель: , доцент, к. ф.-м. н., доцент, кафедра высшей математики Института математики, информатики и информационных технологий УрГПУ

(подпись)

Рабочая программа дисциплины обсуждена на заседании кафедры высшей
математики УрГПУ

Протокол от 10.03.16 г.  № 6.

Зав. кафедрой 
                                                               (подпись)

Руководитель учебного подразделения                                
                                                               (подпись)

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Наименование дисциплины: «Дискретная математика». Цели и задачи дисциплины.

Цели изучения  дисциплины заключаются в формировании и развитии у студентов общепрофессиональных и профессиональных компетенций, регламентируемых ФГОС ВО, в частности, выпускник, освоивший программу бакалавриата, должен обладать

– способность использовать естественнонаучные и математические знания для ориентирования в современном информационном пространстве  (ОК-3);

– готовностью реализовывать образовательные программы по учебному предмету в соответствии с требованиями образовательных стандартов (ПК-1).

Задачи изучения дисциплины:

научить студентов применять комбинаторные правила и конструкции; познакомить студентов с важными понятиями теории графов, имеющими прикладной характер; познакомить студентов с производящими функциями и их свойствами.

Место дисциплины в структуре ОПОП.

Дисциплина «Дискретная математика» относится обязательным дисциплинам вариативной части ОПОП Педагогическое образование (с двумя профилями подготовки) «Информатика и математика». Она непосредственно связана с дисциплинами «Алгебра»,  «Геометрия», «Математический анализ», и опирается на освоенные при изучении данных дисциплин знания и умения.

Перечень планируемых результатов обучения по дисциплине (модулю), соотнесенных с планируемыми результатами освоениями образовательной программы:

Основные требования к результатам освоения дисциплины представлены в  таблице № 1  в виде признаков сформированности компетенций. Требования формулируются  в соответствии со структурой, принятой в ФГОС ВО: знать, уметь, владеть.

Знать: основные понятия  комбинаторики, теории графов и производящих функций;

Уметь: применять  основные понятия и факты комбинаторики, теории графов и производящих функций;

Владеть: основными понятиями и фактами комбинаторики, теории графов и производящих функций.

Объем дисциплины (модуля) в зачетных единицах.

Распределение по семестрам	Часов
экзамены	зачеты	трудоемкость в ЗЕ	трудоемкость в часах	аудиторных	самост. работа
контактых	лекций	практик	Лабор. работы
7		2	72	32	16	16	-	40

Особенности реализации дисциплины (модуля).

Дисциплина «Дискретная математика» реализуется на русском языке.

УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ

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

IV семестр

№ п/п	Наименование раздела, темы	Всего тру- доем- кость	Аудиторные занятия	Самостоя- тель- ная работа
Все- го	Лек- ции	Пра- кти- чес- кие	Ла- бора- тор- ные
1	Комбинаторика.	8	4	2	2	4
2	Основные понятия теории графов.	8	4	2	2	4
3	Связные графы.	8	4	2	2	4
4	Эйлеровы  графы.	8	4	2	2	4
5	Гамильтоновы графы.	5	1	1		4
6	Деревья.	8	4	2	2	4
7	Планарные графы.	7	3	1	2	4
8	Раскраски графов.	7	3	1	2	4
9	Орграфы и турниры	7	3	1	2	4
10	Рекуррентные отношения и производящие функции.	6	2	2		4
Итого	72	32	16	16	40

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Структурированное содержание дисциплины

№ п/п	Наименование раздела (темы)	Содержание раздела
1	Комбинаторика.	Конечные множества. Комбинаторные правила: правила сложения и умножения. Комбинаторика без повторений: перестановки, размещения, сочетания. Биномиальные коэффициенты и их свойства. Комбинаторика с повторениями: размещения, перестановки, сочетания. Обобщенная формула Ньютона.
2	Основные понятия теории графов.	Определения графа, мультиграф, ориентированные графы. Степень вершины графа. Теорема о сумме степеней вершин графа. Некоторые важные виды графов. Изоморфизм графов. Операции над графами. Способы задания графов. Матрица смежности и матрица инциденций.
3	Связные графы.	Пути, цепи, циклы в графе. Связные графы. Компонента связности. Мосты и точки сочленения в графе. Теорема о соотношении между числом ребер, числом вершин и числом компонент связности.
4	Эйлеровы  графы.	Эйлеровы и полуэйлеровы графы. Критерий эйлеровости и полуэлеровости графа. Алгоритм Флёри построения эйлеровой цепи в эйлеровом графе.
5	Гамильтоновы графы.	Гамильтоновы и полугамильтоновы графы. Теорема Дирака.
6	Деревья.	Дерево и лес. Характеризационная теорема. Стандартное изображение дерева. Корень дерева. Перечисление деревьев.
7	Планарные графы.	Плоские и планарные графы. Теорема Эйлера о многогранниках. Теорема о непланарности графов K5 и К3,3. Гомеоморфные графы. Теорема Куратовского. Элементарное стягивание графа.
8	Раскраски графов.	Хроматическое число графа. Теоремы о раскрасках планарных графов. Гипотеза четырех красок.
9	Орграфы и турниры.	Ориентированный граф. Эйлеровы орграфы и турниры.
10	Рекуррентные отношения и производящие функции.	Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи. Числа Каталана. Однородные линейные рекуррентные соотношения. Производящие функции и рекуррентные соотношения.

Перечень тем лекционных занятий

Лекция № 1.  Комбинаторные правила. Комбинаторика без повторений: перестановки, размещения, сочетания.

Лекция № 2.  Комбинаторика с повторениями: перестановки, размещения, сочетания.

Лекция № 3. Определения графов. Некоторые важные виды графов.  Способы задания графов. Матрица смежности и матрица инциденций.

Лекция №  4. Пути, цепи, циклы в графе. Связные графы. Компонента связности. Мосты и точки сочленения в графе.

Лекция № 5. Эйлеровы  графы. Критерий эйлеровости  графа.

Лекция № 6. Дерево и лес. Характеризационная теорема.

Лекция № 7. Плоские и планарные графы.  Теорема о непланарности графов K5 и К3,3. 

Лекция № 8. Хроматическое число графа. Теоремы о раскрасках планарных графов. 

Перечень тем практических занятий

Занятие № 1.  Комбинаторные правила. Комбинаторика без повторений: перестановки, размещения, сочетания.

Занятие № 2.  Биномиальные коэффициенты и их свойства.

Занятие № 3.  Комбинаторика с повторениями: перестановки, размещения, сочетания.

Занятие № 4.  Операции над графами. Способы задания графов. Матрица смежности и матрица инциденций.

Занятие № 5. Пути, цепи, циклы в графе. Связные графы. Компонента связности. Мосты и точки сочленения в графе.

Занятие № 6.  Эйлеровы  графы. Критерий эйлеровости. 

Занятие № 7.  Гамильтоновы  графы.

Занятие № 8.  Дерево и лес. Характеризационная теорема.

Вопросы для контроля и самоконтроля

Комбинаторные правила. Комбинаторика без повторений: перестановки, размещения, сочетания. Биномиальные коэффициенты и их свойства. Комбинаторика с повторениями: перестановки, размещения, сочетания. Определения графов. Некоторые важные виды графов. Изоморфизм графов. Операции над графами. Способы задания графов. Матрица смежности и матрица инциденций. Пути, цепи, циклы в графе. Связные графы. Компонента связности. Мосты и точки сочленения в графе.

14.        Эйлеровы и полуэйлеровы графы.

15.  Критерий эйлеровости и полуэлеровости графа.

16.  Алгоритм Флёри построения эйлеровой цепи в эйлеровом графе.

  Гамильтоновы и полугамильтоновы графы.

17.  Дерево и лес. Характеризационная теорема.

18.  Стандартное изображение дерева. Корень дерева.

19.  Плоские и планарные графы.

20.  Теорема о непланарности графов K5 и К3,3.

21.  Хроматическое число графа.

22.  Теоремы о раскрасках планарных графов. 

23.  Теоремы о раскрасках планарных графов. Гипотеза четырех красок.

24.  Задачи, приводящие к рекуррентным соотношениям.

25.  Числа Фибоначчи.

3.5. Перечень тем занятий, реализуемых в активной и интерактивной формах

Занятие № 3.  Комбинаторика с повторениями.

Занятие № 4.  Операции над графами.

Занятие № 5. Пути, цепи, циклы в графе. Связные графы. Компонента связности. Мосты и точки сочленения в графе.

Занятие № 8.  Дерево и лес. Характеризационная теорема.

ПЕРЕЧЕНЬ УЧЕБНО-МЕТОДИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ)
Темы, вынесенные на самостоятельное изучение для студентов очной и заочной форм обучения Ориентированный граф.  Эйлеровы орграфы и турниры.
Вопросы для подготовки к теоретической части экзамена
Комбинаторные правила. Комбинаторика без повторений: перестановки, размещения, сочетания. Биномиальные коэффициенты и их свойства. Комбинаторика с повторениями: перестановки, размещения, сочетания. Определения графов. Некоторые важные виды графов. Изоморфизм графов. Операции над графами. Способы задания графов. Матрица смежности и матрица инциденций. Пути, цепи, циклы в графе. Связные графы. Компонента связности. Мосты и точки сочленения в графе. Теорема о соотношении между числом ребер, числом вершин и числом компонент связности. Эйлеровы и полуэйлеровы графы. Критерий эйлеровости и полуэлеровости графа. Гамильтоновы и полугамильтоновы графы. Дерево и лес. Характеризационная теорема. Плоские и планарные графы. Теорема Эйлера о многогранниках. Теорема о непланарности графов K5 и К3,3. Гомеоморфные графы. Теорема Куратовского.  Хроматическое число графа. Теоремы о раскрасках планарных графов.  Теоремы о раскрасках планарных графов. Гипотеза четырех красок. Ориентированный граф.  Эйлеровы орграфы и турниры. ФОНД ОЦЕНОЧНЫХ СРЕДСТВ ДЛЯ ПРОВЕДЕНИЯ ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ПО ДИСЦИПЛИНЕ (МОДУЛЮ)

Смотри Приложение 1.

УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

6.1. Рекомендуемая литература
Основная

1.        Андерсон Джеймс, А. Дискретная математика и комбинаторика [Текст] / ндерсон; пер. с англ. . — М. : Вильямс, 2004. — 960 с. — ISBN 5-8459-0498-6 : [5 экз.]

2.        Ковалева, математика в задачах. Учебное пособие [Электронный ресурс] / — Москва : Евразийский открытый институт, 2011. — 142 с. — ISBN 978-5-374-00514-1. — <URL: .">http://biblioclub. ru/index. php? page=book&id=93273>.

3.        Усов, математика. Учебно-методическое пособие [Электронный ресурс] / — Омск : Омский государственный университет, 2011. — 60 с. — ISBN 978-5-7779-1339-5. — <URL: .">http://biblioclub. ru/index. php? page=book&id=238214>.

4.        Мурзинова, Галина Сергеевна. Дискретная математика [Текст] : учеб. пособие [для студентов пед. вузов] / ; Урал. гос. пед. ун-т. — Екатеринбург : [б. и.], 2008. — 85 с. : ил. — Библиогр. : с. 103. —  (92 экз.).

Дополнительная

Иванов, Борис Николаевич. Дискретная математика. Алгоритмы и программы : Учеб. пособие / . — М. : Лаборатория Базовых Знаний, 2001. — 288с. : ил. — (Технический университет). — ISBN 5-93208-093-0 : (2 экз.). Ерусалимский, математика. Теория, задачи, приложения. Учебное пособие [Электронный ресурс] / — Москва : Вузовская книга, 2009. — 288 с. — ISBN 978-5-9502-0423-4. — "><URL: http://biblioclub. ru/index. php? page=book&id=129626>.  Балюкевич, математика. Учебно-практическое пособие [Электронный ресурс] / ; ; — Москва : Евразийский открытый институт, 2012. — 173 с. — ISBN 978-5-374-00334-5. — <URL: . ">http://biblioclub. ru/index. php? page=book&id=93277>.

6.2 Информационное обеспечение дисциплины

Цифровые образовательные ресурсы сети Интернет (в частности, сайты www. exponenta. ru; www. school-collection. edu. ru), сайт электронной библиотеки УрГПУ (http://e-lib. uspu. ru)

6.3. Печатные и (или) электронные ресурсы для лиц с ОВЗ

       В УрГПУ функционирует Центр психолого-педагогического информационного обеспечения образования для обучающихся из числа лиц с ограниченными возможностями здоровья. В Центре обучающимся предоставляются печатные и электронные образовательные ресурсы в формах, адаптированных к ограничениям их здоровья.

МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ И ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

При изучении дисциплины  рекомендуется использовать технические средства обучения (персональные компьютеры, медиа проектор).

СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ

Фамилия Имя Отчество
ученая степень	к. ф.-м. н.
ученое звание	доцент
должность и место работы	доцент, каф. высшей математики
рабочий телефон	[phone]