Изменения

Перейти к: навигация, поиск

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

26 537 байт добавлено, 19:43, 4 сентября 2022
м
rollbackEdits.php mass rollback
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]]! Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
= Первый семестр =
== Отношения ==
*[[Определение отношения]]
*[[Степень Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Отношение порядка]]
*[[Изоморфизмы упорядоченных множеств]]<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>* [[Турниры]]* [[Теорема Редеи-Камиона]] == Укладки графов ==* [[Укладка графа на плоскости]]* [[Формула Эйлера]]* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]* [[Укладка дерева]]* [[Укладка графа с планарными компонентами реберной двусвязности]]* [[Укладка графа с планарными компонентами вершинной двусвязности]]* [[Теорема Понтрягина-Куратовского]]* [[Теорема Вагнера]]* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>* [[Двойственный граф планарного графа]]* [[Теорема Фари]]<tex>^\star</tex>* [[Гамма-алгоритм]]* [[Разрез в планарных графах]] == Раскраски графов ==* [[Раскраска графа]]* [[Двудольные графы и раскраска в 2 цвета]]* [[Хроматический многочлен]]* [[Формула Зыкова]]* [[Формула Уитни]]* [[Теорема Брукса]]* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>* [[Хроматическое число планарного графа]]* [[Многочлен Татта]]<tex>^\star</tex>* [[Теория Рамсея]]<tex>^\star</tex> == Обход в глубину ==* [[Обход в глубину, цвета вершин]]* [[Лемма о белых путях]]* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для поиска цикла]]* [[Использование обхода в глубину для топологической сортировки]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент вершинной двусвязности]]* [[Использование обхода в глубину для поиска мостов]]* [[Построение компонент реберной двусвязности]] == Кратчайшие пути в графах ==* [[Обход в ширину]]* [[Алгоритм Форда-Беллмана]]* [[Алгоритм Дейкстры]]* [[Алгоритм Флойда]]* [[Алгоритм Джонсона]]* [[Алгоритм Левита]]<tex>^\star</tex>* [[Алгоритм A*]] <tex>^\star</tex>* [[Алгоритм D*]] <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 с помощью метода четырех русских)* [[Алгоритм Хьюи]]* [[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>]]* [[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>]]
1632
правки

Навигация