Просолупов Е.В. Курс лекций по дискретной математике

Учебное пособие. — СПб.: Санкт-Петербургский государственный университет, 2012. — 217 с.В учебном пособии рассматриваются основные разделы дискретной математики: комбинаторика, математическая логика, теория алгоритмов, теория графов. Курс не требует специальных знаний для начала освоения. Вся необходимая терминология подробно разбирается по мере прохождения материала. Определения и утверждения подкреплены большим количеством примеров.
Учебное пособие основано на курсе по дискретной математике, который автор читал в течении семи лет на факультете прикладной математики и процессов управления Санкт-Петербургского государственного университета.Основы теории множеств
Бинарные отношения, функции, отношения эквивалентности
Отношения порядка
Размещения и сочетания, бином Ньютона, формула обращения
Мультимножества, мультиномиальная формула, число разбиений множества
Композиция и разбиение числа, группа перестановок
Циклы перестановки, тип перестановки
Принцип включения-исключения, задача о беспорядках
Мощность объединения множеств, число целочисленных решений системы неравенств
Булевы функции и формулы
Дизъюнктивные и конъюнктивные нормальные формы
Полином Жегалкина
Полные системы функций в P₂
Самодвойственные и монотонные функции
Линейные функции, критерий полноты
Исчисление высказываний
Теоремы исчисления высказываний
Вспомогательные утверждения к теореме о полноте исчисления высказываний
Полнота, независимость аксиом исчисления высказываний
Исчисление предикатов
Исчисление предикатов: продолжение
Машины Тьюринга
Алгоритмически неразрешимые задачи
Сложность алгоритмов
NP-полные задачи
Основные определения теории графов
Маршруты и операции над графами
Инварианты и способы задания графа
Деревья и обходы графа
Минимальное остовное дерево и деревья поиска
АВЛ-деревья
NP-полные задачи теории графов