Дискретная математика, алгоритмы и структуры данных

Убедительная просьба читать правила оформления вики-конспектов.

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Первый семестр

Отношения

• Определение отношения
• Композиция отношений, степень отношения, обратное отношение
• Рефлексивное отношение. Антирефлексивное отношение.
• Симметричное отношение
• Антисимметричное отношение
• Транзитивное отношение
• Отношение порядка
• Отношение эквивалентности
• Транзитивное замыкание отношения
• Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
• Транзитивный остов

Булевы функции

• Определение булевой функции
• Суперпозиции
• ДНФ
• Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
• КНФ
• Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
• Полином Жегалкина, преобразование Мёбиуса
• Полные системы функций. Теорема Поста о полной системе функций
• Представление функции класса DM с помощью медианы
• Пороговая функция
• Троичная логика[math]^\star[/math]

Схемы из функциональных элементов

• Реализация булевой функции схемой из функциональных элементов
• Простейшие методы синтеза схем из функциональных элементов
• Метод Лупанова синтеза схем
• Cумматор
• Каскадный сумматор
• Двоичный каскадный сумматор
• Троичный сумматор[math]^\star[/math]
• Реализация вычитания сумматором
• Матричный умножитель
• Дерево Уоллеса
• Контактная схема
• Квантовые гейты[math]^\star[/math]

Представление информации

• Кодирование информации
• Представление целых чисел: прямой код, код со сдвигом, дополнительный код
• Представление вещественных чисел
• Представление символов, таблицы кодировок[math]^\star[/math]

Алгоритмы сжатия

• Алгоритм Хаффмана
• Оптимальное хранение словаря в алгоритме Хаффмана
• Алгоритм Хаффмана за O(n)
• Алгоритм Ху-Таккера[math]^\star[/math]
• Неравенство Крафта
• Неравенство Макмиллана
• Код Шеннона
• Оптимальный префиксный код с длиной кодового слова не более L бит[math]^\star[/math]
• Алгоритмы LZ77 и LZ78
• Алгоритм LZW
• Алгоритм LZSS[math]^\star[/math]
• Преобразование Барроуза-Уиллера и обратное ему
• Преобразование MTF
• Расстояние Хэмминга
• Избыточное кодирование, код Хэмминга
• Гамма-, дельта- и омега-код Элиаса[math]^\star[/math]

Комбинаторика

Комбинаторные объекты

• Комбинаторные объекты
• Лексикографический порядок
• Коды Грея
• Коды Грея для перестановок
• Коды антигрея
• Цепные коды
• Правильные скобочные последовательности

Генерация комбинаторных объектов

• Генерация комбинаторных объектов в лексикографическом порядке
• Получение номера по объекту
• Получение объекта по номеру
• Получение следующего объекта
• Получение предыдущего объекта[math]^\star[/math]
• Метод генерации случайной перестановки, алгоритм Фишера-Йетса
• Методы генерации случайного сочетания[math]^\star[/math]

Подсчёт числа объектов

• Формула включения-исключения, подсчет числа беспорядков
• Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
• Производящая функция
• Лемма Бёрнсайда и Теорема Пойа
• Задача об ожерельях
• Числа Стирлинга первого рода
• Числа Стирлинга второго рода
• Числа Эйлера первого и второго рода. Подъемы в перестановках[math]^\star[/math]
• Числа Каталана

Свойства комбинаторных объектов

• Умножение перестановок, обратная перестановка, группа перестановок
• Действие перестановки на набор из элементов, представление в виде циклов
• Таблица инверсий
• Теорема Кэли
• Матричное представление перестановок
• Задача о минимуме/максимуме скалярного произведения
• Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

Динамическое программирование

Классические задачи динамического программирования

• Кратчайший путь в ациклическом графе
• Задача о числе путей в ациклическом графе
• Задача о расстановке знаков в выражении
• Задача о порядке перемножения матриц
• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности
• Задача коммивояжера, ДП по подмножествам
• Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
• Задача о рюкзаке

Способы оптимизации методов динамического программирования

• Метод четырех русских для умножения матриц[math]^\star[/math]
• Применение метода четырех русских в задачах ДП на примере задачи о НОП[math]^\star[/math]
• Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
• Meet-in-the-middle[math]^\star[/math]

Другие задачи

• Задача о расстоянии Дамерау-Левенштейна[math]^\star[/math]
• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
• Задача о наибольшей подпоследовательности-палиндроме
• Наибольшая общая возрастающая подпоследовательность[math]^\star[/math]
• Задача о наибольшей общей палиндромной подпоследовательности[math]^\star[/math]
• Динамическое программирование по профилю[math]^\star[/math]
• Динамика по поддеревьям

