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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Второй семестр)
м (rollbackEdits.php mass rollback)
 
(не показано 186 промежуточных версий 61 участника)
Строка 1: Строка 1:
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
−
 
 
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
 
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
  
Строка 16: Строка 15:
 
*[[Транзитивное отношение]]
 
*[[Транзитивное отношение]]
 
*[[Отношение порядка]]
 
*[[Отношение порядка]]
 +
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
*[[Отношение эквивалентности]]
 
*[[Отношение эквивалентности]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
Строка 23: Строка 23:
 
== Булевы функции ==
 
== Булевы функции ==
 
*[[Определение булевой функции]]
 
*[[Определение булевой функции]]
 +
*[[Побитовые операции]]<tex>^\star</tex>
 
*[[Суперпозиции]]
 
*[[Суперпозиции]]
 
*[[ДНФ]]
 
*[[ДНФ]]
 
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[КНФ]]
 
*[[КНФ]]
 +
*[[2-SAT]]
 +
*[[XOR-SAT]]<tex>^\star</tex>
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
Строка 46: Строка 49:
 
*[[Дерево Уоллеса]]
 
*[[Дерево Уоллеса]]
 
*[[Контактная схема]]
 
*[[Контактная схема]]
 +
*[[Триггеры]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
  
Строка 66: Строка 70:
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZSS]]<tex>^\star</tex>
 
* [[Алгоритм LZSS]]<tex>^\star</tex>
 +
* [[Алгоритм LZMA]]<tex>^\star</tex>
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование MTF]]
 
* [[Преобразование MTF]]
Строка 79: Строка 84:
 
* [[Коды Грея для перестановок]]
 
* [[Коды Грея для перестановок]]
 
* [[Коды антигрея]]
 
* [[Коды антигрея]]
 +
* [[Монотонный код Грея]]
 
* [[Цепные коды]]
 
* [[Цепные коды]]
 
* [[Правильные скобочные последовательности]]
 
* [[Правильные скобочные последовательности]]
Строка 119: Строка 125:
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
Строка 124: Строка 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]]
  
 
=== Другие задачи ===
 
=== Другие задачи ===
Строка 133: Строка 141:
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
−
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
+
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
Строка 150: Строка 158:
 
*[[Ковариация случайных величин]]
 
*[[Ковариация случайных величин]]
 
*[[Корреляция случайных величин]]
 
*[[Корреляция случайных величин]]
 +
*[[Неравенство Маркова]]
 
*[[Энтропия случайного источника]]
 
*[[Энтропия случайного источника]]
 
*[[Симуляция одним распределением другого]]
 
*[[Симуляция одним распределением другого]]
Строка 180: Строка 189:
 
* [[Стек]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Очередь]]
 +
* [[Дек]]
 +
* [[Мажорирующий элемент]]
 +
* [[Счетчик Кнута]]
 +
* [[Мастер-теорема]]<tex>^\star</tex>
 +
* [[List order maintenance]]<tex>^\star</tex>
 +
 +
== Персистентные структуры данных ==
 +
* [[Персистентные структуры данных]]
 
* [[Персистентный стек]]
 
* [[Персистентный стек]]
 
* [[Персистентная очередь]]
 
* [[Персистентная очередь]]
 
* [[Персистентный дек]]
 
* [[Персистентный дек]]
−
* [[Мажорирующий элемент]]
+
* [[Персистентная приоритетная очередь]]
−
* [[Счетчик Кнута]]
 
−
 
 
−
== Приоритетные очереди ==
 
  
 +
== [[Приоритетные очереди]] ==
 
* [[Двоичная куча]]
 
* [[Двоичная куча]]
 
* [[Биномиальная куча]]
 
* [[Биномиальная куча]]
Строка 202: Строка 217:
 
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
 
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
  
−
== Поисковые структуры данных ==
+
== [[Поисковые структуры данных]] ==
 
* [[Упорядоченное множество]]
 
* [[Упорядоченное множество]]
 
* [[Дерево поиска, наивная реализация]]
 
* [[Дерево поиска, наивная реализация]]
Строка 212: Строка 227:
 
* [[Декартово дерево по неявному ключу]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Splay-дерево]]
 
* [[Splay-дерево]]
 +
* [[Взвешенное дерево]]
 
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Дерево ван Эмде Боаса]]
 
* [[Дерево ван Эмде Боаса]]
 
* [[Список с пропусками]]
 
* [[Список с пропусками]]
−
* [[Fusion tree]]
+
* [[Fusion tree]]<tex>^\star</tex>
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Rope]]<tex>^\star</tex>
 
* [[Rope]]<tex>^\star</tex>
 +
* [[AA-дерево]]<tex>^\star</tex>
  
 
== Дерево отрезков ==
 
== Дерево отрезков ==
−
 
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 
* [[Дерево отрезков. Построение]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков сверху]]
Строка 241: Строка 258:
 
* [[Хеширование кукушки]]
 
* [[Хеширование кукушки]]
 
* [[Идеальное хеширование]]
 
* [[Идеальное хеширование]]
−
* [[Перехеширование. Амортизационный анализ]]
+
* [[Перехеширование]]
 
* [[Фильтр Блума]]
 
* [[Фильтр Блума]]
 +
* [[Quotient filter]]<tex>^\star</tex>
 
* [[Универсальное семейство хеш-функций]]
 
* [[Универсальное семейство хеш-функций]]
 +
* [[Расширяемое хеширование]]<tex>^\star</tex>
  
−
== [[Сортировка]] ==
+
== [[Сортировки]] ==
 
=== Квадратичные сортировки ===
 
=== Квадратичные сортировки ===
 
* [[Сортировка выбором]]
 
* [[Сортировка выбором]]
Строка 258: Строка 277:
 
* [[Терпеливая сортировка]]<tex>^\star</tex>
 
* [[Терпеливая сортировка]]<tex>^\star</tex>
 
* [[Timsort]]<tex>^\star</tex>
 
* [[Timsort]]<tex>^\star</tex>
 +
* [[Smoothsort]]<tex>^\star</tex>
 
* [[Теорема о нижней оценке для сортировки сравнениями]]
 
* [[Теорема о нижней оценке для сортировки сравнениями]]
 +
 
=== Многопоточные сортировки ===
 
=== Многопоточные сортировки ===
 
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
 
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
Строка 265: Строка 286:
 
* [[Поиск k-ой порядковой статистики]]
 
* [[Поиск k-ой порядковой статистики]]
 
* [[Поиск k-ой порядковой статистики за линейное время]]
 
* [[Поиск k-ой порядковой статистики за линейное время]]
 +
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом]]
−
* [[Сортировка подсчетом сложных объектов]]
 
 
* [[Цифровая сортировка]]
 
* [[Цифровая сортировка]]
 
* [[Карманная сортировка]]
 
* [[Карманная сортировка]]
 
* [[Сортировка Хана]]<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>
 
* [[Вещественный двоичный поиск]]
 
* [[Вещественный двоичный поиск]]
 
* [[Троичный поиск]]
 
* [[Троичный поиск]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Интерполяционный поиск]]
 
* [[Интерполяционный поиск]]
 +
* [[Метод Фибоначчи]]<tex>^\star</tex>
  
 
== Связь между структурами данных ==
 
== Связь между структурами данных ==
Строка 296: Строка 321:
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Матрица смежности графа]]
 
* [[Матрица смежности графа]]
−
* [[Связь степени матрицы смежности и количества путей]]
 
 
* [[Матрица инцидентности графа]]
 
* [[Матрица инцидентности графа]]
−
* [[Циклическое пространство графа]]
+
* [[Циклическое пространство графа]]<tex>^\star</tex>
−
* [[Фундаментальные циклы графа]]
+
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
 
* [[Дерево, эквивалентные определения]]
 
* [[Дерево, эквивалентные определения]]
−
* [[Алгоритмы на деревьях]]
+
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 +
* [[Двудольные графы]]
 
* [[Дополнительный, самодополнительный граф]]
 
* [[Дополнительный, самодополнительный граф]]
 +
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 +
* [[Рёберное ядро]]
 +
* [[Факторизация графов]]<tex>^\star</tex>
 +
* [[Группы графов]]<tex>^\star</tex>
 +
* [[Гиперграфы]]<tex>^\star</tex>
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 308: Строка 338:
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 +
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Мост, эквивалентные определения]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф блоков-точек сочленения]]
 
* [[Граф блоков-точек сочленения]]
−
* [[Точка сочленения, эквивалентные определения]]
 
−
* [[Мост, эквивалентные определения]]
 
 
* [[k-связность]]
 
* [[k-связность]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
  
 
== Остовные деревья ==
 
== Остовные деревья ==
Строка 325: Строка 356:
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Алгоритм двух китайцев]]
 
* [[Алгоритм двух китайцев]]
 +
* [[Минимально узкое остовное дерево]]
 +
* [[Остовное дерево в планарном графе]]
  
 
=== Свойства остовных деревьев ===
 
=== Свойства остовных деревьев ===
Строка 336: Строка 369:
 
=== Эйлеровы графы ===
 
=== Эйлеровы графы ===
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
−
* [[Покрытие ребер графа путями]]
+
* [[Покрытие рёбер графа путями]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 +
 
=== Гамильтоновы графы ===
 
=== Гамильтоновы графы ===
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
 
* [[Теорема Хватала]]
 
* [[Теорема Хватала]]
−
* [[Теорема Поша]]
 
 
* [[Теорема Дирака]]
 
* [[Теорема Дирака]]
 
* [[Теорема Оре]]
 
* [[Теорема Оре]]
 +
* [[Теорема Поша]]<tex>^\star</tex>
 +
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
 
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
−
* [[Теорема Гринберга]]
+
* [[Теорема Гринберга]]<tex>^\star</tex>
 
* [[Турниры]]
 
* [[Турниры]]
 
* [[Теорема Редеи-Камиона]]
 
* [[Теорема Редеи-Камиона]]
Строка 358: Строка 394:
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Теорема Вагнера]]
 +
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Двойственный граф планарного графа]]
 
* [[Двойственный граф планарного графа]]
−
* [[Теорема Фари]]
+
* [[Теорема Фари]]<tex>^\star</tex>
 +
* [[Гамма-алгоритм]]
 +
* [[Разрез в планарных графах]]
  
 
== Раскраски графов ==
 
== Раскраски графов ==
Строка 368: Строка 408:
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 
* [[Теорема Брукса]]
 
* [[Теорема Брукса]]
−
* [[Верхние и нижние оценки хроматического числа]]
+
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 
* [[Хроматическое число планарного графа]]
 
* [[Хроматическое число планарного графа]]
−
* [[Многочлен Татта]]
+
* [[Многочлен Татта]]<tex>^\star</tex>
−
* [[Теория Рамсея]]
+
* [[Теория Рамсея]]<tex>^\star</tex>
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 389: Строка 429:
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Дейкстры]]
−
* [[Алгоритм Левита]]
 
 
* [[Алгоритм Флойда]]
 
* [[Алгоритм Флойда]]
−
* [[Алгоритм A*]]
 
 
* [[Алгоритм Джонсона]]
 
* [[Алгоритм Джонсона]]
−
* [[Эвристики для поиска кратчайших путей]]
+
* [[Алгоритм Левита]]<tex>^\star</tex>
−
* [[Алгоритм D*]]
+
* [[Алгоритм A*]] <tex>^\star</tex>
 +
* [[Алгоритм D*]] <tex>^\star</tex>
 +
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
  
 
== Задача о паросочетании ==
 
== Задача о паросочетании ==
−
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
+
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
Строка 403: Строка 443:
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь вершинного покрытия и независимого множества]]
 
* [[Связь вершинного покрытия и независимого множества]]
 +
* [[Рёберное ядро]]<tex>^\star</tex>
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Декомпозиция Эдмондса-Галлаи]]
 
* [[Декомпозиция Эдмондса-Галлаи]]
−
* [[Задача об устойчивом паросочетании]]
+
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 +
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 413: Строка 455:
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Дополняющая сеть, дополняющий путь]]
 
* [[Дополняющая сеть, дополняющий путь]]
−
* [[Лемма о сложении потоков]]
+
* [[Сложение и разность потоков]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
Строка 421: Строка 463:
 
* [[Схема алгоритма Диница]]
 
* [[Схема алгоритма Диница]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 +
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Метод проталкивания предпотока]]
 
* [[Метод проталкивания предпотока]]
Строка 427: Строка 470:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
−
* [[Алгоритм Каргера для нахождения минимального разреза]]
+
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 +
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 +
* [[Примеры сведения к задачам поиска потока]]
  
 
== Задача о потоке минимальной стоимости ==
 
== Задача о потоке минимальной стоимости ==
Строка 437: Строка 482:
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
  
 
= Четвертый семестр =
 
= Четвертый семестр =
Строка 445: Строка 491:
 
* [[Слово Фибоначчи]]
 
* [[Слово Фибоначчи]]
 
* [[Слово Туэ-Морса]]
 
* [[Слово Туэ-Морса]]
−
* [[Декомпозиция Линдона]]
+
* [[Декомпозиция Линдона]]<tex>^\star</tex>
−
* [[Алгоритм Ландау-Шмидта]]
+
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
−
* [[Алгоритм Крочемора]]
+
* [[Алгоритм Крочемора]]<tex>^\star</tex>
 +
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 +
* [[Алгоритм Манакера]]<tex>^\star</tex>
 +
* [[Дерево палиндромов]]<tex>^\star</tex>
  
 
== [[Поиск подстроки в строке]] ==
 
== [[Поиск подстроки в строке]] ==
 +
=== Точный поиск ===
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
Строка 455: Строка 505:
 
* [[Префикс-функция]]
 
* [[Префикс-функция]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
−
* [[Алгоритм Бойера-Мура]]
+
* [[Автомат Кнута-Морриса-Пратта]]
−
* [[Алгоритм Колусси]]
 
 
* [[Z-функция]]
 
* [[Z-функция]]
−
* [[Автомат для поиска образца в тексте]]
 
 
* [[Бор]]
 
* [[Бор]]
 
* [[Алгоритм Ахо-Корасик]]
 
* [[Алгоритм Ахо-Корасик]]
−
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]
+
* [[Суффиксный автомат]]
 +
* [[Алгоритм Бойера-Мура]]
 +
* [[Алгоритм Апостолико-Крочемора]]<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>
  
 
== Суффиксное дерево ==
 
== Суффиксное дерево ==
Строка 467: Строка 526:
 
* [[Сжатое суффиксное дерево]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Алгоритм Укконена]]
 
* [[Алгоритм Укконена]]
−
* [[Алгоритм МакКрейта]]
+
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
−
* [[Алгоритм Фарача]]
+
* [[Алгоритм Фарача]]<tex>^\star</tex>
  
 
== Суффиксный массив ==
 
== Суффиксный массив ==
Строка 477: Строка 536:
 
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 +
* [[Количество подпалиндромов в строке]]<tex>^\star</tex>
  
 
== Задача о наименьшем общем предке ==
 
== Задача о наименьшем общем предке ==
 +
* [[Алгоритм Мо]]
 +
* [[Сведение задачи LCA к задаче RMQ]]
 +
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Метод двоичного подъема]]
 
* [[Метод двоичного подъема]]
−
* [[Сведение задачи LCA к задаче RMQ]]
 
 
* [[Решение RMQ с помощью разреженной таблицы]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Двумерная разреженная таблица]]
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
−
* [[Алгоритм Шибера-Вишкина]]
+
* [[Алгоритм Хьюи]]
−
* [[Сведение задачи RMQ к задаче LCA]]
+
* [[Heavy-light декомпозиция]]
−
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]
+
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
−
* [[Link-Cut Tree]]
+
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
 +
* [[Link-Cut Tree]]<tex>^\star</tex>
 +
* [[Rake-Compress деревья]]<tex>^\star</tex>
  
 
== Матроиды ==
 
== Матроиды ==
Строка 499: Строка 564:
 
* [[Аксиоматизация матроида циклами]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Ранговая функция, полумодулярность]]
 +
* [[Аксиоматизация матроида рангами]]
 
* [[Двойственный матроид]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Покрытия, закрытые множества]]
 
* [[Покрытия, закрытые множества]]
−
* [[Матроид Вамоса]]
+
* [[Матроид Вамоса]]<tex>^\star</tex>
 +
 
 
=== Пересечение матроидов ===
 
=== Пересечение матроидов ===
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]
−
* [[Лемма о паросочетании в графе замен]]
+
* [[Граф замен]]
−
* [[Лемма о единственном паросочетании в графе замен]]
 
−
* [[Граф замен для двух матроидов]]
 
−
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
−
* [[Теорема Эдмондса-Лоулера]]
+
 
 
=== Объединение матроидов ===
 
=== Объединение матроидов ===
 
* [[Объединение матроидов, проверка множества на независимость]]
 
* [[Объединение матроидов, проверка множества на независимость]]
Строка 517: Строка 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»