Программа учебной дисциплины ОПД. Ф.10 Основы дискретной математики (стр. 2 )

Раскраска вершин и ребер графа. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.

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

№ п/п	Наименование модулей, разделов и тем	Всего часов:	В том числе
Лекции	Практич. занятия	Самост. работа
1.	Модуль 1. Множества и отношения	36	4	2	30
	Раздел I. Введение в теорию множеств	11	2	1	8
	Тема 1. Множество. Операции над множествами	11	2	1	8
	Раздел II. Отношения. Отображения	25	2	1	22
	Тема 1. Бинарные отношения	4	0,5	-	3,5
	Тема 2. Отношение эквивалентности и порядка	10	1	0,5	8,5
	Тема 3. . Отображение (функция). Виды отображений	11	0,5	0,5	10
	Модуль 2. Элементы комбинаторики	26	2	2	22
	Тема 1. Общие правила комбинаторики: правило суммы и произведения. Теорема о включениях и исключениях. Размещения и перестановки с повторениями и без повторений	10	1	1	8
	Тема 2. Сочетания. Свойства биномиальных коэффициентов. Бином Ньютона и полиномиальная формула.	10	1	1	8
	Тема 3. Комбинаторика разбиений	6	-	-	6
	Модуль 3. Основы математической логики	44	2	2	40
2.	Раздел I. Алгебра высказываний	20	2	2	16
3.	Тема 1. Высказывания; логические операции над высказываниями; формулы логики высказываний; основные равносильности логики высказываний	12	2	2	8
4.	Тема 2. Конъюнктивные и дизъюнктивные нормальные формы, совершенные к. н.ф. и д. н.ф. для формул логики высказываний	8	-	-	8
5.	Раздел II.  Булевы функции (функции алгебры логики)	24	-	-	24
6.	Тема 1. Понятие булевой функции; равносильные б. ф.; закон двойственности; теорема о разложении функции по аргументам.	8	-	-	8
7.	Тема 2. Нормальные формы булевых функций и алгоритмы приведения б. ф. к нормальным формам.	8	-	-	8
8.	Тема 3. Применение булевых функций к анализу и синтезу релейно-контактных схем	8	-	-	8
9.	Модуль 4. Элементы теории графов	44	4	-	40
10.	Раздел I. Введение в теорию графов. Маршруты, цепи и циклы в графе	30	4	-	26
11.	Тема 1. Определение графа (неориентированного). Смежность и инцидентность. Матричная форма представления графов. Ориентированный граф	8	2	-	6
12.	Тема 2. Маршруты в графе; цепи, циклы. Путь и контур в орграфе.	7	1	-	6
13.	Тема 3. Кратчайший маршрут во взвешенном связном графе; алгоритм Дейкстры.	7	-	-	7
14.	Тема 4. Гамильтоновы и эйлеровы графы; алгоритмы построения эйлерова цикла и эйлеровой цепи.	8	1	-	7
15.	Раздел II. Планарные и плоские графы. Раскраска вершин графа	14	-	-	14
16.	Тема 1. Планарные и плоские графы. Теорема Эйлера о соотношении чисел граней, ребер и вершин плоского графа..	6	-	-	6
17.	Тема 2. Раскраска вершин и ребер графа. Теорема о пяти красках	8	-	-	8
Всего:	150	12	6	132

2.4.  ЛЕКЦИИ

№ п/п	СОДЕРЖАНИЕ ЛЕКЦИЙ
1 курс, установочная сессия
1	Множество. Операции над множествами. Понятие множества. Способы задания множеств. Подмножество. Универсальное множество. Булеан множества. Равенство множеств. Диаграммы Эйлера-Венна. Операции над множествами: объединение, пересечение, разность, декартово произведение. Теоремы об основных свойствах операций.
2	Бинарные отношения. Отображения. Определение бинарного отношения на паре множеств. Область определения, область значений б. о. Способы задания бинарных отношений; граф и график б. о. Отношения на множестве и их свойства. Отношение эквивалентности. Классы эквивалентности и фактор - множество. Понятие разбиения. Связь отношения эквивалентности, заданного на множестве, с разбиением этого множества. Отображение (функция). Виды отображений: инъективное, сюръективное и биективное отображения. Взаимно однозначные отображения и мощности множеств. Счетные множества.
3	Элементы комбинаторики. Общие правила комбинаторики: правило суммы и произведения. Теорема о включениях и исключениях. Размещения с повторениями и без повторений. Перестановки с повторениями и без повторений. Сочетания. Свойства биномиальных коэффициентов. Бином Ньютона и полиномиальная формула
4	Алгебра высказываний. Понятие высказывания; элементарные и составные высказывания; логические операции над высказываниями. Формулы логики высказываний; таблицы истинности. Равносильность формул; основные равносильности алгебры высказываний; тождественно истинные, тождественно ложные и выполнимые формулы. Нормальные формы формул логики высказываний.
5	Основные понятия теории графов. Определение графа (неориентированного). Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Матричная форма представления графов: матрица смежности, матрица инцидентности. Степени вершин.
6	Маршруты в графе. Цепи, циклы. Эйлеровы и гамильтоновы графы.

2.5.  ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

№ п/п	СОДЕРЖАНИЕ ЗАНЯТИЙ
1 курс, установочная сессия
1	Множества. Операции над множествами: объединение, пересечение, разность, декартово произведение. Бинарные отношения на множестве и их свойства. Отношение эквивалентности; разбиение на классы эквивалентности и фактор-множество. Отображение (функция); виды отображений.
2	Общие правила комбинаторики: правило суммы и произведения. Теорема о включениях и исключениях. Размещения с повторениями и без повторений. Перестановки с повторениями и без повторений. Сочетания. Свойства биномиальных коэффициентов. Бином Ньютона и полиномиальная формула.
3	Высказывания. Логические операции над высказываниями и их свойства. Построение таблиц истинности. Законы логики.

2.6.  САМОСТОЯТЕЛЬНАЯ РАБОТА СТУДЕНТОВ

(132 часа):

1.  Проработка материала лекций и практических занятий в рекомендуемой литературе – 60 часов

2.  Выполнение заданий для самостоятельной работы и ответ на вопросы для самоконтроля– 10 часов.

3.  Выполнение индивидуальной домашней контрольной работы – 20 часов.

4.  Подготовка кратких ответов по вопросам программы экзамена – 42 часа.

1.  УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

а) основная литература: