Дискретная математика, алгоритмы и структуры данных — различия между версиями
Rukin (обсуждение | вклад) (→Алгоритмы поиска) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 447 промежуточные версии, сделанные более чем 100 участниками) | |||
| Строка 1: | Строка 1: | ||
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
| + | Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]. | ||
| − | + | Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса. | |
= Первый семестр = | = Первый семестр = | ||
| Строка 8: | Строка 9: | ||
== Отношения == | == Отношения == | ||
*[[Определение отношения]] | *[[Определение отношения]] | ||
| − | *[[ | + | *[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]] |
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | *[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | ||
*[[Симметричное отношение]] | *[[Симметричное отношение]] | ||
*[[Антисимметричное отношение]] | *[[Антисимметричное отношение]] | ||
| − | |||
*[[Транзитивное отношение]] | *[[Транзитивное отношение]] | ||
| − | |||
| − | |||
*[[Отношение порядка]] | *[[Отношение порядка]] | ||
| + | *[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex> | ||
*[[Отношение эквивалентности]] | *[[Отношение эквивалентности]] | ||
| + | *[[Транзитивное замыкание|Транзитивное замыкание отношения]] | ||
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | *[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | ||
| + | *[[Транзитивный остов]] | ||
== Булевы функции == | == Булевы функции == | ||
*[[Определение булевой функции]] | *[[Определение булевой функции]] | ||
| + | *[[Побитовые операции]]<tex>^\star</tex> | ||
*[[Суперпозиции]] | *[[Суперпозиции]] | ||
*[[ДНФ]] | *[[ДНФ]] | ||
| + | *[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] | ||
*[[КНФ]] | *[[КНФ]] | ||
| − | *[[Полином Жегалкина]] | + | *[[2-SAT]] |
| + | *[[XOR-SAT]]<tex>^\star</tex> | ||
| + | *[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] | ||
| + | *[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] | ||
*[[Полные системы функций. Теорема Поста о полной системе функций]] | *[[Полные системы функций. Теорема Поста о полной системе функций]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
*[[Представление функции класса DM с помощью медианы]] | *[[Представление функции класса DM с помощью медианы]] | ||
*[[Пороговая функция]] | *[[Пороговая функция]] | ||
| + | *[[Троичная логика]]<tex>^\star</tex> | ||
== Схемы из функциональных элементов == | == Схемы из функциональных элементов == | ||
*[[Реализация булевой функции схемой из функциональных элементов]] | *[[Реализация булевой функции схемой из функциональных элементов]] | ||
| + | *[[Простейшие методы синтеза схем из функциональных элементов]] | ||
| + | *[[Метод Лупанова синтеза схем]] | ||
*[[Cумматор]] | *[[Cумматор]] | ||
*[[Каскадный сумматор]] | *[[Каскадный сумматор]] | ||
*[[Двоичный каскадный сумматор]] | *[[Двоичный каскадный сумматор]] | ||
| + | *[[Троичный сумматор]]<tex>^\star</tex> | ||
*[[Реализация вычитания сумматором]] | *[[Реализация вычитания сумматором]] | ||
*[[Матричный умножитель]] | *[[Матричный умножитель]] | ||
*[[Дерево Уоллеса]] | *[[Дерево Уоллеса]] | ||
| + | *[[Контактная схема]] | ||
| + | *[[Триггеры]]<tex>^\star</tex> | ||
| + | *[[Квантовые гейты]]<tex>^\star</tex> | ||
== Представление информации == | == Представление информации == | ||
| Строка 47: | Строка 56: | ||
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] | *[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] | ||
*[[Представление вещественных чисел]] | *[[Представление вещественных чисел]] | ||
| − | *[[Представление символов, таблицы кодировок]] | + | *[[Представление символов, таблицы кодировок]]<tex>^\star</tex> |
== Алгоритмы сжатия == | == Алгоритмы сжатия == | ||
| − | *[[Алгоритм Хаффмана]] | + | * [[Алгоритм Хаффмана]] |
| − | *[[Алгоритм | + | * [[Оптимальное хранение словаря в алгоритме Хаффмана]] |
| − | *[[Алгоритмы LZ77 и LZ78]] | + | * [[Алгоритм Хаффмана за O(n)]] |
| − | *[[ | + | * [[Алгоритм Ху-Таккера]]<tex>^\star</tex> |
| − | *[[ | + | * [[Неравенство Крафта]] |
| − | *[[Преобразование MTF]] | + | * [[Неравенство Макмиллана]] |
| − | *[[Расстояние Хэмминга]] | + | * [[Код Шеннона]] |
| − | *[[Избыточное кодирование, код Хэмминга]] | + | * [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex> |
| − | *[[ | + | * [[Алгоритмы LZ77 и LZ78]] |
| − | + | * [[Алгоритм LZW]] | |
| + | * [[Алгоритм LZSS]]<tex>^\star</tex> | ||
| + | * [[Алгоритм LZMA]]<tex>^\star</tex> | ||
| + | * [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]] | ||
| + | * [[Преобразование MTF]] | ||
| + | * [[Расстояние Хэмминга]] | ||
| + | * [[Избыточное кодирование, код Хэмминга]] | ||
| + | * [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> | ||
== Комбинаторика == | == Комбинаторика == | ||
| − | *[[Комбинаторные объекты]] | + | === Комбинаторные объекты === |
| − | *[[Лексикографический порядок]] | + | * [[Комбинаторные объекты]] |
| − | *[[ | + | * [[Лексикографический порядок]] |
| − | *[[Генерация комбинаторных объектов в лексикографическом порядке]] | + | * [[Коды Грея]] |
| − | *[[Получение номера по объекту]] | + | * [[Коды Грея для перестановок]] |
| − | *[[Получение объекта по номеру]] | + | * [[Коды антигрея]] |
| − | *[[Получение следующего объекта]] | + | * [[Монотонный код Грея]] |
| − | *[[ | + | * [[Цепные коды]] |
| − | *[[ | + | * [[Правильные скобочные последовательности]] |
| − | *[[ | + | |
| − | *[[ | + | === Генерация комбинаторных объектов === |
| − | *[[ | + | * [[Генерация комбинаторных объектов в лексикографическом порядке]] |
| − | *[[ | + | * [[Получение номера по объекту]] |
| − | *[[ | + | * [[Получение объекта по номеру]] |
| − | *[[Умножение перестановок, обратная перестановка, группа перестановок]] | + | * [[Получение следующего объекта]] |
| − | *[[Теорема Кэли]] | + | * [[Получение предыдущего объекта]]<tex>^\star</tex> |
| − | *[[Матричное представление перестановок]] | + | * [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] |
| − | *[[Задача о минимуме/максимуме скалярного произведения]] | + | * [[Методы генерации случайного сочетания]]<tex>^\star</tex> |
| − | *[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП | + | |
| − | + | === Подсчёт числа объектов === | |
| − | + | * [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] | |
| + | * [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] | ||
| + | * [[Производящая функция]] | ||
| + | * [[Лемма Бёрнсайда и Теорема Пойа]] | ||
| + | * [[Задача об ожерельях]] | ||
| + | * [[Числа Стирлинга первого рода]] | ||
| + | * [[Числа Стирлинга второго рода]] | ||
| + | * [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex> | ||
| + | * [[Числа Каталана]] | ||
| + | |||
| + | === Свойства комбинаторных объектов === | ||
| + | * [[Умножение перестановок, обратная перестановка, группа перестановок]] | ||
| + | * [[Действие перестановки на набор из элементов, представление в виде циклов]] | ||
| + | * [[Таблица инверсий]] | ||
| + | * [[Теорема Кэли]] | ||
| + | * [[Матричное представление перестановок]] | ||
| + | * [[Задача о минимуме/максимуме скалярного произведения]] | ||
| + | * [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] | ||
== [[Динамическое программирование]] == | == [[Динамическое программирование]] == | ||
| + | === Классические задачи динамического программирования === | ||
*[[Кратчайший путь в ациклическом графе]] | *[[Кратчайший путь в ациклическом графе]] | ||
| + | *[[Задача о числе путей в ациклическом графе]] | ||
*[[Задача о расстановке знаков в выражении]] | *[[Задача о расстановке знаков в выражении]] | ||
| + | *[[Задача о порядке перемножения матриц]] | ||
*[[Задача о наибольшей общей подпоследовательности]] | *[[Задача о наибольшей общей подпоследовательности]] | ||
| − | |||
*[[Задача о наибольшей возрастающей подпоследовательности]] | *[[Задача о наибольшей возрастающей подпоследовательности]] | ||
| − | *[[ | + | *[[Быстрый поиск наибольшей возрастающей подпоследовательности]]* |
| − | * | ||
| − | |||
*[[Задача коммивояжера, ДП по подмножествам]] | *[[Задача коммивояжера, ДП по подмножествам]] | ||
| − | |||
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] | *[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] | ||
| − | *[[Задача о | + | *[[Задача о рюкзаке]] |
| + | |||
| + | === Способы оптимизации методов динамического программирования === | ||
| + | *[[Метод четырех русских для умножения матриц]] | ||
| + | *[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex> | ||
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] | *[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] | ||
| + | *[[Meet-in-the-middle]]<tex>^\star</tex> | ||
| + | *[[Convex hull trick]] | ||
| + | |||
| + | === Другие задачи === | ||
| + | *[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex> | ||
| + | *[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] | ||
| + | *[[Задача о наибольшей подпоследовательности-палиндроме]] | ||
| + | *[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex> | ||
| + | *[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex> | ||
| + | *[[Динамическое программирование по профилю]]<tex>^\star</tex> | ||
| + | *[[Динамика по поддеревьям]] | ||
== Теория вероятностей == | == Теория вероятностей == | ||
| Строка 103: | Строка 150: | ||
*[[Независимые события]] | *[[Независимые события]] | ||
*[[Условная вероятность]] | *[[Условная вероятность]] | ||
| + | *[[Формула полной вероятности]] | ||
*[[Формула Байеса]] | *[[Формула Байеса]] | ||
| − | |||
*[[Дискретная случайная величина]] | *[[Дискретная случайная величина]] | ||
*[[Независимые случайные величины]] | *[[Независимые случайные величины]] | ||
*[[Математическое ожидание случайной величины]] | *[[Математическое ожидание случайной величины]] | ||
| + | *[[Дисперсия случайной величины]] | ||
*[[Ковариация случайных величин]] | *[[Ковариация случайных величин]] | ||
| − | *[[ | + | *[[Корреляция случайных величин]] |
| + | *[[Неравенство Маркова]] | ||
*[[Энтропия случайного источника]] | *[[Энтропия случайного источника]] | ||
*[[Симуляция одним распределением другого]] | *[[Симуляция одним распределением другого]] | ||
*[[Арифметическое кодирование]] | *[[Арифметическое кодирование]] | ||
| − | *[[ | + | *[[Парадоксы теории вероятностей]]<tex>^\star</tex> |
| + | *[[Схема Бернулли]]<tex>^\star</tex> | ||
| − | == | + | == Марковские цепи == |
| + | * [[Марковская цепь]] | ||
* [[Теорема о поглощении]] | * [[Теорема о поглощении]] | ||
* [[Фундаментальная матрица]] | * [[Фундаментальная матрица]] | ||
| Строка 123: | Строка 174: | ||
* [[Эргодическая марковская цепь]] | * [[Эргодическая марковская цепь]] | ||
* [[Регулярная марковская цепь]] | * [[Регулярная марковская цепь]] | ||
| + | * [[Примеры использования Марковских цепей]] | ||
| + | * [[Скрытые Марковские модели]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Витерби]]<tex>^\star</tex> | ||
| + | * [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Баума-Велша]]<tex>^\star</tex> | ||
= Второй семестр = | = Второй семестр = | ||
| Строка 128: | Строка 184: | ||
== Амортизационный анализ == | == Амортизационный анализ == | ||
* [[Амортизационный анализ]] | * [[Амортизационный анализ]] | ||
| − | * [[ | + | * [[Динамический массив]] |
| − | * [[ | + | * [[Hashed Array Tree]]<tex>^\star</tex> |
| + | * [[Список]] | ||
* [[Стек]] | * [[Стек]] | ||
* [[Очередь]] | * [[Очередь]] | ||
| − | * [[ | + | * [[Дек]] |
| + | * [[Мажорирующий элемент]] | ||
| + | * [[Счетчик Кнута]] | ||
| + | * [[Мастер-теорема]]<tex>^\star</tex> | ||
| + | * [[List order maintenance]]<tex>^\star</tex> | ||
| + | |||
| + | == Персистентные структуры данных == | ||
| + | * [[Персистентные структуры данных]] | ||
* [[Персистентный стек]] | * [[Персистентный стек]] | ||
| + | * [[Персистентная очередь]] | ||
* [[Персистентный дек]] | * [[Персистентный дек]] | ||
| + | * [[Персистентная приоритетная очередь]] | ||
| − | == Приоритетные очереди == | + | == [[Приоритетные очереди]] == |
| − | |||
* [[Двоичная куча]] | * [[Двоичная куча]] | ||
* [[Биномиальная куча]] | * [[Биномиальная куча]] | ||
* [[Фибоначчиева куча]] | * [[Фибоначчиева куча]] | ||
| + | * [[Левосторонняя куча]] | ||
| + | * [[Тонкая куча]] | ||
| + | * [[Толстая куча на избыточном счетчике]] | ||
| + | * [[Куча Бродала-Окасаки]]<tex>^\star</tex> | ||
== Система непересекающихся множеств == | == Система непересекающихся множеств == | ||
| Строка 146: | Строка 215: | ||
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] | * [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] | ||
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | * [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | ||
| − | * [[ | + | * [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex> |
| − | == | + | == [[Поисковые структуры данных]] == |
* [[Упорядоченное множество]] | * [[Упорядоченное множество]] | ||
* [[Дерево поиска, наивная реализация]] | * [[Дерево поиска, наивная реализация]] | ||
| Строка 156: | Строка 225: | ||
* [[Красно-черное дерево]] | * [[Красно-черное дерево]] | ||
* [[Декартово дерево]] | * [[Декартово дерево]] | ||
| + | * [[Декартово дерево по неявному ключу]] | ||
* [[Splay-дерево]] | * [[Splay-дерево]] | ||
| − | * [[ | + | * [[Взвешенное дерево]] |
| + | * [[Tango-дерево]]<tex>^\star</tex> | ||
| + | * [[Рандомизированное бинарное дерево поиска]] | ||
* [[Дерево ван Эмде Боаса]] | * [[Дерево ван Эмде Боаса]] | ||
| − | * [[ | + | * [[Список с пропусками]] |
| + | * [[Fusion tree]]<tex>^\star</tex> | ||
| + | * [[Сверхбыстрый цифровой бор]] | ||
| + | * [[Rope]]<tex>^\star</tex> | ||
| + | * [[AA-дерево]]<tex>^\star</tex> | ||
== Дерево отрезков == | == Дерево отрезков == | ||
| − | |||
* [[Статистики на отрезках. Корневая эвристика]] | * [[Статистики на отрезках. Корневая эвристика]] | ||
| + | * [[Корневая декомпозиция с операциями: get, insert, erase]] | ||
* [[Дерево отрезков. Построение]] | * [[Дерево отрезков. Построение]] | ||
* [[Реализация запроса в дереве отрезков сверху]] | * [[Реализация запроса в дереве отрезков сверху]] | ||
| Строка 178: | Строка 254: | ||
== Хеширование == | == Хеширование == | ||
| − | * [[ | + | * [[Хеш-таблица]] |
| − | * [[ | + | * [[Разрешение коллизий]] |
| − | |||
* [[Хеширование кукушки]] | * [[Хеширование кукушки]] | ||
| − | * [[ | + | * [[Идеальное хеширование]] |
| − | * [[Перехеширование | + | * [[Перехеширование]] |
* [[Фильтр Блума]] | * [[Фильтр Блума]] | ||
| + | * [[Quotient filter]]<tex>^\star</tex> | ||
* [[Универсальное семейство хеш-функций]] | * [[Универсальное семейство хеш-функций]] | ||
| + | * [[Расширяемое хеширование]]<tex>^\star</tex> | ||
| − | == | + | == [[Сортировки]] == |
| + | === Квадратичные сортировки === | ||
* [[Сортировка выбором]] | * [[Сортировка выбором]] | ||
* [[Сортировка пузырьком]] | * [[Сортировка пузырьком]] | ||
| + | * [[Сортировка вставками]] | ||
| + | === Сортировки на сравнениях === | ||
| + | * [[Сортировка Шелла]]<tex>^\star</tex> | ||
| + | * [[Сортировка кучей]] | ||
| + | * [[Быстрая сортировка]] | ||
* [[Сортировка слиянием]] | * [[Сортировка слиянием]] | ||
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]] | * [[Cортировка слиянием с использованием O(1) дополнительной памяти]] | ||
| − | * [[ | + | * [[Терпеливая сортировка]]<tex>^\star</tex> |
| + | * [[Timsort]]<tex>^\star</tex> | ||
| + | * [[Smoothsort]]<tex>^\star</tex> | ||
| + | * [[Теорема о нижней оценке для сортировки сравнениями]] | ||
| + | |||
| + | === Многопоточные сортировки === | ||
| + | * [[Многопоточная сортировка слиянием]]<tex>^\star</tex> | ||
| + | * [[PSRS-сортировка]]<tex>^\star</tex> | ||
| + | === Другие сортировки === | ||
| + | * [[Поиск k-ой порядковой статистики]] | ||
| + | * [[Поиск k-ой порядковой статистики за линейное время]] | ||
| + | * [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex> | ||
* [[Сортировка подсчетом]] | * [[Сортировка подсчетом]] | ||
| − | |||
* [[Цифровая сортировка]] | * [[Цифровая сортировка]] | ||
| − | * [[ | + | * [[Карманная сортировка]] |
| − | * [[ | + | * [[Сортировка Хана]]<tex>^\star</tex> |
| − | * [[ | + | * [[Задача флага Нидерландов]]<tex>^\star</tex> |
| − | * [[ | + | * [[Блинная сортировка]]<tex>^\star</tex> |
| − | == [[Сортирующие сети]] | + | == Сортирующие сети == |
| + | * [[Сортирующие сети]] | ||
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | * [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | ||
* [[Сортирующие сети для квадратичных сортировок]] | * [[Сортирующие сети для квадратичных сортировок]] | ||
| + | * [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex> | ||
* [[Сеть Бетчера]] | * [[Сеть Бетчера]] | ||
== Алгоритмы поиска == | == Алгоритмы поиска == | ||
| + | * [[Целочисленный двоичный поиск]] | ||
| + | * [[Поиск в матрице]]<tex>^\star</tex> | ||
| + | * [[Вещественный двоичный поиск]] | ||
* [[Троичный поиск]] | * [[Троичный поиск]] | ||
* [[Поиск с помощью золотого сечения]] | * [[Поиск с помощью золотого сечения]] | ||
* [[Интерполяционный поиск]] | * [[Интерполяционный поиск]] | ||
| − | * [[ | + | * [[Метод Фибоначчи]]<tex>^\star</tex> |
| − | * [[ | + | |
| + | == Связь между структурами данных == | ||
| + | * [[Связь между структурами данных]] | ||
= Третий семестр = | = Третий семестр = | ||
| Строка 221: | Строка 321: | ||
* [[Теорема о существовании простого цикла в случае существования цикла]] | * [[Теорема о существовании простого цикла в случае существования цикла]] | ||
* [[Матрица смежности графа]] | * [[Матрица смежности графа]] | ||
| − | |||
* [[Матрица инцидентности графа]] | * [[Матрица инцидентности графа]] | ||
| − | * [[Циклическое пространство графа]] | + | * [[Циклическое пространство графа]]<tex>^\star</tex> |
| − | * [[Фундаментальные циклы графа]] | + | * [[Фундаментальные циклы графа]]<tex>^\star</tex> |
* [[Дерево, эквивалентные определения]] | * [[Дерево, эквивалентные определения]] | ||
| + | * [[Алгоритмы на деревьях]]<tex>^\star</tex> | ||
| + | * [[Двудольные графы]] | ||
| + | * [[Дополнительный, самодополнительный граф]] | ||
| + | * [[Теоретико-множественные операции над графами]]<tex>^\star</tex> | ||
| + | * [[Рёберное ядро]] | ||
| + | * [[Факторизация графов]]<tex>^\star</tex> | ||
| + | * [[Группы графов]]<tex>^\star</tex> | ||
| + | * [[Гиперграфы]]<tex>^\star</tex> | ||
== Связность в графах == | == Связность в графах == | ||
| Строка 231: | Строка 338: | ||
* [[Отношение реберной двусвязности]] | * [[Отношение реберной двусвязности]] | ||
* [[Отношение вершинной двусвязности]] | * [[Отношение вершинной двусвязности]] | ||
| + | * [[Точка сочленения, эквивалентные определения]] | ||
| + | * [[Мост, эквивалентные определения]] | ||
* [[Граф компонент реберной двусвязности]] | * [[Граф компонент реберной двусвязности]] | ||
* [[Граф блоков-точек сочленения]] | * [[Граф блоков-точек сочленения]] | ||
| − | |||
| − | |||
* [[k-связность]] | * [[k-связность]] | ||
* [[Теорема Менгера]] | * [[Теорема Менгера]] | ||
* [[Теорема Менгера, альтернативное доказательство]] | * [[Теорема Менгера, альтернативное доказательство]] | ||
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | * [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | ||
| + | * [[Задача о динамической связности оффлайн]]<tex>^\star</tex> | ||
== Остовные деревья == | == Остовные деревья == | ||
| + | === Построение остовных деревьев === | ||
| + | * [[Остовные деревья: определения, лемма о безопасном ребре]] | ||
| + | * [[Алгоритм Прима]] | ||
| + | * [[Алгоритм Краскала]] | ||
| + | * [[Алгоритм Борувки]] | ||
| + | * [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] | ||
| + | * [[Алгоритм двух китайцев]] | ||
| + | * [[Минимально узкое остовное дерево]] | ||
| + | * [[Остовное дерево в планарном графе]] | ||
| + | |||
| + | === Свойства остовных деревьев === | ||
* [[Матрица Кирхгофа]] | * [[Матрица Кирхгофа]] | ||
* [[Связь матрицы Кирхгофа и матрицы инцидентности]] | * [[Связь матрицы Кирхгофа и матрицы инцидентности]] | ||
| Строка 248: | Строка 367: | ||
== Обходы графов == | == Обходы графов == | ||
| + | === Эйлеровы графы === | ||
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | * [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | ||
| − | * [[Покрытие | + | * [[Покрытие рёбер графа путями]] |
* [[Алгоритм построения Эйлерова цикла]] | * [[Алгоритм построения Эйлерова цикла]] | ||
* [[Произвольно вычерчиваемые из заданной вершины графы]] | * [[Произвольно вычерчиваемые из заданной вершины графы]] | ||
| + | * [[Деревья Эйлерова обхода]]<tex>^\star</tex> | ||
| + | |||
| + | === Гамильтоновы графы === | ||
* [[Гамильтоновы графы]] | * [[Гамильтоновы графы]] | ||
* [[Теорема Хватала]] | * [[Теорема Хватала]] | ||
| − | + | * [[Теорема Дирака]] | |
| − | |||
* [[Теорема Оре]] | * [[Теорема Оре]] | ||
| + | * [[Теорема Поша]]<tex>^\star</tex> | ||
| + | * [[Теорема Гуйя-Ури]]<tex>^\star</tex> | ||
| + | * [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] | ||
| + | * [[Теорема Гринберга]]<tex>^\star</tex> | ||
* [[Турниры]] | * [[Турниры]] | ||
* [[Теорема Редеи-Камиона]] | * [[Теорема Редеи-Камиона]] | ||
| Строка 268: | Строка 394: | ||
* [[Укладка графа с планарными компонентами вершинной двусвязности]] | * [[Укладка графа с планарными компонентами вершинной двусвязности]] | ||
* [[Теорема Понтрягина-Куратовского]] | * [[Теорема Понтрягина-Куратовского]] | ||
| + | * [[Теорема Вагнера]] | ||
| + | * [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex> | ||
* [[Двойственный граф планарного графа]] | * [[Двойственный граф планарного графа]] | ||
| + | * [[Теорема Фари]]<tex>^\star</tex> | ||
| + | * [[Гамма-алгоритм]] | ||
| + | * [[Разрез в планарных графах]] | ||
== Раскраски графов == | == Раскраски графов == | ||
| Строка 274: | Строка 405: | ||
* [[Двудольные графы и раскраска в 2 цвета]] | * [[Двудольные графы и раскраска в 2 цвета]] | ||
* [[Хроматический многочлен]] | * [[Хроматический многочлен]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
* [[Формула Зыкова]] | * [[Формула Зыкова]] | ||
* [[Формула Уитни]] | * [[Формула Уитни]] | ||
| + | * [[Теорема Брукса]] | ||
| + | * [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex> | ||
| + | * [[Хроматическое число планарного графа]] | ||
| + | * [[Многочлен Татта]]<tex>^\star</tex> | ||
| + | * [[Теория Рамсея]]<tex>^\star</tex> | ||
== Обход в глубину == | == Обход в глубину == | ||
| Строка 286: | Строка 417: | ||
* [[Лемма о белых путях]] | * [[Лемма о белых путях]] | ||
* [[Использование обхода в глубину для проверки связности]] | * [[Использование обхода в глубину для проверки связности]] | ||
| − | * [[Использование обхода в глубину для поиска цикла | + | * [[Использование обхода в глубину для поиска цикла]] |
* [[Использование обхода в глубину для топологической сортировки]] | * [[Использование обхода в глубину для топологической сортировки]] | ||
* [[Использование обхода в глубину для поиска компонент сильной связности]] | * [[Использование обхода в глубину для поиска компонент сильной связности]] | ||
| Строка 299: | Строка 430: | ||
* [[Алгоритм Дейкстры]] | * [[Алгоритм Дейкстры]] | ||
* [[Алгоритм Флойда]] | * [[Алгоритм Флойда]] | ||
| − | |||
* [[Алгоритм Джонсона]] | * [[Алгоритм Джонсона]] | ||
| − | + | * [[Алгоритм Левита]]<tex>^\star</tex> | |
| − | + | * [[Алгоритм A*]] <tex>^\star</tex> | |
| − | * [[ | + | * [[Алгоритм D*]] <tex>^\star</tex> |
| − | * [[Алгоритм | + | * [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex> |
| − | * [[Алгоритм | ||
| − | * | ||
| − | * [[ | ||
== Задача о паросочетании == | == Задача о паросочетании == | ||
| − | * [[ | + | * [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] |
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | * [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | ||
* [[Алгоритм Куна для поиска максимального паросочетания]] | * [[Алгоритм Куна для поиска максимального паросочетания]] | ||
| + | * [[Теорема Холла]] | ||
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | * [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | ||
* [[Связь вершинного покрытия и независимого множества]] | * [[Связь вершинного покрытия и независимого множества]] | ||
| + | * [[Рёберное ядро]]<tex>^\star</tex> | ||
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | * [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | ||
| + | * [[Теорема Татта о существовании полного паросочетания]] | ||
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | * [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | ||
| + | * [[Декомпозиция Эдмондса-Галлаи]] | ||
| + | * [[Задача об устойчивом паросочетании]]<tex>^\star</tex> | ||
| + | * [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex> | ||
== Задача о максимальном потоке == | == Задача о максимальном потоке == | ||
| Строка 322: | Строка 455: | ||
* [[Разрез, лемма о потоке через разрез]] | * [[Разрез, лемма о потоке через разрез]] | ||
* [[Дополняющая сеть, дополняющий путь]] | * [[Дополняющая сеть, дополняющий путь]] | ||
| − | * [[ | + | * [[Сложение и разность потоков]] |
* [[Теорема Форда-Фалкерсона]] | * [[Теорема Форда-Фалкерсона]] | ||
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | * [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | ||
* [[Алоритм Эдмондса-Карпа]] | * [[Алоритм Эдмондса-Карпа]] | ||
| + | * [[Алгоритм масштабирования потока]] | ||
| + | * [[Блокирующий поток]] | ||
| + | * [[Схема алгоритма Диница]] | ||
| + | * [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] | ||
| + | * [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex> | ||
| + | * [[Алгоритм поиска блокирующего потока в ациклической сети]] | ||
| + | * [[Метод проталкивания предпотока]] | ||
| + | * [[Алгоритм "поднять-в-начало"]] | ||
* [[Теорема о декомпозиции]] | * [[Теорема о декомпозиции]] | ||
* [[Теорема о декомпозиционном барьере]] | * [[Теорема о декомпозиционном барьере]] | ||
| − | |||
| − | |||
* [[Циркуляция потока]] | * [[Циркуляция потока]] | ||
| − | * [[Алгоритм | + | * [[Алгоритм Штор-Вагнера нахождения минимального разреза]] |
| − | * [[Алгоритм | + | * [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex> |
| − | * [[ | + | * [[Примеры сведения к задачам поиска потока]] |
== Задача о потоке минимальной стоимости == | == Задача о потоке минимальной стоимости == | ||
| Строка 343: | Строка 482: | ||
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] | * [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] | ||
* [[Венгерский алгоритм решения задачи о назначениях]] | * [[Венгерский алгоритм решения задачи о назначениях]] | ||
| + | * [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex> | ||
= Четвертый семестр = | = Четвертый семестр = | ||
| Строка 351: | Строка 491: | ||
* [[Слово Фибоначчи]] | * [[Слово Фибоначчи]] | ||
* [[Слово Туэ-Морса]] | * [[Слово Туэ-Морса]] | ||
| + | * [[Декомпозиция Линдона]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Крочемора]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Манакера]]<tex>^\star</tex> | ||
| + | * [[Дерево палиндромов]]<tex>^\star</tex> | ||
| − | == Поиск подстроки в строке == | + | == [[Поиск подстроки в строке]] == |
| + | === Точный поиск === | ||
* [[Наивный алгоритм поиска подстроки в строке]] | * [[Наивный алгоритм поиска подстроки в строке]] | ||
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]] | * [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]] | ||
| Строка 358: | Строка 505: | ||
* [[Префикс-функция]] | * [[Префикс-функция]] | ||
* [[Алгоритм Кнута-Морриса-Пратта]] | * [[Алгоритм Кнута-Морриса-Пратта]] | ||
| + | * [[Автомат Кнута-Морриса-Пратта]] | ||
* [[Z-функция]] | * [[Z-функция]] | ||
| − | |||
* [[Бор]] | * [[Бор]] | ||
* [[Алгоритм Ахо-Корасик]] | * [[Алгоритм Ахо-Корасик]] | ||
| + | * [[Суффиксный автомат]] | ||
| + | * [[Алгоритм Бойера-Мура]] | ||
| + | * [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Колусси]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Райта]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Shift-And]]<tex>^\star</tex> | ||
| + | * [[Двусторонний алгоритм]]<tex>^\star</tex> | ||
| + | * [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex> | ||
| + | |||
| + | === Нечёткий поиск === | ||
| + | * [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex> | ||
| − | == | + | == Суффиксное дерево == |
* [[Суффиксный бор]] | * [[Суффиксный бор]] | ||
* [[Сжатое суффиксное дерево]] | * [[Сжатое суффиксное дерево]] | ||
* [[Алгоритм Укконена]] | * [[Алгоритм Укконена]] | ||
| + | * [[Алгоритм МакКрейта]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Фарача]]<tex>^\star</tex> | ||
| − | + | == Суффиксный массив == | |
* [[Суффиксный массив]] | * [[Суффиксный массив]] | ||
* [[Построение суффиксного массива с помощью стандартных методов сортировки]] | * [[Построение суффиксного массива с помощью стандартных методов сортировки]] | ||
| − | |||
* [[Алгоритм цифровой сортировки суффиксов циклической строки]] | * [[Алгоритм цифровой сортировки суффиксов циклической строки]] | ||
* [[Алгоритм Касаи и др.]] | * [[Алгоритм Касаи и др.]] | ||
* [[Алгоритм Карккайнена-Сандерса]] | * [[Алгоритм Карккайнена-Сандерса]] | ||
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] | * [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] | ||
| + | * [[Количество подпалиндромов в строке]]<tex>^\star</tex> | ||
== Задача о наименьшем общем предке == | == Задача о наименьшем общем предке == | ||
| + | * [[Алгоритм Мо]] | ||
| + | * [[Сведение задачи LCA к задаче RMQ]] | ||
| + | * [[Сведение задачи RMQ к задаче LCA]] | ||
* [[Метод двоичного подъема]] | * [[Метод двоичного подъема]] | ||
| − | |||
* [[Решение RMQ с помощью разреженной таблицы]] | * [[Решение RMQ с помощью разреженной таблицы]] | ||
| − | * [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода | + | * [[Двумерная разреженная таблица]] |
| − | * [[ | + | * [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских) |
| + | * [[Алгоритм Хьюи]] | ||
| + | * [[Heavy-light декомпозиция]] | ||
| + | * [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex> | ||
| + | * [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> | ||
| + | * [[Link-Cut Tree]]<tex>^\star</tex> | ||
| + | * [[Rake-Compress деревья]]<tex>^\star</tex> | ||
== Матроиды == | == Матроиды == | ||
| + | === Основные факты теории матроидов === | ||
* [[Определение матроида]] | * [[Определение матроида]] | ||
* [[Примеры матроидов]] | * [[Примеры матроидов]] | ||
* [[Прямая сумма матроидов]] | * [[Прямая сумма матроидов]] | ||
* [[Теорема Радо-Эдмондса (жадный алгоритм)]] | * [[Теорема Радо-Эдмондса (жадный алгоритм)]] | ||
| − | |||
* [[Теорема о базах]] | * [[Теорема о базах]] | ||
* [[Аксиоматизация матроида базами]] | * [[Аксиоматизация матроида базами]] | ||
| Строка 395: | Строка 564: | ||
* [[Аксиоматизация матроида циклами]] | * [[Аксиоматизация матроида циклами]] | ||
* [[Ранговая функция, полумодулярность]] | * [[Ранговая функция, полумодулярность]] | ||
| + | * [[Аксиоматизация матроида рангами]] | ||
* [[Двойственный матроид]] | * [[Двойственный матроид]] | ||
* [[Оператор замыкания для матроидов]] | * [[Оператор замыкания для матроидов]] | ||
| + | * [[Покрытия, закрытые множества]] | ||
| + | * [[Матроид Вамоса]]<tex>^\star</tex> | ||
| + | |||
| + | === Пересечение матроидов === | ||
* [[Пересечение матроидов, определение, примеры]] | * [[Пересечение матроидов, определение, примеры]] | ||
| − | + | * [[Граф замен]] | |
| − | |||
| − | * [[Граф замен | ||
| − | |||
* [[Алгоритм построения базы в пересечении матроидов]] | * [[Алгоритм построения базы в пересечении матроидов]] | ||
| − | + | ||
| + | === Объединение матроидов === | ||
* [[Объединение матроидов, проверка множества на независимость]] | * [[Объединение матроидов, проверка множества на независимость]] | ||
* [[Объединение матроидов, доказательство того, что объединение является матроидом]] | * [[Объединение матроидов, доказательство того, что объединение является матроидом]] | ||
* [[Алгоритм построения базы в объединении матроидов]] | * [[Алгоритм построения базы в объединении матроидов]] | ||
| − | ==Теория расписаний== | + | |
| + | == Теория расписаний == | ||
| + | === Общая теория === | ||
* [[Классификация задач]] | * [[Классификация задач]] | ||
* [[Методы решения задач теории расписаний]] | * [[Методы решения задач теории расписаний]] | ||
* [[Правило Лаулера]] | * [[Правило Лаулера]] | ||
| − | * [[QpmtnCmax|<tex>Q | + | |
| − | * [[QpmtnriLmax|<tex>Q | + | === Задачи с одним станком === |
| + | * [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]] | ||
| + | * [[1sumwu|<tex> 1 \mid\mid \sum w_i U_i </tex>]] | ||
| + | * [[1sumwT|<tex> 1 \mid\mid \sum w_i T_i </tex>]] | ||
| + | * [[1p1sumu|<tex>1 \mid p_{i} = 1 \mid \sum U_{i}</tex>]] | ||
| + | * [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]] | ||
| + | * [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]] | ||
| + | * [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]] | ||
| + | * [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]] | ||
| + | * [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]] | ||
| + | * [[1ripippmtnsumwu| <tex> 1 \mid r_i,p_i=p, pmtn \mid \sum w_i U_i</tex>]] | ||
| + | * [[1ripmtnsumwu|<tex>1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex>]] | ||
| + | * [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]] | ||
| + | * [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] | ||
| + | * [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]] | ||
| + | |||
| + | === Специальные случаи задач для двух станков === | ||
| + | * [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]] | ||
| + | * [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]] | ||
| + | * [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] | ||
| + | * [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]] | ||
| + | * [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]] | ||
| + | * [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]] | ||
| + | |||
| + | === Задачи для произвольного числа станков === | ||
| + | * [[Flow shop]] | ||
| + | * [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]] | ||
| + | * [[PSumCi|<tex>P \mid \mid \sum C_{i}</tex>]] | ||
| + | * [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]] | ||
| + | * [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]] | ||
| + | * [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]] | ||
| + | * [[Ppi1riintegerLmax|<tex>P \mid p_i=1; r_i - integer \mid L_{max}</tex>]] | ||
| + | * [[RSumCi|<tex>R \mid \mid \sum C_i</tex>]] | ||
| + | * [[RpmtnCmax|<tex>R \mid pmtn \mid C_{max}</tex>]] | ||
| + | * [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]] | ||
| + | * [[QpmtnSumCi|<tex> Q \mid pmtn \mid \sum C_i </tex>]] | ||
| + | * [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]] | ||
| + | * [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]] | ||
| + | * [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]] | ||
| + | * [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]] | ||
| + | * [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]] | ||
| + | * [[Opij1SumTi|<tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>]] | ||
| + | * [[Opij1Cmax|<tex> O \mid p_{ij} = 1 \mid C_{max} </tex>]] | ||
| + | * [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]] | ||
Текущая версия на 19:43, 4 сентября 2022
Убедительная просьба читать правила оформления вики-конспектов.
Символом помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
Содержание
- 1 Первый семестр
- 2 Второй семестр
- 2.1 Амортизационный анализ
- 2.2 Персистентные структуры данных
- 2.3 Приоритетные очереди
- 2.4 Система непересекающихся множеств
- 2.5 Поисковые структуры данных
- 2.6 Дерево отрезков
- 2.7 Дерево Фенвика
- 2.8 Хеширование
- 2.9 Сортировки
- 2.10 Сортирующие сети
- 2.11 Алгоритмы поиска
- 2.12 Связь между структурами данных
- 3 Третий семестр
- 4 Четвертый семестр
Первый семестр
Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Побитовые операции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 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 деревья
Матроиды
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Аксиоматизация матроида рангами
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- Матроид Вамоса
Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Граф замен
- Алгоритм построения базы в пересечении матроидов
Объединение матроидов
- Объединение матроидов, проверка множества на независимость
- Объединение матроидов, доказательство того, что объединение является матроидом
- Алгоритм построения базы в объединении матроидов
