Глава 3. Графы
3.1.Определения и примеры
3.2.Деревья
3.3.Двудольные графы
3.4.Графы абстрактные и помеченные. Автоморфизмы
3.5.Эйлеровы графы
3.6.Гамильтоновы графы
3.7.Паросочетания
3.8.Связность
3.9.Планарность
3.10.Раскраски
3.11.Теоремы Турана и Рамсея
3.12.Перечисление графов
Задачи для самостоятельного решения
Литература
Глава 4. Алгоритмы
4.1.Понятие алгоритма
4.2.Алгоритмы на графах
4.3.Потоки в сетях
4.4.Практические методы решения задач дискретной оптимизации
4.5.Жадные алгоритмы и матроиды
4.6.Теория сложности: классы P и NP
4.7.Сложность приближённого решения
4.8.Машина Тьюринга
4.9.Теорема Кука
Задачи для самостоятельного решения
Литература
Глава 5. Коды, блок-схемы, шифры
5.1.Задачи кодирования
5.2.Экономное кодирование. Алгоритм Хаффмана
5.3.Принципы помехоустойчивого кодирования
5.4.Линейные коды. Коды Хэмминга
5.5.Скорость передачи и вероятность ошибки. Теорема Шеннона
5.6.Коды Рида--Маллера
5.7.Конечные поля
5.8.Коды БЧХ
5.9.Латинские квадраты. Блок-схемы. Матрицы Адамара
5.10.Коды Адамара. Совершенный код Голея
5.11.О плотности упаковки шаров Хэмминга
5.12.Математические принципы современной криптографии
Задачи для самостоятельного решения
Литература
Дополнение 1. Упорядоченные множества
Определения и примеры; линейные продолжения; разбиения на цепи; решётки и булевы алгебры; модулярные и геометрические решётки; алгебра инцидентности; обращение Мёбиуса; свойства функции Мёбиуса; примеры обращения Мёбиуса
Задачи для самостоятельного решения
Литература
Дополнение 2. Вероятностный метод
Основы; случайные величины ; метод математических ожиданий; длина д. н. ф. типичной булевой функции; теорема Шеннона; максимальная тень антицепи; случайные (±1)-матрицы и детерминанты; дальнейшие результаты и гипотезы
Задачи для самостоятельного решения
Литература
Ответы и указания к решению задач