Дискретная математика, алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Сортирующие сети)
м (rollbackEdits.php mass rollback)
 
(не показано 158 промежуточных версий 55 участников)
Строка 15: Строка 15:
 
*[[Транзитивное отношение]]
 
*[[Транзитивное отношение]]
 
*[[Отношение порядка]]
 
*[[Отношение порядка]]
 +
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
*[[Отношение эквивалентности]]
 
*[[Отношение эквивалентности]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
Строка 22: Строка 23:
 
== Булевы функции ==
 
== Булевы функции ==
 
*[[Определение булевой функции]]
 
*[[Определение булевой функции]]
 +
*[[Побитовые операции]]<tex>^\star</tex>
 
*[[Суперпозиции]]
 
*[[Суперпозиции]]
 
*[[ДНФ]]
 
*[[ДНФ]]
 
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[КНФ]]
 
*[[КНФ]]
 +
*[[2-SAT]]
 +
*[[XOR-SAT]]<tex>^\star</tex>
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
Строка 45: Строка 49:
 
*[[Дерево Уоллеса]]
 
*[[Дерево Уоллеса]]
 
*[[Контактная схема]]
 
*[[Контактная схема]]
 +
*[[Триггеры]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
  
Строка 65: Строка 70:
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZSS]]<tex>^\star</tex>
 
* [[Алгоритм LZSS]]<tex>^\star</tex>
 +
* [[Алгоритм LZMA]]<tex>^\star</tex>
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование MTF]]
 
* [[Преобразование MTF]]
Строка 78: Строка 84:
 
* [[Коды Грея для перестановок]]
 
* [[Коды Грея для перестановок]]
 
* [[Коды антигрея]]
 
* [[Коды антигрея]]
 +
* [[Монотонный код Грея]]
 
* [[Цепные коды]]
 
* [[Цепные коды]]
 
* [[Правильные скобочные последовательности]]
 
* [[Правильные скобочные последовательности]]
Строка 118: Строка 125:
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
Строка 123: Строка 131:
  
 
=== Способы оптимизации методов динамического программирования ===
 
=== Способы оптимизации методов динамического программирования ===
−
*[[Метод четырех русских для умножения матриц]]<tex>^\star</tex>
+
*[[Метод четырех русских для умножения матриц]]
 
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
 
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Meet-in-the-middle]]<tex>^\star</tex>
 
*[[Meet-in-the-middle]]<tex>^\star</tex>
 +
*[[Convex hull trick]]
  
 
=== Другие задачи ===
 
=== Другие задачи ===
Строка 132: Строка 141:
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
−
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
+
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
Строка 180: Строка 189:
 
* [[Стек]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Очередь]]
 +
* [[Дек]]
 
* [[Мажорирующий элемент]]
 
* [[Мажорирующий элемент]]
 
* [[Счетчик Кнута]]
 
* [[Счетчик Кнута]]
 
* [[Мастер-теорема]]<tex>^\star</tex>
 
* [[Мастер-теорема]]<tex>^\star</tex>
 +
* [[List order maintenance]]<tex>^\star</tex>
  
 
== Персистентные структуры данных ==
 
== Персистентные структуры данных ==
Строка 189: Строка 200:
 
* [[Персистентная очередь]]
 
* [[Персистентная очередь]]
 
* [[Персистентный дек]]
 
* [[Персистентный дек]]
 +
* [[Персистентная приоритетная очередь]]
  
−
== Приоритетные очереди ==
+
== [[Приоритетные очереди]] ==
−
 
 
 
* [[Двоичная куча]]
 
* [[Двоичная куча]]
 
* [[Биномиальная куча]]
 
* [[Биномиальная куча]]
Строка 216: Строка 227:
 
* [[Декартово дерево по неявному ключу]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Splay-дерево]]
 
* [[Splay-дерево]]
 +
* [[Взвешенное дерево]]
 
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
Строка 223: Строка 235:
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Rope]]<tex>^\star</tex>
 
* [[Rope]]<tex>^\star</tex>
 +
* [[AA-дерево]]<tex>^\star</tex>
  
 
== Дерево отрезков ==
 
== Дерево отрезков ==
−
 
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 
* [[Дерево отрезков. Построение]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков сверху]]
Строка 247: Строка 260:
 
* [[Перехеширование]]
 
* [[Перехеширование]]
 
* [[Фильтр Блума]]
 
