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

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

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

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

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

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

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

Исчисление высказываний

• Пример задачи логики высказываний
• Формальные теории
• Формальная теория исчисление высказываний
• Теоремы исчисления высказываний
• Теорема о полноте исчисления высказываний
• Независимость аксиом исчисления высказываний

Алгоритмы

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