Инструменты сайта


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

июль 2023

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