Дискретная математика для программистов

Содержание
Введение
История развития курса
Цели курса
Структура курса
Используемые обозначения
Стандартные математические
символы
Выделения в тексте
Онтология дискретной матема-
тики
Подведение итогов
1. Множества и отношения
1.1. Множества
1.1.1. Элементы и множества
1.1.2. Задание множеств
1.1.3. Парадокс Рассела
1.1.4. Мультимножества
1.1.5. Конечные последовательности
1.2. Алгебра подмножеств
1.2.1. Сравнение множеств
1.2.2. Равномощные множества
1.2.3. Конечные и бесконечные множества
1.2.4. Счётные и несчётные множества
1.2.5. Мощность конечного множества
1.2.6. Операции над множествами
1.2.7. Разбиения и покрытия
1.2.8. Булеан
1.2.9. Свойства операций над множествами
1.3. Представление множеств в
программах
1.3.1. Битовые шкалы
1.3.2. Представление натуральных чисел
1.3.3. Перебор подмножеств множества
1.3.4. Алгоритм построения кода Грея
1.3.5. Представление множеств списками
1.3.6. Проверка включения слиянием
1.3.7. Вычисление объединения слиянием
1.3.8. Вычисление пересечения слиянием
1.3.9. Представление множеств итераторами
1.4. Отношения
1.4.1. Упорядоченные пары и наборы
1.4.2. Прямое произведение множеств
1.4.3. Размеченное объединение множеств
1.4.4. Бинарные отношения
1.4.5. Композиция отношений
1.4.6. Свойства отношений
1.4.7. Степень отношения и циклы
1.4.8. Ядро отношения
1.4.9. Представление отношений в программах
1.5. Замыкание и сокращение отношений
1.5.1. Транзитивное и рефлексивное замыкание
1.5.2. Алгоритм Уоршалла
1.5.3. Транзитивное сокращение
1.5.4. Диаграммы Хассе
1.6. Функции
1.6.1. Функциональные отношения
1.6.2. Инъекция, сюръекция и биекция
1.6.3. Образы и прообразы
1.6.4. Суперпозиция функций
1.6.5. Степень функции
1.6.6. Представление функций в программах
1.7. Отношения эквивалентности
1.7.1. Классы эквивалентности
1.7.2. Ядро функционального отношения
1.7.3. Фактормножество
1.7.4. Множества уровня
1.7.5. Толерантность
1.7.6. Гомоморфизмы и изоморфизмы
1.8. Отношения порядка
1.8.1. Предпорядок
1.8.2. Частичный и линейный порядок
1.8.3. Минимальные и наименьшие элементы
1.8.4. Алгоритм топологической сортировки
1.8.5. Верхние и нижние границы
1.8.6. Монотонные и непрерывные функции
1.8.7. Наименьшая неподвижная точка функции
1.8.8. Вполне упорядоченные множества
1.8.9. Индукция
1.9. Характеристические функ-
ции
1.9.1. Классификация характеристических
функций
1.9.2. Характеристические функции мно-
жеств
1.9.3. Характеристические функции отноше-
ний
1.9.4. Характеристические функции мульти-
множеств
1.9.5. Классификаторы
1.9.6. Нечёткие множества
2. Алгебраические структуры
2.1. Алгебры и морфизмы
2.1.1. Операции и их носители
2.1.2. Замыкания и подалгебры
2.1.3. Система образующих
2.1.4. Свойства операций
2.1.5. Таблицы Кэли
2.1.6. Гомоморфизмы и изоморфизмы ал-
гебр
2.2. Алгебры с одной операцией
2.2.1. Полугруппы
2.2.2. Определяющие соотношения
2.2.3. Системы подстановок термов
2.2.4. Алгоритм Кнута–Бендикса
2.2.5. Моноиды
2.2.6. Группы
2.2.7. Действие группы на множестве
2.2.8. Группа перестановок
2.2.9. Перестановочные матрицы
2.3. Алгебры с двумя операция-
ми2.3.1. Кольца
2.3.2. Области целостности и тела
2.3.3. Поля
2.4. Элементарная теория чисел
2.4.1. Делимость чисел
2.4.2. Наибольший общий делитель и наи-
меньшее общее кратное
2.4.3. Линейное представление наибольше-
го общего делителя
2.4.4. Простые числа
2.4.5. Сравнения
2.4.6. Системы вычетов
2.4.7. Китайская теорема об остатках
2.4.8. Вычисления в остаточных классах
2.4.9. Функция Эйлера
2.5. Векторные пространства
2.5.1. Пространство векторов над полем
2.5.2. Линейные комбинации
2.5.3. Базис и размерность
2.5.4. Конечные поля
2.5.5. Модули
2.5.6. Алгебры Ли
2.6. Решётки
2.6.1. Дистрибутивные и ограниченные ре-
шётки
2.6.2. Решётки с дополнением
2.6.3. Частичный порядок в решётке
2.6.4. Полные решётки
2.6.5. Полурешётки
2.6.6. Булевы алгебры
2.7. Матроиды и жадные алгорит-
мы
2.7.1. Матроиды
2.7.2. Максимальные независимые подмно-
жества
2.7.3. Базисы
2.7.4. Циклы в матроидах
2.7.5. Жадный алгоритм
2.7.6. Примеры применения матроидов
3. Булевы функции
3.1. Элементарные булевы функ-
ции
3.1.1. Функции алгебры логики
3.1.2. Существенные и несущественные пе-
ременные
3.1.3. Булевы функции одной переменной
3.1.4. Булевы функции двух переменных
3.1.5. Функции k-значной логики
3.2. Формулы
3.2.1. Реализация функций формулами
3.2.2. Равносильные формулы
3.2.3. Подстановка и замена
3.2.4. Алгебра булевых функций
3.3. Двойственность и симметрия
3.3.1. Двойственные и самодвойственные
функции
3.3.2. Реализация двойственной функции
3.3.3. Принцип двойственности
3.3.4. Симметрические функции
3.4. Нормальные формы
3.4.1. Разложение булевых функций по пе-
ременным
3.4.2. Минимальные термы
3.4.3. Совершенные нормальные формы
3.4.4. Эквивалентные преобразования
3.4.5. Минимальные дизъюнктивные формы
3.4.6. Геометрическая интерпретация
3.4.7. Сокращённые дизъюнктивные формы
3.5. Представление булевых
функций в программах
3.5.1. Табличные представления
3.5.2. Строковые представления
3.5.3. Алгоритм вычисления значения буле-
вой функции
3.5.4. Представление булевых функций
арифметическими полиномами
3.5.5. Карты Карно и матрицы минтермов
3.5.6. Булевы функции и карты Карно
3.5.7. Минимизация формул картами Карно
3.5.8. Деревья решений
3.6. Полные системы булевых
функций
3.6.1. Замкнутые классы
3.6.2. Полные системы функций
3.6.3. Полнота двойственной системы
3.6.4. Теорема Поста
4. Логические исчисления
4.1. Логические связки и кванто-
ры
4.1.1. Высказывания и связки
4.1.2. Формулы
4.1.3. Интерпретация
4.1.4. Логические следование и эквивалент-
ность
4.1.5. Подстановка и замена
4.1.6. Кванторы
4.1.7. Формализация
4.2. Формальные теории
4.2.1. Определение формальной теории
4.2.2. Выводимость
4.2.3. Интерпретация
4.2.4. Общезначимость и непротиворечи-
вость
4.2.5. Полнота, независимость и разреши-
мость
4.3. Исчисление высказываний
4.3.1. Определение исчисления высказыва-
ний
4.3.2. Частный случай формулы
4.3.3. Алгоритмы унификации
4.3.4. Конструктивное определение исчис-
ления высказываний
4.3.5. Производные правила вывода
4.3.6. Дедукция
4.3.7. Некоторые теоремы исчисления вы-
сказываний
4.3.8. Множество теорем исчисления выска-
зываний
4.3.9. Другие аксиоматизации исчисления
высказываний
4.4. Исчисление предикатов
4.4.1. Определение исчисления предикатов
4.4.2. Интерпретация
4.4.3. Общезначимость
4.4.4. Непротиворечивость и полнота чисто-
го исчисления предикатов
4.4.5. Логическое следование и логическая
эквивалентность
4.4.6. Теория равенства
4.4.8. Неаксиоматизируемые теории
4.4.9. Теоремы Гёделя о неполноте
4.5. Наивная теория алгоритмов
4.5.1. Алгоритмы
4.5.2. Вычислимые функции
4.5.3. Перечислимые множества
4.5.4. Разрешимые множества
4.5.5. Протокол выполнения алгоритма
4.5.6. Программы
4.5.7. Невычислимые функции и неразреши-
мые множества
4.5.8. Истинность и доказуемость
4.5.9. Множество истин арифметики
4.6. Автоматическое доказатель-
ство теорем
4.6.1. Постановка задачи автоматического
доказательства теорем
4.6.2. Доказательство от противного
4.6.3. Свед ́ение к дизъюнктам
4.6.4. Правило резолюции для исчисления
высказываний
4.6.5. Правило резолюции для исчисления
предикатов
4.6.6. Опровержение методом резолюций
4.6.7. Дерево вывода
4.6.8. Алгоритм метода резолюций
4.6.9. Стратегии метода резолюций
5. Комбинаторный анализ
5.1. Комбинаторные задачи
5.1.1. Комбинаторные конфигурации
5.1.2. Размещения
5.1.3. Размещения без повторений
5.1.4. Перестановки
5.1.5. Сочетания
5.1.6. Сочетания с повторениями
5.1.7. Дискретная вероятность
5.2. Перестановки
5.2.1. Циклы в перестановках
5.2.2. Порядок перестановки
5.2.3. Инверсии
5.2.4. Генерация перестановок
5.2.5. Двойные факториалы
5.2.6. Быстрая сортировка
5.2.7. Трудоёмкость в среднем
5.2.8. Гармонические числа
5.2.9. Оценка в среднем для быстрой сорти-
ровки
5.3. Биномиальные коэффициен-
ты5.3.1. Свойства биномиальных коэффициен-
тов
5.3.2. Бином Ньютона
5.3.3. Треугольник Паскаля
5.3.4. Применение рекуррентного соотно-
шения
5.3.5. Генерация подмножеств
5.3.6. Расширенные биномиальные коэффи-
циенты
5.3.7. Мультимножества и последовательно-
сти
5.3.8. Мультиномиальные коэффициенты
5.3.9. Биномиальная система счисления
5.4. Разбиения
5.4.1. Числа Стирлинга
5.4.2. Числа Моргана
5.4.3. Вычисление чисел Стирлинга
5.4.4. Числа Белла
5.4.5. Треугольник Белла
5.5. Включения и исключения
5.5.1. Объединение конфигураций
5.5.2. Формула включений и исключений
5.5.3. Число булевых функций, существенно
зависящих от всех своих переменных
5.5.4. Комбинации свойств
5.5.5. Беспорядки и субфакториал
5.6. Формулы обращения
5.6.1. Теорема обращения
5.6.2. Формулы обращения
5.6.3. Формулы для чисел Стирлинга и
Моргана
5.6.4. Полиномы с рациональными коэффи-
циентами
5.7. Производящие функции
5.7.1. Формальные степенные ряды
5.7.2. Метод неопределённых коэффициен-
тов
5.7.3. Числа Фибоначчи
5.7.4. Числа Каталана
6. Кодирование
6.1. Алфавитное кодирование
6.1.1. Таблица кодов
6.1.2. Разделимые схемы
6.1.3. Префиксные схемы
6.1.4. Неравенство Макмиллана
6.2. Кодирование с минималь-
ной избыточностью
6.2.1. Минимизация длины кода сообщения
6.2.2. Цена кодирования
6.2.3. Алгоритм Фано
6.2.4. Оптимальное кодирование
6.2.5. Алгоритм Хаффмена
6.3. Помехоустойчивое кодиро-
вание
6.3.1. Кодирование с исправлением ошибок
6.3.2. Возможность исправления всех оши-
бок
6.3.3. Расстояния Левенштейна и Хэмминга
6.3.4. Кодовое расстояние схемы
6.3.5. Мощность кодирования
6.3.6. Виды кодирования
6.3.7. Систематическая форма кодовых со-
общений
6.3.8. Коды Хэмминга
6.3.9. Исправление одного замещения
6.4. Сжатие и шифрование дан-
ных
6.4.1. Сжатие текстов
6.4.2. Предварительное построение словаря
6.4.3. Алгоритм Лемпела–Зива
6.4.4. Криптография
6.4.5. Шифрование с помощью случайных
чисел
6.4.6. Криптостойкость
6.4.7. Шифрование с открытым ключом
6.4.8. Цифровая подпись
7. Графы
7.1. Определения графов
7.1.1. История теории графов
7.1.2. Основное определение
7.1.3. Инцидентность, смежность и дополне-
ние
7.1.4. Диаграмма графа
7.1.5. Орграфы, псевдографы, мультиграфы
и гиперграфы
7.1.6. Изоморфизм графов
7.2. Элементы графов
7.2.1. Подграфы
7.2.2. Валентность
7.2.3. Маршруты, цепи, циклы
7.2.4. Связные и несвязные графы
7.2.5. Расстояние между вершинами, ярусы,
эксцентриситет, диаметр, радиус, центр
7.2.6. Степенные последовательности
7.3. Виды графов и операции над
графами
7.3.1. Полные и пустые графы
7.3.2. Двудольные графы
7.3.3. Звёздные графы
7.3.4. Направленные орграфы и сети
7.3.5. Операции над графами
7.3.6. Свойства простых циклов
7.3.7. Рёберные графы
7.4. Представление графов в
программах
7.4.1. Требования к представлению графов
7.4.2. Матрица смежности
7.4.3. Матрица инциденций
7.4.4. Списки смежности
7.4.5. Массив дуг
7.4.6. Обходы графов
7.5. Графы и отношения
7.5.1. Орграфы и бинарные отношения
7.5.2. Граф инциденций
7.5.3. Гиперграфы и многоместные отноше-
ния
7.5.4. Достижимость и частичное упорядоче-
ние
7.5.5. Достижимость и транзитивное замы-
кание
8. Связность
8.1. Компоненты связности
8.1.1. Объединение графов и компоненты
связности
8.1.2. Точки сочленения, мосты и блоки
8.1.3. Свойства блоков
8.1.4. Вершинная и рёберная связность
8.1.5. Оценка числа рёбер
8.2. Теорема Менгера
8.2.1. Непересекающиеся цепи и разделяю-
щие множества
8.2.2. Теорема Менгера в «вершинной фор-
ме»
8.2.3. Варианты теоремы Менгера
8.3. Паросочетания
8.3.1. Задачи о свадьбах, трансверсалях и
паросочетаниях
8.3.2. Теорема Холла
8.3.3. Латинские квадраты
8.3.4. Устойчивые паросочетания
8.3.5. Наибольшее паросочетание
8.3.6. Алгоритм поиска наибольшего паро-
сочетания
8.4. Потоки в сетях
8.4.1. Определение потока
8.4.2. Разрезы
8.4.3. Теорема Форда–Фалкерсона
8.4.4. Алгоритм нахождения максимального
потока
8.4.5. Связь между теоремой Менгера и тео-
ремой Форда–Фалкерсона
8.5. Связность в орграфах
8.5.1. Сильная, односторонняя и слабая
связность
8.5.2. Компоненты сильной связности
8.5.3. Выделение компонент сильной связ-
ности
8.5.4. Базисы ориентированных графов
8.6. Кратчайшие пути
8.6.1. Взвешенные орграфы
8.6.2. Кратчайшие пути в бесконтурном ор-
графе
8.6.3. Алгоритм Беллмана–Форда
8.6.4. Алгоритм Дейкстры
8.6.5. Область применимости алгоритма
Дейкстры
8.6.6. Анализ алгоритма Дейкстры
8.6.7. Алгоритм Флойда–Уоршалла
8.6.8. Алгоритмы с предобработкой
9. Деревья
9.1. Свободные деревья
9.1.1. Свободные деревья и их элементы
9.1.2. Основные свойства деревьев
9.1.3. Центр дерева
9.2. Ориентированные, упорядо-
ченные и бинарные деревья
9.2.1. Ориентированные деревья
9.2.2. Эквивалентные определения ордере-
ва
9.2.3. Упорядоченные деревья
9.2.4. Бинарные деревья
9.3. Представление деревьев в
программах
9.3.1. Представление свободных деревьев
9.3.2. Представление упорядоченных кор-
невых деревьев
9.3.3. Число упорядоченных ориентирован-
ных деревьев
9.3.4. Проверка правильности скобочной
структуры
9.3.5. Представление бинарных деревьев
9.3.6. Обходы бинарных деревьев
9.4. Деревья сортировки
9.4.1. Ассоциативная память
9.4.2. Таблицы расстановки
9.4.3. Эффективность хэширования
9.4.4. Алгоритм поиска в дереве сортировки
9.4.5. Алгоритм вставки в дерево сортиров-
ки
9.4.6. Алгоритм удаления из дерева сорти-
ровки
9.4.7. Вспомогательные алгоритмы для де-
рева сортировки
9.4.8. Сравнение представлений ассоциа-
тивной памяти
9.5. Специальные деревья
9.5.1. Выровненные и полные деревья
9.5.2. Сбалансированные деревья
9.5.3. Балансировка деревьев
9.5.4. Двоичные кучи
9.5.5. Восстановление свойства кучи
9.5.6. Реализация операций кучи
9.5.7. Построение графа по степенному ряду
9.5.8. Дерево отрезков
9.5.9. Оценки эффективности дерева отрез-
ков
9.6. Кратчайший остов
9.6.1. Стягивающие деревья и остовы
9.6.2. Схема алгоритма построения кратчай-
шего остова
9.6.3. Алгоритм Краскала
9.6.4. Алгоритм Прима
10. Циклы, независимость и рас-
краска
10.1. Фундаментальные циклы и
разрезы
10.1.1. Циклы и разрезы
10.1.2. Фундаментальная система циклов
и циклический ранг
10.1.3. Фундаментальная система разрезов
и коциклический ранг
10.1.4. Подпространства циклов и коциклов
10.2. Эйлеровы циклы
10.2.1. Эйлеровы графы
10.2.2. Алгоритм построения эйлерова цик-
ла в эйлеровом графе
10.2.3. Оценка числа эйлеровых графов
10.3. Гамильтоновы циклы
10.3.1. Гамильтоновы графы
10.3.2. Задача коммивояжёра
10.3.3. Теорема Поша
10.4. Независимые и покрываю-
щие множества
10.4.1. Независимые и покрывающие мно-
жества вершин и рёбер
10.4.2. Связь чисел независимости и покры-
тий
10.4.3. Оценка числа вершинной независи-
мости
10.4.4. Теорема Кёнига
10.5. Построение независимых
множеств вершин
10.5.1. Постановка задачи отыскания наи-
большего независимого множества вершин
10.5.2. Поиск с возвратами
10.5.3. Улучшенный перебор
10.5.4. Алгоритм построения независимых
множеств
10.6. Доминирующие множества
10.6.1. Минимальные и наименьшие доми-
нирующие множества
10.6.2. Доминирование и независимость
10.6.3. Задача о наименьшем покрытии
10.6.4. Связь задачи о наименьшем покры-
тии с другими задачами
10.7. Раскраска графов
10.7.1. Хроматическое число графа и его
оценки
10.7.2. Хроматические числа графа и его до-
полнения
10.7.3. Точный алгоритм раскрашивания
10.7.4. Приближённые алгоритмы раскра-
шивания
10.7.5. Хроматический полином
10.8. Планарность
10.8.1. Укладка графов
10.8.2. Эйлерова характеристика
10.8.3. Теорема о пяти красках