Раздел: Математические.
Категория: Дискретная математика

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

• Понятие множества. Способы задания. Подмножества. Операции над множествами: пересечение, объединение. Диаграммы Эйлера-Венна.
• Декартово произведение множеств.
• Универсальное множество. Дополнение. Правила де Моргана.
• Отношения. Бинарные отношения. Свойства отношений. Рефлексивные, симметричные, транзитивные отношения.
• Отношение эквивалентности. Классы эквивалентности. Фактор-множество. Разбиение (покрытие) множества. Классы разбиения.
• Отношение порядка: частичный порядок, строгий порядок. Максимальные и минимальные элементы Диаграммы Хассе.
• Транзитивное замыкание отношений.

Алгебра высказываний и логика предикатов.

• Высказывания. Логические операции над высказываниями. Таблицы истинности.
• Понятие тавтологии и противоречия.
• Логическая эквивалентность и логическая импликация.
• Конверсия. Инверсия. Контрапозиция. Логические функции. Стрелка Пирса. Штрих Шеффера.
• Теория доказательств: непосредственное доказательство условных высказываний; доказательство с помощью контрапозиции; доказательство методом от противного; доказательство контрпримером; метод математической индукции.
• Логика предикатов. Термы, предикаты, кванторы.
• Связанные и свободные переменные.
• Правильно построенные формулы (ППФ).
• Резолютивный вывод в логике первого порядка. Доказательство теорем.

Алгебра логики.

• Единичный куб и функции алгебры логики.
• Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ).
• Совершенная дизъюнктивная нормальная форма.
• Формулы в стандартном базисе. Реализация функций формулами.
• Эквивалентность формул. Эквивалентные преобразования формул на основе тождеств.
• Минимизация дизъюнктивных нормальных форм (ДНФ). Карты Карно.
• Сокращенная дизъюнктивная нормальная форма и способы ее построения.
• Тупиковые дизъюнктивные нормальные формы.
• Формулы общего вида. Полнота и примеры полных систем. Представление функций алгебры логики полиномами.
• Двойственность и класс самодвойственных функций.
• Класс линейных функций. Полином Жегалкина.
• Классы функций сохранения константы. Монотонные функции.
• Замыкание и основные замкнутые классы. Теорема о полноте (Теорема Поста).

Теория графов

• Графы. Основные понятия теории графов. Операции над графами.
• Типы и задания графов: матрица смежности, матрица инцидентности, матрица весов.
• Цепи, циклы, компоненты.
• Изоморфизм и связность.
• Алгоритмы поиска в графе: поиск в глубину (метод оптимиста), поиск в ширину (метод пессимиста).
• Формула Эйлера. Эйлеровы циклы. Эйлеровы графы
• Нахождение расстояния между вершинами графа (алгоритм Флойда).
• Нахождение кратчайшего пути (метод Дийкстра).
• Понятие о теореме Понтрягина – Куратовского.
• Остовные деревья.
• Алгоритмы на остовных деревьях: жадный алгоритм построения минимального остовного дерева, алгоритм ближайшего соседа построения остовного дерева.
• Транспортные сети. Потоки в сетях. Построение полного потока. Алгоритм Форда-Фалкерсона нахождения максимального потока.
• Двудольные графы.
• Хроматические графы. Задача раскраски графа.

Основы комбинаторики

• Общие правила комбинаторики. Формула включений и выключений Правило суммы и произведения.
• Размещения с повторениями и без повторений.
• Перестановки с повторениями и без повторений.
• Сочетания.
• Полиномиальные формулы. Бином Ньютона.
• Инверсии.

Теория автоматов

• Определение автомата. Операции с автоматами. Способы задания автоматов.
• Эквивалентность автоматов.
• Автоматы с конечной памятью.
• Автоматные базисы и проблема полноты.
• Автоматные языки.
• Машина Тьюринга. Операции над машиной Тьюринга.
• Автоматы Мили и Мура.