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

1-й курс магистратуры.

Выборки. Перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальная  и полиномиальная теоремы. Разбиения. Числа Стирлинга 1-го и 2-го рода; свойства чисел Стирлинга; обращение Стирлинга. Числа Белла и их свойства. Формулы обращения. Дзета-функция и функция Мёбиуса. Метод включений и исключений. Оценки для числа элементов, не обладающих ни одним  из  n свойств. Формула для числа элементов, обладающих в точности m свойствами, 0 ≤ m ≤ n. Формула обращения Мёбиуса. Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Линейные рекуррентные соотношения с постоянными коэффициентами. Теорема о решении линейных рекуррентных соотношений. Числа Фибоначчи. Числа Каталана. Экспоненциальные производящие функции. Трансверсаль. Теорема о числе трансверсалей. Задача о гаремах. Латинские прямоугольники. Теорема Рамсея. Теорема Рамсея для графов.  Верхние и нижние оценки для чисел Рамсея. Теорема Эрдеша – Секереша. Теорема Ван дер Вардена  об арифметических последовательностях.

Булевы функции, их реализация формулами. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Принцип двойственности. Полином Жегалкина. Предполные классы функций. Теорема Поста. Минимальные и кратчайшие ДНФ. Алгоритм Квайна – Мак-Клоски. Карты Карно. Метод Блейка получения сокращенной ДНФ. Таблицы Квайна. Схема из функциональных элементов, ее сложность. Метод Лупанова синтеза схем из функциональных элементов. Мощностной метод получения нижней оценки функции Шеннона для СФЭ. Контактная схема, ее сложность. Функция Шеннона для контактных схем. Метод каскадов для контактных схем. Нижняя оценка функции Шеннона для контактных схем. Схема Кардо. Ограниченно-детерминированные функции. Способы их задания. Конечный детерминированный автомат с выходом. Автоматные функции, связь с ограниченно-детерминированными функциями. Схема из автоматных элементов. Теорема о не существовании конечных полных систем автоматных функций. Схемы из автоматных элементов с использованием операции обратной связи. Реализация произвольной автоматной функции.

Графы. Основные понятия. Способы представления графов. Перечисление графов на нумерованных вершинах. Верхняя оценка для числа неизоморфных графов с  q  ребрами. Деревья и их свойства. Оценка числа неизоморфных корневых  деревьев с  q   ребрами. Теорема Кэли о числе помеченных деревьев. Связность. Свойства двусвязных графов. Теорема Менгера. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для ориентированных графов, последовательности де Брейна. Гамильтоновы циклы. Теорема Дирака. Гамильтоновы циклы и степенные последовательности. Теорема Хватала. Гамильтоновы циклы и совершенные паросочетания. Теорема Финка. Укладка графа в пространство. Планарный и плоский графы. Формула Эйлера. Теорема Понтрягина-Куратовского. Алгебраические критерии планарности. Правильная раскраска вершин графа. Оценки хроматического числа. Теорема Брукса. Теорема Зыкова. Раскраски планарных графов. Теорема о четырех красках. Совершенные графы. Теорема Ловаца. Совершенность триангулированных графов. Правильная раскраска ребер графа. Хроматический индекс. Теорема Кёнига о хроматическом индексе двудольных графов. Теорема Визинга.