Дискретная математика, алгоритмы и структуры данных — различия между версиями
Noobgam (обсуждение | вклад) (→Дерево отрезков) |
м (rollbackEdits.php mass rollback) |
||
(не показано 13 промежуточных версий 11 участников) | |||
Строка 135: | Строка 135: | ||
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] | *[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] | ||
*[[Meet-in-the-middle]]<tex>^\star</tex> | *[[Meet-in-the-middle]]<tex>^\star</tex> | ||
+ | *[[Convex hull trick]] | ||
=== Другие задачи === | === Другие задачи === | ||
Строка 237: | Строка 238: | ||
== Дерево отрезков == | == Дерево отрезков == | ||
− | |||
* [[Статистики на отрезках. Корневая эвристика]] | * [[Статистики на отрезках. Корневая эвристика]] | ||
+ | * [[Корневая декомпозиция с операциями: get, insert, erase]] | ||
* [[Дерево отрезков. Построение]] | * [[Дерево отрезков. Построение]] | ||
* [[Реализация запроса в дереве отрезков сверху]] | * [[Реализация запроса в дереве отрезков сверху]] | ||
Строка 345: | Строка 346: | ||
* [[Теорема Менгера, альтернативное доказательство]] | * [[Теорема Менгера, альтернативное доказательство]] | ||
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | * [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | ||
+ | * [[Задача о динамической связности оффлайн]]<tex>^\star</tex> | ||
== Остовные деревья == | == Остовные деревья == | ||
Строка 367: | Строка 369: | ||
=== Эйлеровы графы === | === Эйлеровы графы === | ||
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | * [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | ||
− | * [[Покрытие | + | * [[Покрытие рёбер графа путями]] |
* [[Алгоритм построения Эйлерова цикла]] | * [[Алгоритм построения Эйлерова цикла]] | ||
* [[Произвольно вычерчиваемые из заданной вершины графы]] | * [[Произвольно вычерчиваемые из заданной вершины графы]] | ||
Строка 468: | Строка 470: | ||
* [[Теорема о декомпозиционном барьере]] | * [[Теорема о декомпозиционном барьере]] | ||
* [[Циркуляция потока]] | * [[Циркуляция потока]] | ||
+ | * [[Алгоритм Штор-Вагнера нахождения минимального разреза]] | ||
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex> | * [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex> | ||
* [[Примеры сведения к задачам поиска потока]] | * [[Примеры сведения к задачам поиска потока]] | ||
Строка 536: | Строка 539: | ||
== Задача о наименьшем общем предке == | == Задача о наименьшем общем предке == | ||
+ | * [[Алгоритм Мо]] | ||
* [[Сведение задачи LCA к задаче RMQ]] | * [[Сведение задачи LCA к задаче RMQ]] | ||
* [[Сведение задачи RMQ к задаче LCA]] | * [[Сведение задачи RMQ к задаче LCA]] | ||
* [[Метод двоичного подъема]] | * [[Метод двоичного подъема]] | ||
* [[Решение RMQ с помощью разреженной таблицы]] | * [[Решение RMQ с помощью разреженной таблицы]] | ||
+ | * [[Двумерная разреженная таблица]] | ||
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских) | * [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских) | ||
* [[Алгоритм Хьюи]] | * [[Алгоритм Хьюи]] |
Текущая версия на 19:43, 4 сентября 2022
Убедительная просьба читать правила оформления вики-конспектов.
Символом
помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.Первый семестр
Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Побитовые операции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Пороговая функция
- Троичная логика
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Метод Лупанова синтеза схем
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Триггеры
- Квантовые гейты
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Динамическое программирование
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Быстрый поиск наибольшей возрастающей подпоследовательности*
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о рюкзаке
Способы оптимизации методов динамического программирования
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Meet-in-the-middle
- Convex hull trick
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Задача о наибольшей общей возрастающей последовательности
- Задача о наибольшей общей палиндромной подпоследовательности
- Динамическое программирование по профилю
- Динамика по поддеревьям
Теория вероятностей
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула полной вероятности
- Формула Байеса
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины
- Дисперсия случайной величины
- Ковариация случайных величин
- Корреляция случайных величин
- Неравенство Маркова
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Парадоксы теории вероятностей
- Схема Бернулли
Марковские цепи
- Марковская цепь
- Теорема о поглощении
- Фундаментальная матрица
- Математическое ожидание времени поглощения
- Расчет вероятности поглощения в состоянии
- Эргодическая марковская цепь
- Регулярная марковская цепь
- Примеры использования Марковских цепей
- Скрытые Марковские модели
- Алгоритм Витерби
- Алгоритм "Вперед-Назад"
- Алгоритм Баума-Велша
Второй семестр
Амортизационный анализ
- Амортизационный анализ
- Динамический массив
- Hashed Array Tree
- Список
- Стек
- Очередь
- Дек
- Мажорирующий элемент
- Счетчик Кнута
- Мастер-теорема
- List order maintenance
Персистентные структуры данных
- Персистентные структуры данных
- Персистентный стек
- Персистентная очередь
- Персистентный дек
- Персистентная приоритетная очередь
Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- Фибоначчиева куча
- Левосторонняя куча
- Тонкая куча
- Толстая куча на избыточном счетчике
- Куча Бродала-Окасаки
Система непересекающихся множеств
- Наивные реализации
- Списки с весовой эвристикой
- Реализация с помощью леса корневых деревьев
- СНМ с операцией удаления за О(1)
Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Декартово дерево по неявному ключу
- Splay-дерево
- Взвешенное дерево
- Tango-дерево
- Рандомизированное бинарное дерево поиска
- Дерево ван Эмде Боаса
- Список с пропусками
- Fusion tree
- Сверхбыстрый цифровой бор
- Rope
- AA-дерево
Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Корневая декомпозиция с операциями: get, insert, erase
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
Хеширование
- Хеш-таблица
- Разрешение коллизий
- Хеширование кукушки
- Идеальное хеширование
- Перехеширование
- Фильтр Блума
- Quotient filter
- Универсальное семейство хеш-функций
- Расширяемое хеширование
Сортировки
Квадратичные сортировки
Сортировки на сравнениях
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Терпеливая сортировка
- Timsort
- Smoothsort
- Теорема о нижней оценке для сортировки сравнениями
Многопоточные сортировки
Другие сортировки
- Поиск k-ой порядковой статистики
- Поиск k-ой порядковой статистики за линейное время
- Поиск k-ой порядковой статистики в двух массивах
- Сортировка подсчетом
- Цифровая сортировка
- Карманная сортировка
- Сортировка Хана
- Задача флага Нидерландов
- Блинная сортировка
Сортирующие сети
- Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортирующие сети для квадратичных сортировок
- Сортировочные сети с особыми свойствами
- Сеть Бетчера
Алгоритмы поиска
- Целочисленный двоичный поиск
- Поиск в матрице
- Вещественный двоичный поиск
- Троичный поиск
- Поиск с помощью золотого сечения
- Интерполяционный поиск
- Метод Фибоначчи
Связь между структурами данных
Третий семестр
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
- Алгоритмы на деревьях
- Двудольные графы
- Дополнительный, самодополнительный граф
- Теоретико-множественные операции над графами
- Рёберное ядро
- Факторизация графов
- Группы графов
- Гиперграфы
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
- Задача о динамической связности оффлайн
Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
- Минимально узкое остовное дерево
- Остовное дерево в планарном графе
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие рёбер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Деревья Эйлерова обхода
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Теорема Гринберга
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Теорема Вагнера
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
- Разрез в планарных графах
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
- Хроматическое число планарного графа
- Многочлен Татта
- Теория Рамсея
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
Задача о паросочетании
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Рёберное ядро
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
- Декомпозиция Эдмондса-Галлаи
- Задача об устойчивом паросочетании
- Совершенное паросочетание в кубическом графе
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Сложение и разность потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Алгоритм масштабирования потока
- Блокирующий поток
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм Голдберга-Тарьяна
- Алгоритм поиска блокирующего потока в ациклической сети
- Метод проталкивания предпотока
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Штор-Вагнера нахождения минимального разреза
- Алгоритм Каргера для нахождения минимального разреза
- Примеры сведения к задачам поиска потока
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
- Алгоритм отмены цикла минимального среднего веса
Четвертый семестр
Основные определения. Простые комбинаторные свойства слов
- Основные определения, связанные со строками
- Период и бордер, их связь
- Слово Фибоначчи
- Слово Туэ-Морса
- Декомпозиция Линдона
- Алгоритм Ландау-Шмидта
- Алгоритм Крочемора
- Алгоритм Мейна-Лоренца
- Алгоритм Манакера
- Дерево палиндромов
Поиск подстроки в строке
Точный поиск
- Наивный алгоритм поиска подстроки в строке
- Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
- Префикс-функция
- Алгоритм Кнута-Морриса-Пратта
- Автомат Кнута-Морриса-Пратта
- Z-функция
- Бор
- Алгоритм Ахо-Корасик
- Суффиксный автомат
- Алгоритм Бойера-Мура
- Алгоритм Апостолико-Крочемора
- Алгоритм Колусси
- Алгоритм Райта
- Алгоритм Shift-And
- Двусторонний алгоритм
- Турбо-алгоритм Бойера-Мура
Нечёткий поиск
Суффиксное дерево
Суффиксный массив
- Суффиксный массив
- Построение суффиксного массива с помощью стандартных методов сортировки
- Алгоритм цифровой сортировки суффиксов циклической строки
- Алгоритм Касаи и др.
- Алгоритм Карккайнена-Сандерса
- Алгоритм поиска подстроки в строке с помощью суффиксного массива
- Количество подпалиндромов в строке
Задача о наименьшем общем предке
- Алгоритм Мо
- Сведение задачи LCA к задаче RMQ
- Сведение задачи RMQ к задаче LCA
- Метод двоичного подъема
- Решение RMQ с помощью разреженной таблицы
- Двумерная разреженная таблица
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
- Алгоритм Хьюи
- Heavy-light декомпозиция
- Алгоритм Шибера-Вишкина
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
- Link-Cut Tree
- Rake-Compress деревья
Матроиды
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Аксиоматизация матроида рангами
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- Матроид Вамоса
Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Граф замен
- Алгоритм построения базы в пересечении матроидов
Объединение матроидов
- Объединение матроидов, проверка множества на независимость
- Объединение матроидов, доказательство того, что объединение является матроидом
- Алгоритм построения базы в объединении матроидов