* [[Фильтр Блума]]
 +
* [[Quotient filter]]<tex>^\star</tex>
 
* [[Универсальное семейство хеш-функций]]
 
* [[Универсальное семейство хеш-функций]]
 +
* [[Расширяемое хеширование]]<tex>^\star</tex>
  
−
== [[Сортировка]] ==
+
== [[Сортировки]] ==
 
=== Квадратичные сортировки ===
 
=== Квадратичные сортировки ===
 
* [[Сортировка выбором]]
 
* [[Сортировка выбором]]
Строка 276: Строка 291:
 
* [[Карманная сортировка]]
 
* [[Карманная сортировка]]
 
* [[Сортировка Хана]]<tex>^\star</tex>
 
* [[Сортировка Хана]]<tex>^\star</tex>
 +
* [[Задача флага Нидерландов]]<tex>^\star</tex>
 +
* [[Блинная сортировка]]<tex>^\star</tex>
  
 
== Сортирующие сети ==
 
== Сортирующие сети ==
Строка 283: Строка 300:
 
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 
* [[Сеть Бетчера]]
 
* [[Сеть Бетчера]]
−
* [[Сортирующая сеть за <tex>O (\log_2 N)</tex>]]
 
  
 
== Алгоритмы поиска ==
 
== Алгоритмы поиска ==
 
* [[Целочисленный двоичный поиск]]
 
* [[Целочисленный двоичный поиск]]
 +
* [[Поиск в матрице]]<tex>^\star</tex>
 
* [[Вещественный двоичный поиск]]
 
* [[Вещественный двоичный поиск]]
 
* [[Троичный поиск]]
 
* [[Троичный поиск]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Интерполяционный поиск]]
 
* [[Интерполяционный поиск]]
 +
* [[Метод Фибоначчи]]<tex>^\star</tex>
  
 
== Связь между структурами данных ==
 
== Связь между структурами данных ==
Строка 303: Строка 321:
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Матрица смежности графа]]
 
* [[Матрица смежности графа]]
−
* [[Связь степени матрицы смежности и количества путей]]
 
 
* [[Матрица инцидентности графа]]
 
* [[Матрица инцидентности графа]]
 
* [[Циклическое пространство графа]]<tex>^\star</tex>
 
* [[Циклическое пространство графа]]<tex>^\star</tex>
Строка 309: Строка 326:
 
* [[Дерево, эквивалентные определения]]
 
* [[Дерево, эквивалентные определения]]
 
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 +
* [[Двудольные графы]]
 
* [[Дополнительный, самодополнительный граф]]
 
* [[Дополнительный, самодополнительный граф]]
 
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 +
* [[Рёберное ядро]]
 +
* [[Факторизация графов]]<tex>^\star</tex>
 +
* [[Группы графов]]<tex>^\star</tex>
 +
* [[Гиперграфы]]<tex>^\star</tex>
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 316: Строка 338:
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 +
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Мост, эквивалентные определения]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф блоков-точек сочленения]]
 
* [[Граф блоков-точек сочленения]]
−
* [[Точка сочленения, эквивалентные определения]]
 
−
* [[Мост, эквивалентные определения]]
 
 
* [[k-связность]]
 
* [[k-связность]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
  
 
== Остовные деревья ==
 
== Остовные деревья ==
Строка 333: Строка 356:
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Алгоритм двух китайцев]]
 
* [[Алгоритм двух китайцев]]
 +
* [[Минимально узкое остовное дерево]]
 +
* [[Остовное дерево в планарном графе]]
  
 
=== Свойства остовных деревьев ===
 
=== Свойства остовных деревьев ===
Строка 344: Строка 369:
 
=== Эйлеровы графы ===
 
=== Эйлеровы графы ===
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
−
* [[Покрытие ребер графа путями]]
+
* [[Покрытие рёбер графа путями]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 +
 
=== Гамильтоновы графы ===
 
=== Гамильтоновы графы ===
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
 
* [[Теорема Хватала]]
 
* [[Теорема Хватала]]
−
* [[Теорема Поша]]<tex>^\star</tex>
 
 
* [[Теорема Дирака]]
 
* [[Теорема Дирака]]
 
* [[Теорема Оре]]
 
* [[Теорема Оре]]
 +
* [[Теорема Поша]]<tex>^\star</tex>
 +
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
 
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 
* [[Теорема Гринберга]]<tex>^\star</tex>
 
* [[Теорема Гринберга]]<tex>^\star</tex>
Строка 366: Строка 394:
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Теорема Вагнера]]
 +
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Двойственный граф планарного графа]]
 