Теория вероятностей

• Вероятностное пространство, элементарный исход, событие
• Независимые события
• Условная вероятность
• Формула полной вероятности
• Формула Байеса
• Дискретная случайная величина
• Независимые случайные величины
• Математическое ожидание случайной величины
• Дисперсия случайной величины
• Ковариация случайных величин
• Корреляция случайных величин
• Энтропия случайного источника
• Симуляция одним распределением другого
• Арифметическое кодирование
• Парадоксы теории вероятностей[math]^\star[/math]
• Схема Бернулли[math]^\star[/math]

Марковские цепи

• Марковская цепь
• Теорема о поглощении
• Фундаментальная матрица
• Математическое ожидание времени поглощения
• Расчет вероятности поглощения в состоянии
• Эргодическая марковская цепь
• Регулярная марковская цепь
• Примеры использования Марковских цепей
• Скрытые Марковские модели[math]^\star[/math]
• Алгоритм Витерби[math]^\star[/math]
• Алгоритм "Вперед-Назад"[math]^\star[/math]
• Алгоритм Баума-Велша[math]^\star[/math]

Второй семестр

Амортизационный анализ

• Амортизационный анализ
• Динамический массив
• Hashed Array Tree[math]^\star[/math]
• Список
• Стек
• Очередь
• Персистентный стек
• Персистентная очередь
• Персистентный дек
• Мажорирующий элемент
• Счетчик Кнута

Приоритетные очереди

• Двоичная куча
• Биномиальная куча
• Фибоначчиева куча
• Левосторонняя куча
• Тонкая куча
• Толстая куча на избыточном счетчике
• Куча Бродала-Окасаки[math]^\star[/math]

Система непересекающихся множеств

• Наивные реализации
• Списки с весовой эвристикой
• Реализация с помощью леса корневых деревьев
• СНМ с операцией удаления за О(1)[math]^\star[/math]

Поисковые структуры данных

• Упорядоченное множество
• Дерево поиска, наивная реализация
• АВЛ-дерево
• 2-3 дерево
• B-дерево
• Красно-черное дерево
• Декартово дерево
• Декартово дерево по неявному ключу
• Splay-дерево
• Tango-дерево[math]^\star[/math]
• Рандомизированное бинарное дерево поиска
• Дерево ван Эмде Боаса
• Список с пропусками
• Fusion tree[math]^\star[/math]
• Сверхбыстрый цифровой бор[math]^\star[/math]
• Rope[math]^\star[/math]

Дерево отрезков

• Статистики на отрезках. Корневая эвристика
• Дерево отрезков. Построение
• Реализация запроса в дереве отрезков сверху
• Реализация запроса в дереве отрезков снизу
• Несогласованные поддеревья. Реализация массового обновления
• Многомерное дерево отрезков
• Сжатое многомерное дерево отрезков

Дерево Фенвика

• Дерево Фенвика
• Встречное дерево Фенвика
• Дерево Фенвика для некоммутативных операций
• Многомерное дерево Фенвика

Хеширование

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование. Амортизационный анализ
• Фильтр Блума
• Универсальное семейство хеш-функций

Сортировка

Квадратичные сортировки

• Сортировка выбором
• Сортировка пузырьком
• Сортировка вставками

Сортировки на сравнениях

• Сортировка Шелла[math]^\star[/math]
• Сортировка кучей
• Быстрая сортировка
• Сортировка слиянием
• Cортировка слиянием с использованием O(1) дополнительной памяти
• Терпеливая сортировка[math]^\star[/math]
• Timsort[math]^\star[/math]
• Теорема о нижней оценке для сортировки сравнениями

Многопоточные сортировки

• Многопоточная сортировка слиянием[math]^\star[/math]
• PSRS-сортировка[math]^\star[/math]

Другие сортировки

• Поиск k-ой порядковой статистики
• Поиск k-ой порядковой статистики за линейное время
• Сортировка подсчетом
• Сортировка подсчетом сложных объектов
• Цифровая сортировка
• Карманная сортировка
• Сортировка Хана[math]^\star[/math]

Сортирующие сети

• Сортирующие сети
• Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
• Сортировочные сети с особыми свойствами[math]^\star[/math]
• Сортирующие сети для квадратичных сортировок
• Сеть Бетчера

Алгоритмы поиска

• Целочисленный двоичный поиск
• Вещественный двоичный поиск
• Троичный поиск
• Поиск с помощью золотого сечения
• Интерполяционный поиск

Связь между структурами данных

• Связь между структурами данных

Третий семестр

Основные определения теории графов

• Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
• Лемма о рукопожатиях
• Теорема о существовании простого пути в случае существования пути
• Теорема о существовании простого цикла в случае существования цикла
• Матрица смежности графа
• Связь степени матрицы смежности и количества путей
• Матрица инцидентности графа
• Циклическое пространство графа[math]^\star[/math]
• Фундаментальные циклы графа[math]^\star[/math]
• Дерево, эквивалентные определения
• Алгоритмы на деревьях[math]^\star[/math]
• Дополнительный, самодополнительный граф

Связность в графах

• Отношение связности, компоненты связности
• Отношение реберной двусвязности
• Отношение вершинной двусвязности
• Граф компонент реберной двусвязности
• Граф блоков-точек сочленения
• Точка сочленения, эквивалентные определения
• Мост, эквивалентные определения
• k-связность
• Теорема Менгера
• Теорема Менгера, альтернативное доказательство
• Вершинная, реберная связность, связь между ними и минимальной степенью вершины

Остовные деревья

Построение остовных деревьев

• Остовные деревья: определения, лемма о безопасном ребре
• Алгоритм Прима
• Алгоритм Краскала
• Алгоритм Борувки
• Теорема Тарьяна (критерий минимальности остовного дерева)
• Алгоритм двух китайцев

Свойства остовных деревьев

• Матрица Кирхгофа
• Связь матрицы Кирхгофа и матрицы инцидентности
• Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

Обходы графов

Эйлеровы графы

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Покрытие ребер графа путями
• Алгоритм построения Эйлерова цикла
• Произвольно вычерчиваемые из заданной вершины графы

Гамильтоновы графы

• Гамильтоновы графы
• Теорема Хватала
• Теорема Поша[math]^\star[/math]
• Теорема Дирака
• Теорема Оре
• Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
• Теорема Гринберга[math]^\star[/math]
• Турниры
• Теорема Редеи-Камиона

Укладки графов

• Укладка графа на плоскости
• Формула Эйлера
• Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
• Укладка дерева
• Укладка графа с планарными компонентами реберной двусвязности
• Укладка графа с планарными компонентами вершинной двусвязности
• Теорема Понтрягина-Куратовского
• Двойственный граф планарного графа
• Теорема Фари[math]^\star[/math]

Раскраски графов

• Раскраска графа
• Двудольные графы и раскраска в 2 цвета
• Хроматический многочлен
• Формула Зыкова
• Формула Уитни
• Теорема Брукса
• Верхние и нижние оценки хроматического числа[math]^\star[/math]
• Хроматическое число планарного графа
• Многочлен Татта[math]^\star[/math]
• Теория Рамсея[math]^\star[/math]

Обход в глубину

• Обход в глубину, цвета вершин
• Лемма о белых путях
• Использование обхода в глубину для проверки связности
• Использование обхода в глубину для поиска цикла
• Использование обхода в глубину для топологической сортировки
• Использование обхода в глубину для поиска компонент сильной связности
• Использование обхода в глубину для поиска точек сочленения
• Построение компонент вершинной двусвязности
• Использование обхода в глубину для поиска мостов
• Построение компонент реберной двусвязности

Кратчайшие пути в графах

• Обход в ширину
• Алгоритм Форда-Беллмана
• Алгоритм Дейкстры
• Алгоритм Левита[math]^\star[/math]
• Алгоритм Флойда
• Алгоритм A* [math]^\star[/math]
• Алгоритм Джонсона
• Эвристики для поиска кратчайших путей[math]^\star[/math]
• Алгоритм D* [math]^\star[/math]

Задача о паросочетании

• Теорема о максимальном паросочетании и дополняющих цепях
• Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
• Алгоритм Куна для поиска максимального паросочетания
• Теорема Холла
• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
• Связь вершинного покрытия и независимого множества
• Матрица Татта и связь с размером максимального паросочетания в двудольном графе
• Теорема Татта о существовании полного паросочетания
• Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
• Декомпозиция Эдмондса-Галлаи
• Задача об устойчивом паросочетании[math]^\star[/math]

Задача о максимальном потоке

• Определение сети, потока
• Разрез, лемма о потоке через разрез
• Дополняющая сеть, дополняющий путь
• Лемма о сложении потоков
• Теорема Форда-Фалкерсона
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алоритм Эдмондса-Карпа
• Алгоритм масштабирования потока
• Блокирующий поток
• Схема алгоритма Диница
• Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
• Алгоритм поиска блокирующего потока в ациклической сети
• Метод проталкивания предпотока
• Алгоритм "поднять-в-начало"
• Теорема о декомпозиции
• Теорема о декомпозиционном барьере
• Циркуляция потока
• Алгоритм Каргера для нахождения минимального разреза[math]^\star[/math]

