1.6 Содержание дисциплины.

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

№ п/п	Наименование раздела, темы	Количество часов
		для специальности 010200 «Прикладная математика и информатика»
		Всего ауд.	ЛК	ПР	ЛБ	Сам.раб.
1	Элементы теории множеств	8	4	4	–	10
2	Конечные графы	32	16	16	–	10
3	Функциональные системы с операциями: алгебра логики	34	16	18	–	20
	ИТОГО	74	36	38	–	40

1.6.2 Содержание разделов дисциплины.

Элементы теории множеств

§ 1. Множества и их элементы. Операции над множествами.

§ 2. Вектор и его компоненты. Прямое произведение. Бинарные отношения и их свойства.

Конечные графы

§ 1. Основные понятия теории графов.

Ориентированные и неориентированные графы, их вершины, рёбра и дуги. Мультиграфы. Псевдографы. Изоморфные графы. Нулевой граф. Полный граф. Часть графа. Подграф. Собственный подграф. Число помеченных графов на n вершинах.

§ 2. Операции над графами.

Дополнение. Объединение графов. Произведение графов. Композиция графов.

§ 3. Способы задания псевдографов.

Матрица смежности. Матрица инцидентности. Список ребер. Списки смежности.

§ 4. Степени вершин.

Степени вершин псевдографа. Лемма о рукопожатиях. Однородный (регулярный) граф.

§ 5. Отношение связности для вершин неориентированного графа.

Маршрут, цепь и цикл. Отношение связности и его свойства. Компоненты связности. Связный граф. Точка сочленения. Мост.

§ 6. Отношение достижимости для вершин орграфа.

Путь, ориентированная цепь и ориентированный цикл. Отношение достижимости и его свойства. Базисный граф. Алгоритм построения базисного графа.

§ 7. Эйлеров псевдограф.

Эйлеров цикл и условия его существования. Эйлерова цепь и условия ее существования.

§ 8. Гамильтонов граф.

Гамильтонов цикл и простейшие условия его существования.

§ 9. Деревья.

Деревья и их свойства. Формула Кэли. Задача о минимальном соединении. Остовное дерево. Построение минимального остовного дерева.

§ 10. Двудольный граф.

Определение двудольного графа. Условия, при которых граф двудольный.

§ 11. Планарность.

Укладка графа. Плоский граф. Планарный граф. Теорема Эйлера о связи между количеством вершин, ребер и граней плоского графа. Следствия из теоремы Эйлера: относительно количества ребер планарного графа; относительно графов K₅ и K_3,3; относительно степени вершины планарного графа. Теорема Понтрягина-Куратовского.

§ 12. Раскраска графа.

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

Функциональные системы с операциями: алгебра логики

§ 1. Основные определения.

Элементарные булевы функции. Формулы. Эквивалентность формул. Таблицы значений.

§ 2. Свойства элементарных функций.

§ 3. Совершенные дизъюнктивная и конъюнктивная нормальные формы.

§ 4. Полнота.

Полная система функций. Примеры полных систем. Полином Жегалкина.

§ 5. Замыкание. Важнейшие замкнутые классы.

Класс функций, сохраняющих константу 0, класс функций, сохраняющих константу 1, класс самодвойственных функций, класс монотонных функций, класс линейных функций.

§ 6. Теорема о функциональной полноте.

§ 7. Постановка задачи о минимизации булевых функций Метод минимизирующих карт.

1.6.3 Темы для самостоятельного изучения.

№ п/п	Наименование раздела дисциплины. Тема.	Форма самостоятельной работы	Форма контроля выполнения самостоятельной работы	Количество часов
1	Элементы теории множеств	Контрольная работа № 1	Проверка контрольной работы	10
2	Конечные графы	Контрольная работа № 1	Проверка контрольной работы, тестирование	10
3	Функциональные системы с операциями: алгебра логики	Контрольная работа № 2	Проверка контрольной работы	20