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

Основы теории множеств

• Множества
• Диаграммы Эйлера-Венна
• Прямое произведение множеств
• Парадокс Рассела
• Аксиомы ZFC
• Бинарные отношения
• Отношение эквивалентности
• Отношение порядка
• Лексикографический порядок

Комбинаторика

• Размещения
• Сочетания
• Треугольник Паскаля
• Перебор сочетаний
• Бином Ньютона
• Мультимножества
• Мультиномиальная формула Ньютона
• Разбиения множеств
• Композиция натурального числа
• Разбиения натурального числа
• Перестановки
• Группа перестановок
• Циклы перестановки
• Тип перестановки
• Принцип включения-исключения
• Задача о беспорядках
• Мощность объединения множеств
• Число целочисленных решений системы неравенств

Булевы функции

• Булевы функции
• Формулы
• Основные тождества
• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма
• Разложение функции по переменным
• Полином Жегалкина
• Полнота системы функций
• Функции, сохраняющие ноль
• Функции, сохраняющие единицу
• Двойственные функции
• Самодвойственные функции
• Монотонные функции
• Линейные функции
• Критерий полноты системы функций

Алгоритмы

• Понятие алгоритма
• Машина Тьюринга
• Стандартные конфигурации машины Тьюринга
• Вычислимые функции
• Алгоритмически неразрешимые задачи
• Сложность алгоритмов
• Полиномиальная сводимость
• Классы задач в форме распознавания свойств
• NP-полные задачи
• Задача коммивояжера