Алексеев В.Е. Дискретная математика

Учебное пособие. — Н. Новгород: Нижегородский государственный университет им. Н.И. Лобачевского, 2017. — 139 с.В учебном пособии излагаются основные понятия и фундаментальные факты важнейших разделов дискретной математики: комбинаторики, теории графов, теории логических функций, теории кодирования.
Учебное пособие предназначено для студентов ННГУ, обучающихся по направлениям подготовки «Прикладная математика и информатика», «Математика», «Математика и компьютерные науки».Множества.
Понятие множества.
Подмножества.
Алгебра множеств.
Диаграмма Венна.
Декартово произведение.
Мультимножества.
Отношения.
Понятие отношения, общие свойства отношений.
Отношения эквивалентности.
Отношения порядка.
Более общие виды отношений.
Функциональные отношения и функции.
Сравнение бесконечных множеств. Cчетные и несчетные множества.
Комбинаторика.
Принципы подсчета.
Наборы и слова.
Лексикографический порядок.
Перестановки.
Последовательный выбор.
Размещения.
Сочетания.
Бином Ньютона. Биномиальные коэффициенты.
Упорядоченные разбиения.
Полиномиальная теорема.
Сочетания с повторениями.
Формула включений-исключений.
Неупорядоченные разбиения.
Функции.
Линейные рекуррентные уравнения.
Рекуррентные уравнения.
Линейные рекуррентные уравнения первого порядка.
Линейные рекуррентные уравнения второго порядка.
Графы.
Основные понятия теории графов.
Изоморфизм.
Пути и циклы.
Расстояния. Метрические характеристики.
Эйлеровы циклы и пути.
Деревья.
Двудольные графы.
Планарные графы.
Логические функции. Алгебра логики.
Булевы функции. Существенные и фиктивные переменные.
Элементарные функции. Формулы. Алгебра логики.
Булевы формулы.
Нормальные формы.
Полиномы.
Логические функции. Полные системы.
Суперпозиция, замкнутость и полнота.
Важнейшие замкнутые классы.
Функции, сохраняющие константы.
Монотонные функции.
Самодвойственные функции.
Линейные функции.
Критерий полноты.
Предполные классы и базисы.
Дополнительные сведения.
Схемы.
Схемы из функциональных элементов.
Построение схем.
Сумматор.
Дополнительные сведения.
Кодирование.
Задача оптимального кодирования.
Префиксные коды.
Оптимальный двоичный префиксный код.
Недвоичный оптимальный код.