* [[Двойственный граф планарного графа]]
 
* [[Теорема Фари]]<tex>^\star</tex>
 
* [[Теорема Фари]]<tex>^\star</tex>
 +
* [[Гамма-алгоритм]]
 +
* [[Разрез в планарных графах]]
  
 
== Раскраски графов ==
 
== Раскраски графов ==
Строка 397: Строка 429:
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Дейкстры]]
 +
* [[Алгоритм Флойда]]
 +
* [[Алгоритм Джонсона]]
 
* [[Алгоритм Левита]]<tex>^\star</tex>
 
* [[Алгоритм Левита]]<tex>^\star</tex>
−
* [[Алгоритм Флойда]]
 
 
* [[Алгоритм A*]] <tex>^\star</tex>
 
* [[Алгоритм A*]] <tex>^\star</tex>
−
* [[Алгоритм Джонсона]]
+
* [[Алгоритм D*]] <tex>^\star</tex>
 
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
 
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
−
* [[Алгоритм D*]] <tex>^\star</tex>
 
  
 
== Задача о паросочетании ==
 
== Задача о паросочетании ==
Строка 411: Строка 443:
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь вершинного покрытия и независимого множества]]
 
* [[Связь вершинного покрытия и независимого множества]]
 +
* [[Рёберное ядро]]<tex>^\star</tex>
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
Строка 416: Строка 449:
 
* [[Декомпозиция Эдмондса-Галлаи]]
 
* [[Декомпозиция Эдмондса-Галлаи]]
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 +
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 421: Строка 455:
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Дополняющая сеть, дополняющий путь]]
 
* [[Дополняющая сеть, дополняющий путь]]
−
* [[Лемма о сложении потоков]]
+
* [[Сложение и разность потоков]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
Строка 429: Строка 463:
 
* [[Схема алгоритма Диница]]
 
* [[Схема алгоритма Диница]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 +
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Метод проталкивания предпотока]]
 
* [[Метод проталкивания предпотока]]
Строка 435: Строка 470:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
 +
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 +
* [[Примеры сведения к задачам поиска потока]]
  
 
== Задача о потоке минимальной стоимости ==
 
== Задача о потоке минимальной стоимости ==
Строка 445: Строка 482:
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
  
 
= Четвертый семестр =
 
= Четвертый семестр =
Строка 457: Строка 495:
 
* [[Алгоритм Крочемора]]<tex>^\star</tex>
 
* [[Алгоритм Крочемора]]<tex>^\star</tex>
 
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 +
* [[Алгоритм Манакера]]<tex>^\star</tex>
 +
* [[Дерево палиндромов]]<tex>^\star</tex>
  
 
== [[Поиск подстроки в строке]] ==
 
== [[Поиск подстроки в строке]] ==
 +
=== Точный поиск ===
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
Строка 464: Строка 505:
 
* [[Префикс-функция]]
 
* [[Префикс-функция]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
 +
* [[Автомат Кнута-Морриса-Пратта]]
 +
* [[Z-функция]]
 +
* [[Бор]]
 +
* [[Алгоритм Ахо-Корасик]]
 +
* [[Суффиксный автомат]]
 
* [[Алгоритм Бойера-Мура]]
 
* [[Алгоритм Бойера-Мура]]
 +
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex>
 
* [[Алгоритм Колусси]]<tex>^\star</tex>
 
* [[Алгоритм Колусси]]<tex>^\star</tex>
 +
* [[Алгоритм Райта]]<tex>^\star</tex>
 
* [[Алгоритм Shift-And]]<tex>^\star</tex>
 
* [[Алгоритм Shift-And]]<tex>^\star</tex>
−
* [[Z-функция]]
+
* [[Двусторонний алгоритм]]<tex>^\star</tex>
−
* [[Автомат для поиска образца в тексте]]
+
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex>
−
* [[Бор]]
+
 
−
* [[Алгоритм Ахо-Корасик]]
+
=== Нечёткий поиск ===
 
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex>
 
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex>
 +
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex>
  
 
== Суффиксное дерево ==
 
== Суффиксное дерево ==
Строка 487: Строка 536:
 
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 +
* [[Количество подпалиндромов в строке]]<tex>^\star</tex>
  
 
== Задача о наименьшем общем предке ==
 
== Задача о наименьшем общем предке ==
 +
* [[Алгоритм Мо]]
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Метод двоичного подъема]]
 
