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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Задачи для произвольного числа станков)
м (rollbackEdits.php mass rollback)
 
(не показано 67 промежуточных версий 38 участников)
Строка 15: Строка 15:
 
*[[Транзитивное отношение]]
 
*[[Транзитивное отношение]]
 
*[[Отношение порядка]]
 
*[[Отношение порядка]]
 +
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
*[[Отношение эквивалентности]]
 
*[[Отношение эквивалентности]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
Строка 28: Строка 29:
 
*[[КНФ]]
 
*[[КНФ]]
 
*[[2-SAT]]
 
*[[2-SAT]]
 +
*[[XOR-SAT]]<tex>^\star</tex>
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
Строка 68: Строка 70:
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZSS]]<tex>^\star</tex>
 
* [[Алгоритм LZSS]]<tex>^\star</tex>
 +
* [[Алгоритм LZMA]]<tex>^\star</tex>
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование MTF]]
 
* [[Преобразование MTF]]
Строка 81: Строка 84:
 
* [[Коды Грея для перестановок]]
 
* [[Коды Грея для перестановок]]
 
* [[Коды антигрея]]
 
* [[Коды антигрея]]
 +
* [[Монотонный код Грея]]
 
* [[Цепные коды]]
 
* [[Цепные коды]]
 
* [[Правильные скобочные последовательности]]
 
* [[Правильные скобочные последовательности]]
Строка 121: Строка 125:
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
Строка 130: Строка 135:
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Meet-in-the-middle]]<tex>^\star</tex>
 
*[[Meet-in-the-middle]]<tex>^\star</tex>
 +
*[[Convex hull trick]]
  
 
=== Другие задачи ===
 
=== Другие задачи ===
Строка 135: Строка 141:
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
−
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
+
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
Строка 221: Строка 227:
 
* [[Декартово дерево по неявному ключу]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Splay-дерево]]
 
* [[Splay-дерево]]
 +
* [[Взвешенное дерево]]
 
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
Строка 228: Строка 235:
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Rope]]<tex>^\star</tex>
 
* [[Rope]]<tex>^\star</tex>
 +
* [[AA-дерево]]<tex>^\star</tex>
  
 
== Дерево отрезков ==
 
== Дерево отрезков ==
−
 
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 
* [[Дерево отрезков. Построение]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков сверху]]
Строка 318: Строка 326:
 
* [[Дерево, эквивалентные определения]]
 
* [[Дерево, эквивалентные определения]]
 
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 +
* [[Двудольные графы]]
 
* [[Дополнительный, самодополнительный граф]]
 
* [[Дополнительный, самодополнительный граф]]
 
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 
* [[Рёберное ядро]]
 
* [[Рёберное ядро]]
 
* [[Факторизация графов]]<tex>^\star</tex>
 
* [[Факторизация графов]]<tex>^\star</tex>
 +
* [[Группы графов]]<tex>^\star</tex>
 +
* [[Гиперграфы]]<tex>^\star</tex>
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 335: Строка 346:
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
  
 
== Остовные деревья ==
 
== Остовные деревья ==
Строка 344: Строка 356:
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Алгоритм двух китайцев]]
 
* [[Алгоритм двух китайцев]]
 +
* [[Минимально узкое остовное дерево]]
 +
* [[Остовное дерево в планарном графе]]
  
 
=== Свойства остовных деревьев ===
 
=== Свойства остовных деревьев ===
Строка 355: Строка 369:
 
=== Эйлеровы графы ===
 
=== Эйлеровы графы ===
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
−
* [[Покрытие ребер графа путями]]
+
* [[Покрытие рёбер графа путями]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 +
 
=== Гамильтоновы графы ===
 
=== Гамильтоновы графы ===
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
Строка 378: Строка 394:
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Теорема Вагнера]]
 
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Двойственный граф планарного графа]]
 
* [[Двойственный граф планарного графа]]
 
* [[Теорема Фари]]<tex>^\star</tex>
 
* [[Теорема Фари]]<tex>^\star</tex>
 
* [[Гамма-алгоритм]]
 
* [[Гамма-алгоритм]]
 +
* [[Разрез в планарных графах]]
  
 
== Раскраски графов ==
 
== Раскраски графов ==
Строка 452: Строка 470:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
 +
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 +
* [[Примеры сведения к задачам поиска потока]]
  
 
== Задача о потоке минимальной стоимости ==
 
== Задача о потоке минимальной стоимости ==
Строка 462: Строка 482:
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
  
 
= Четвертый семестр =
 
= Четвертый семестр =
Строка 475: Строка 496:
 
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 
* [[Алгоритм Манакера]]<tex>^\star</tex>
 
* [[Алгоритм Манакера]]<tex>^\star</tex>
 +
* [[Дерево палиндромов]]<tex>^\star</tex>
  
 
== [[Поиск подстроки в строке]] ==
 
== [[Поиск подстроки в строке]] ==
Строка 517: Строка 539:
  
 
== Задача о наименьшем общем предке ==
 
== Задача о наименьшем общем предке ==
 +
* [[Алгоритм Мо]]
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи LCA к задаче RMQ]]
 
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Метод двоичного подъема]]
 
* [[Метод двоичного подъема]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Двумерная разреженная таблица]]
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 
* [[Алгоритм Хьюи]]
 
* [[Алгоритм Хьюи]]
Строка 563: Строка 587:
  
 
=== Задачи с одним станком ===
 
=== Задачи с одним станком ===
−
* [[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>]]
 
* [[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>]]
−
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</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>]]
  
Строка 584: Строка 613:
 
* [[Flow shop]]
 
* [[Flow shop]]
 
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
 
* [[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>]]
 
* [[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>]]
 
* [[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>]]
Строка 593: Строка 627:
 
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </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>]]
 
* [[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»