Дискретная математика

Бакалавриат (Системы автоматизированного проектирования)

Преподаватели:

• Лекции: Божко Аркадий Николаевич, д.т.н.
• Семинары: Рабкин Дмитрий Леонидович

Описание

Цель изучения дисциплины ˗ научить студентов использовать средства и методы теории дискретной математики (теории графов, формальных языков и автоматов, булевых функций) для обработки технических данных в соответствии с поставленной задачей, проанализировать результаты расчетов и обосновать полученные выводы, развить способность применять системный подход и математические методы в формализации решения прикладных задач.

Общий объем дисциплины составляет 4 зачетные единицы (з.е.), 144 академических часа.

План занятий

Модуль 1. Основы теории графов.

• Лекция 1. Основные понятия и определения. Виды графов. Изоморфизм графов. Алгебраическое представление графов. Матрицы смежности и инцидентности. Список ребер и список смежности.
• Лекция 2. Маршруты, пути цепи, циклы. Деревья и леса. Связность, связные компоненты, n-связность, мосты. Разрезы.
• Лекция 3. Метрические характеристики графов и вершин. Взвешенные графы. Метрики на графах. Расстояния. Эксцентриситет вершины, радиус, диаметр и центр графа.
• Лекция 4. Обходы графов. Эйлеровы графы. Псевдоэйлеровы графы. Гамильтоновы графы. Псевдогамильтоновы графы. Задача коммивояжера. Эвристические методы решения задачи коммивояжера.
• Лекция 5. Двудольные графы. Трансверсали. Покрытия графов. Независимые множества и клики.
• Лекция 6 Планарные и плоские графы. Теорема Эйлера. Гомеоморфизм графов. Критерий Понтрягина-Куратовского. Двойственные графы.
• Лекция 7. Деревья и леса. Фундаментальная система циклов. Остов графа. Минимальное остовное дерево. Кодирование деревьев методом Прюфера.
• Лекция 8. Ориентированные графы Маршруты, пути и контуры. Виды связности. Бикомпоненты. Конденсация. Турниры. Ориентированные графы и бинарные отношения.

Модуль 2. Булевы функции и конечные автоматы.

• Лекция 1. Определение булевой функции. Табличное задание. Характеристическое множество. Представление функций формулами. Основные тождества булевой алгебры. Эквивалентность формул. Существенные и фиктивные переменные.
• Лекция 2. Булев вектор и булев куб. Векторное представление булевых функций. Троичные матрицы. Элементарные булевы функции.
• Лекция 3. Дизъюнктивные и конъюнктивные нормальные формы булевых функций. СДНФ и СКНФ.
• Лекция 4. Локальное упрощение булевых функций. Импликанты и интервалы. Отношения и операции с троичными векторами.
• Лекция 5. Карты Карно. Основные операции с булевыми функциями на картах Карно. Минимизация булевых функций при помощи карт Карно.
• Лекция 6. Минимизация булевых функций методом Квайна-МакКласски. Поиск минимального покрытия матрица Квайна методом Петрика.
• Лекция 7. Основные классы булевых функций. Самодвойственные, монотонные, линейные булевы функции. Полные системы.
• Лекция 8. Конечные автоматы. Определение. Классификация. Способы описания. Автоматы Миля и Мура. Автоматные языки и грамматики. Реализации конечных автоматов. Минимизация автоматов.