1632
правки
Изменения
м
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Транзитивный остов]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Формула полной вероятности]]
* [[Рандомизированное бинарное дерево поиска]]
* [[Сортировка подсчетом сложных объектов]]
* [[Сортировка кучей]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* Следствия теоремы Хватала: ** [[Теорема Дирака]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Алгоритм A*]]
== Остовные деревья ==* [[Лемма о безопасном ребреАлгоритм Левита]]<tex>^\star</tex>* [[Алгоритм ПримаA*]]<tex>^\star</tex>* [[Алгоритм Краскала]]D* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<tex>^\star</tex>* [[Алгоритм двух китайцевЭвристики для поиска кратчайших путей]]<tex>^\star</tex>
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Автомат для поиска образца в тексте]]
=== Суффиксный массив ===
* [[Алгоритм цифровой сортировки]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Жадный алгоритм поиска базы минимального веса]]
* [[Лемма о паросочетании в графе замен]]* [[Лемма о единственном паросочетании в графе замен]]* [[Граф замен для двух матроидов]]* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Теорема Эдмондса-Лоулера]]=== Объединение матроидов ===
rollbackEdits.php mass rollback
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
= Первый семестр =
== Отношения ==
*[[Определение отношения]]
*[[Степень Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]
== Булевы функции ==
*[[Определение булевой функции]]
*[[Побитовые операции]]<tex>^\star</tex>
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[2-SAT]]*[[XOR-SAT]]<tex>^\star</tex>*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]*[[Полином Жегалкина| Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>
== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
== Представление информации ==
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]* [[Оптимальное хранение словаря в алгоритме Хаффмана]]* [[Алгоритм Хаффмана за O(n)]]*[[Алгоритм LZWХу-Таккера]]<tex>^\star</tex>* [[Неравенство Крафта]]* [[Неравенство Макмиллана]]* [[Код Шеннона]]* [[Оптимальный префиксный код с длиной кодового слова не более 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>
*[[Динамика по поддеревьям]]
== Теория вероятностей ==
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Дисперсия случайной величины]]
*[[Ковариация случайных величин]]
*[[Дисперсия случайной величиныКорреляция случайных величин]]*[[Неравенство Маркова]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Задача о двух конвертахПарадоксы теории вероятностей]]<tex>^\star</tex>*[[Схема Бернулли]]<tex>^\star</tex>
== Марковские цепи ==
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
* [[Примеры использования Марковских цепей]]
* [[Скрытые Марковские модели]]<tex>^\star</tex>
* [[Алгоритм Витерби]]<tex>^\star</tex>
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>
= Второй семестр =
== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Саморасширяющийся Динамический массив]]* [[Массив с увеличениемHashed Array Tree]]<tex>^\star</уменьшением размераtex>* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[СписокДек]]* [[Мажорирующий элемент]]* [[Счетчик Кнута]]* [[Мастер-теорема]]<tex>^\star</tex>* [[List order maintenance]]<tex>^\star</tex> == Персистентные структуры данных ==* [[Персистентные структуры данных]]
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[Персистентная приоритетная очередь]]
== [[Приоритетные очереди ]] ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
* [[Тонкая куча]]
* [[Толстая куча на избыточном счетчике]]
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
== Система непересекающихся множеств ==
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[Анализ реализации СНМ с ранговой эвристикой | Анализ реализации с ранговой эвристикойоперацией удаления за О(1)]]<tex>^\star</tex>
== Деревья поиска [[Поисковые структуры данных]] ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Декартово Взвешенное дерево по неявному ключу]]* [[Tango-дерево]]<tex>^\star</tex>* [[Рандомизированное бинарное дерево поиска]]
* [[Дерево ван Эмде Боаса]]
* [[Список с пропусками]]
* [[Fusion tree]]<tex>^\star</tex>
* [[Сверхбыстрый цифровой бор]]
* [[Rope]]<tex>^\star</tex>
* [[AA-дерево]]<tex>^\star</tex>
== Дерево отрезков ==
* [[Статистики на отрезках. Корневая эвристика]]
* [[Корневая декомпозиция с операциями: get, insert, erase]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
== Хеширование ==
* [[ХешированиеХеш-таблица]]* [[Открытое и закрытое хеширование]]* [[Поиск свободного места при закрытом хешированииРазрешение коллизий]]
* [[Хеширование кукушки]]
* [[Двойное Идеальное хеширование]]* [[Перехеширование. Амортизационный анализ]]
* [[Фильтр Блума]]
* [[Quotient filter]]<tex>^\star</tex>
* [[Универсальное семейство хеш-функций]]
* [[Расширяемое хеширование]]<tex>^\star</tex>
== Сортировка [[Сортировки]] ===== Квадратичные сортировки ===
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
=== Сортировки на сравнениях ===
* [[Сортировка Шелла]]<tex>^\star</tex>
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
* [[Сортировка слиянием]]
* [[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>
* [[Сортировка подсчетом]]
* [[Цифровая сортировка]]
* [[Поиск k-ой порядковой статистикиКарманная сортировка]]* [[Поиск k-й порядковой статистики за линейное времяСортировка Хана]]<tex>^\star</tex>* [[Теорема о нижней оценке для сортировки сравнениямиЗадача флага Нидерландов]]<tex>^\star</tex>* [[Быстрая Блинная сортировка]]<tex>^\star</tex>
== Сортирующие сети ==
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
* [[Сеть Бетчера]]
== Алгоритмы поиска ==
* [[Целочисленный двоичный поиск]]
* [[Поиск в матрице]]<tex>^\star</tex>
* [[Вещественный двоичный поиск]]
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]
* [[Вещественный двоичный поискМетод Фибоначчи]]<tex>^\star</tex> == Связь между структурами данных ==* [[Целочисленный двоичный поискСвязь между структурами данных]]
= Третий семестр =
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Двудольные графы]]
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
* [[Рёберное ядро]]
* [[Факторизация графов]]<tex>^\star</tex>
* [[Группы графов]]<tex>^\star</tex>
* [[Гиперграфы]]<tex>^\star</tex>
== Связность в графах ==
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]
* [[Минимально узкое остовное дерево]]
* [[Остовное дерево в планарном графе]]
=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
== Обходы графов ==
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер рёбер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Оре]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Теорема Вагнера]]
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>
* [[Гамма-алгоритм]]
* [[Разрез в планарных графах]]
== Раскраски графов ==
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>
== Обход в глубину ==
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]
== Задача о паросочетании ==
* [[Теорема Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Рёберное ядро]]<tex>^\star</tex>
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
== Задача о максимальном потоке ==
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении Сложение и разность потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм поиска блокирующего потока в ациклической сетиШтор-Вагнера нахождения минимального разреза]]* [[Алгоритм масштабирования потокаКаргера для нахождения минимального разреза]]<tex>^\star</tex>* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностямиПримеры сведения к задачам поиска потока]]
== Задача о потоке минимальной стоимости ==
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
= Четвертый семестр =
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
* [[Декомпозиция Линдона]]<tex>^\star</tex>
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
* [[Алгоритм Крочемора]]<tex>^\star</tex>
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
* [[Алгоритм Манакера]]<tex>^\star</tex>
* [[Дерево палиндромов]]<tex>^\star</tex>
== [[Поиск подстроки в строке ]] ===== Точный поиск ===
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Автомат Кнута-Морриса-Пратта]]
* [[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 с помощью разреженной таблицы]]
* [[Двумерная разреженная таблица]]* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых четырех русских)* [[Сведение задачи RMQ к задаче Алгоритм Хьюи]]* [[Heavy-light декомпозиция]]* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>* [[Алгоритм Тарьяна поиска LCAза O(1) в оффлайн]]<tex>^\star</tex>* [[Link-Cut Tree]]<tex>^\star</tex>* [[Rake-Compress деревья]]<tex>^\star</tex>
== Матроиды ==
=== Основные факты теории матроидов ===
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Аксиоматизация матроида рангами]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Покрытия, закрытые множества]]
* [[Матроид Вамоса]]<tex>^\star</tex>
=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]
==Теория расписаний===== Общая теория ===
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
=== Задачи с одним станком ===* [[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>]]* [[QpmtnCmax1ridipi1|<tex>Q1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]* [[1pi1sumwu|pmtn<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_{maxi}</tex>]]* [[QpmtnriLmax1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]]* [[1ripipsumwu|<tex>Q1 \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, r_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>]]