* [[Метод двоичного подъема]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Двумерная разреженная таблица]]
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 +
* [[Алгоритм Хьюи]]
 +
* [[Heavy-light декомпозиция]]
 
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
 
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
 
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
 
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
 
* [[Link-Cut Tree]]<tex>^\star</tex>
 
* [[Link-Cut Tree]]<tex>^\star</tex>
 +
* [[Rake-Compress деревья]]<tex>^\star</tex>
  
 
== Матроиды ==
 
== Матроиды ==
Строка 509: Строка 564:
 
* [[Аксиоматизация матроида циклами]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Ранговая функция, полумодулярность]]
 +
* [[Аксиоматизация матроида рангами]]
 
* [[Двойственный матроид]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Покрытия, закрытые множества]]
 
* [[Покрытия, закрытые множества]]
 
* [[Матроид Вамоса]]<tex>^\star</tex>
 
* [[Матроид Вамоса]]<tex>^\star</tex>
 +
 
=== Пересечение матроидов ===
 
=== Пересечение матроидов ===
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]
−
* [[Лемма о паросочетании в графе замен]]
+
* [[Граф замен]]
−
* [[Лемма о единственном паросочетании в графе замен]]
 
−
* [[Граф замен для двух матроидов]]
 
−
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
−
* [[Теорема Эдмондса-Лоулера]]
+
 
 
=== Объединение матроидов ===
 
=== Объединение матроидов ===
 
* [[Объединение матроидов, проверка множества на независимость]]
 
* [[Объединение матроидов, проверка множества на независимость]]
Строка 527: Строка 581:
  
 
== Теория расписаний ==
 
== Теория расписаний ==
 +
=== Общая теория ===
 
* [[Классификация задач]]
 
* [[Классификация задач]]
 
* [[Методы решения задач теории расписаний]]
 
* [[Методы решения задач теории расписаний]]
 
* [[Правило Лаулера]]
 
* [[Правило Лаулера]]
−
* [[Flow shop]]
+
 
−
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</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>]]
 
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
−
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</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>]]
 
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
−
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
 
 
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</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>]]
 
* [[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>]]
 
* [[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>]]
 
* [[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>]]
 
* [[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>]]
 
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
 
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
 
* [[QSumCi|<tex>Q\mid\mid\sum{C_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>]]
 
 
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
 
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
−
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
+
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]
−
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</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

Убедительная просьба читать правила оформления вики-конспектов.

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Содержание

Первый семестр

Отношения

Булевы функции

Схемы из функциональных элементов

Представление информации

Алгоритмы сжатия

Комбинаторика

Комбинаторные объекты

Генерация комбинаторных объектов

Подсчёт числа объектов

Свойства комбинаторных объектов

Динамическое программирование

Классические задачи динамического программирования

Способы оптимизации методов динамического программирования

Другие задачи

Теория вероятностей

Марковские цепи

Второй семестр

Амортизационный анализ

Персистентные структуры данных

Приоритетные очереди

Система непересекающихся множеств

Поисковые структуры данных

Дерево отрезков

Дерево Фенвика

Хеширование

Сортировки

Квадратичные сортировки

Сортировки на сравнениях

Многопоточные сортировки

Другие сортировки

Сортирующие сети

Алгоритмы поиска

Связь между структурами данных

Третий семестр

Основные определения теории графов

Связность в графах

Остовные деревья

Построение остовных деревьев

Свойства остовных деревьев

Обходы графов

Эйлеровы графы

Гамильтоновы графы

Укладки графов

Раскраски графов

Обход в глубину

Кратчайшие пути в графах

Задача о паросочетании

Задача о максимальном потоке

Задача о потоке минимальной стоимости

Четвертый семестр

Основные определения. Простые комбинаторные свойства слов

Поиск подстроки в строке

Точный поиск

Нечёткий поиск

Суффиксное дерево

Суффиксный массив

Задача о наименьшем общем предке

Матроиды

Основные факты теории матроидов

Пересечение матроидов

Объединение матроидов

Теория расписаний

Общая теория

Задачи с одним станком

Специальные случаи задач для двух станков

Задачи для произвольного числа станков

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика,_алгоритмы_и_структуры_данных&oldid=85910»