Задача о потоке минимальной стоимости

• Поток минимальной стоимости
• Теорема Форда-Фалкерсона о потоке минимальной стоимости
• Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
• Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
• Использование потенциалов Джонсона при поиске потока минимальной стоимости
• Сведение задачи о назначениях к задаче о потоке минимальной стоимости
• Венгерский алгоритм решения задачи о назначениях

Четвертый семестр

Основные определения. Простые комбинаторные свойства слов

• Основные определения, связанные со строками
• Период и бордер, их связь
• Слово Фибоначчи
• Слово Туэ-Морса
• Декомпозиция Линдона[math]^\star[/math]
• Алгоритм Ландау-Шмидта[math]^\star[/math]
• Алгоритм Крочемора[math]^\star[/math]

Поиск подстроки в строке

• Наивный алгоритм поиска подстроки в строке
• Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
• Поиск наибольшей общей подстроки двух строк с использованием хеширования
• Префикс-функция
• Алгоритм Кнута-Морриса-Пратта
• Алгоритм Бойера-Мура[math]^\star[/math]
• Алгоритм Колусси[math]^\star[/math]
• Z-функция
• Автомат для поиска образца в тексте
• Бор
• Алгоритм Ахо-Корасик
• Алгоритм Ландау-Вишкина (k несовпадений)[math]^\star[/math]

Суффиксное дерево

• Суффиксный бор
• Сжатое суффиксное дерево
• Алгоритм Укконена
• Алгоритм МакКрейта[math]^\star[/math]
• Алгоритм Фарача[math]^\star[/math]

Суффиксный массив

• Суффиксный массив
• Построение суффиксного массива с помощью стандартных методов сортировки
• Алгоритм цифровой сортировки суффиксов циклической строки
• Алгоритм Касаи и др.
• Алгоритм Карккайнена-Сандерса
• Алгоритм поиска подстроки в строке с помощью суффиксного массива

Задача о наименьшем общем предке

• Метод двоичного подъема
• Сведение задачи LCA к задаче RMQ
• Решение RMQ с помощью разреженной таблицы
• Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
• Алгоритм Шибера-Вишкина[math]^\star[/math]
• Сведение задачи RMQ к задаче LCA
• Алгоритм Тарьяна поиска LCA за O(1) в оффлайн[math]^\star[/math]
• Link-Cut Tree[math]^\star[/math]

Матроиды

Основные факты теории матроидов

• Определение матроида
• Примеры матроидов
• Прямая сумма матроидов
• Теорема Радо-Эдмондса (жадный алгоритм)
• Теорема о базах
• Аксиоматизация матроида базами
• Теорема о циклах
• Аксиоматизация матроида циклами
• Ранговая функция, полумодулярность
• Двойственный матроид
• Оператор замыкания для матроидов
• Покрытия, закрытые множества
• Матроид Вамоса[math]^\star[/math]

Пересечение матроидов

• Пересечение матроидов, определение, примеры
• Лемма о паросочетании в графе замен
• Лемма о единственном паросочетании в графе замен
• Граф замен для двух матроидов
• Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
• Алгоритм построения базы в пересечении матроидов
• Теорема Эдмондса-Лоулера

Объединение матроидов

• Объединение матроидов, проверка множества на независимость
• Объединение матроидов, доказательство того, что объединение является матроидом
• Алгоритм построения базы в объединении матроидов

Теория расписаний

• Классификация задач
• Методы решения задач теории расписаний
• Правило Лаулера
• Flow shop
• [math]1 \mid \mid \sum U_{i}[/math]
• [math]1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}[/math]
• [math]1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -[/math]
• [math]1 \mid outtree \mid \sum w_i C_i[/math]
• [math]1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}[/math]
• [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math]
• [math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math]
• [math]P2 \mid prec, p_i = 1 \mid L_{\max}[/math]
• [math]P \mid pmtn, r_i \mid L_{max}[/math]
• [math]Q \mid pmtn \mid C_{max}[/math]
• [math]Q \mid pmtn, r_{i} \mid L_{max}[/math]
• [math]Q\mid\mid\sum{C_i}[/math]
• [math]R2 \mid \mid C_{max}[/math]
• [math]F2 \mid \mid C_{max}[/math]
• [math]F \mid p_{ij} = 1 \mid \sum w_i U_i[/math]
• [math]O2 \mid \mid C_{max}[/math]
• [math]O \mid p_{ij} = 1 \mid \sum U_i[/math]
• [math]J2 \mid n_{i} \le 2 \mid C_{max}[/math]
• [math]J2\mid p_{ij} = 1\mid L_{max}[/math]