== Список вопросов к экзамену ==

=== июль 2023 ===

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