Каверин С.В. Лекции по дискретной математике

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