1632
правки
Изменения
м
* [[Теорема Поша]]<tex>^\star</tex>
* [[Лемма о паросочетании в графе замен]]* [[Лемма о единственном паросочетании в графе замен]]* [[Граф замен для двух матроидов]]* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
rollbackEdits.php mass rollback
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
== Булевы функции ==
*[[Определение булевой функции]]
*[[Побитовые операции]]<tex>^\star</tex>
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[2-SAT]]
*[[XOR-SAT]]<tex>^\star</tex>
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Триггеры]]<tex>^\star</tex>
*[[Квантовые гейты]]<tex>^\star</tex>
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Алгоритм LZMA]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Монотонный код Грея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>
*[[Convex hull trick]]
=== Другие задачи ===
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Наибольшая общая возрастающая подпоследовательностьЗадача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
* [[Стек]]
* [[Очередь]]
* [[Дек]]
* [[Мажорирующий элемент]]
* [[Счетчик Кнута]]
* [[Мастер-теорема]]<tex>^\star</tex>
* [[List order maintenance]]<tex>^\star</tex>
== Персистентные структуры данных ==
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Взвешенное дерево]]
* [[Tango-дерево]]<tex>^\star</tex>
* [[Рандомизированное бинарное дерево поиска]]
* [[Сверхбыстрый цифровой бор]]
* [[Rope]]<tex>^\star</tex>
* [[AA-дерево]]<tex>^\star</tex>
== Дерево отрезков ==
* [[Статистики на отрезках. Корневая эвристика]]
* [[Корневая декомпозиция с операциями: get, insert, erase]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Сортировка Хана]]<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>
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Теорема Вагнера]]
* [[Род, толщина, крупность, число скрещиваний]]<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>
* [[Алгоритм Shift-And]]<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>
== Матроиды ==
=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Алгоритм построения базы в пересечении матроидов]]
== Теория расписаний ==
=== Общая теория ===
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
=== Задачи с одним станком ===* [[Flow shop1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]* [[P1sumu1sumwu|<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>]]
* [[1ridipi11ripi1sumf|<tex>1 \mid r_{i}r_i, d_{i}, p_{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>]]
* [[J2ni2CmaxOpij1di|<tex>J2 O \mid n_p_{ij} = 1, d_i \mid - </tex>]]* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \le 2 mid \sum w_{i} U_{i} </tex>]]* [[Opij1SumTi|<tex> O \mid p_{i,j} = 1 \mid C_\sum T_{maxi}</tex>]]* [[J2pij1LmaxOpij1Cmax| <tex>J2O \mid p_{ij} = 1\mid L_C_{max}</tex>]]* [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]
