Дискретная математика, алгоритмы и структуры данных — различия между версиями
Qradimir (обсуждение | вклад) (Новые конспекты из методов решений) |
м (rollbackEdits.php mass rollback) |
||
(не показано 56 промежуточных версий 32 участников) | |||
Строка 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> | ||
Строка 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 с помощью метода четырех русских) | ||
* [[Алгоритм Хьюи]] | * [[Алгоритм Хьюи]] | ||
Строка 565: | Строка 589: | ||
* [[1sumu|<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>]] | * [[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>]] | * [[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>]] | * [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]] | ||
Строка 570: | Строка 596: | ||
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_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>]] | * [[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>]] | ||
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] | * [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] | ||
Строка 592: | Строка 619: | ||
* [[Ppi1riintegerLmax|<tex>P \mid p_i=1; r_i - integer \mid L_{max}</tex>]] | * [[Ppi1riintegerLmax|<tex>P \mid p_i=1; r_i - integer \mid L_{max}</tex>]] | ||
* [[RSumCi|<tex>R \mid \mid \sum C_i</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>]] | * [[QpmtnSumCi|<tex> Q \mid pmtn \mid \sum C_i </tex>]] |
Текущая версия на 19:43, 4 сентября 2022
Убедительная просьба читать правила оформления вики-конспектов.
Символом
помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.Первый семестр
Отношения
- Определение отношения
- Композиция отношений, степень отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Изоморфизмы упорядоченных множеств
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- Транзитивный остов
Булевы функции
- Определение булевой функции
- Побитовые операции
- Суперпозиции
- ДНФ
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- КНФ
- 2-SAT
- XOR-SAT
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Пороговая функция
- Троичная логика
Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- Простейшие методы синтеза схем из функциональных элементов
- Метод Лупанова синтеза схем
- Cумматор
- Каскадный сумматор
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса
- Контактная схема
- Триггеры
- Квантовые гейты
Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n)
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78
- Алгоритм LZW
- Алгоритм LZSS
- Алгоритм LZMA
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
Комбинаторика
Комбинаторные объекты
- Комбинаторные объекты
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Монотонный код Грея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- Методы генерации случайного сочетания
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
Свойства комбинаторных объектов
- Умножение перестановок, обратная перестановка, группа перестановок
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
Динамическое программирование
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Быстрый поиск наибольшей возрастающей подпоследовательности*
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о рюкзаке
Способы оптимизации методов динамического программирования
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Meet-in-the-middle
- Convex hull trick
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Задача о наибольшей общей возрастающей последовательности
- Задача о наибольшей общей палиндромной подпоследовательности
- Динамическое программирование по профилю
- Динамика по поддеревьям
Теория вероятностей
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Формула полной вероятности
- Формула Байеса
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины
- Дисперсия случайной величины
- Ковариация случайных величин
- Корреляция случайных величин
- Неравенство Маркова
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Парадоксы теории вероятностей
- Схема Бернулли
Марковские цепи
- Марковская цепь
- Теорема о поглощении
- Фундаментальная матрица
- Математическое ожидание времени поглощения
- Расчет вероятности поглощения в состоянии
- Эргодическая марковская цепь
- Регулярная марковская цепь
- Примеры использования Марковских цепей
- Скрытые Марковские модели
- Алгоритм Витерби
- Алгоритм "Вперед-Назад"
- Алгоритм Баума-Велша
Второй семестр
Амортизационный анализ
- Амортизационный анализ
- Динамический массив
- Hashed Array Tree
- Список
- Стек
- Очередь
- Дек
- Мажорирующий элемент
- Счетчик Кнута
- Мастер-теорема
- List order maintenance
Персистентные структуры данных
- Персистентные структуры данных
- Персистентный стек
- Персистентная очередь
- Персистентный дек
- Персистентная приоритетная очередь
Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- Фибоначчиева куча
- Левосторонняя куча
- Тонкая куча
- Толстая куча на избыточном счетчике
- Куча Бродала-Окасаки
Система непересекающихся множеств
- Наивные реализации
- Списки с весовой эвристикой
- Реализация с помощью леса корневых деревьев
- СНМ с операцией удаления за О(1)
Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Декартово дерево по неявному ключу
- Splay-дерево
- Взвешенное дерево
- Tango-дерево
- Рандомизированное бинарное дерево поиска
- Дерево ван Эмде Боаса
- Список с пропусками
- Fusion tree
- Сверхбыстрый цифровой бор
- Rope
- AA-дерево
Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Корневая декомпозиция с операциями: get, insert, erase
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
Хеширование
- Хеш-таблица
- Разрешение коллизий
- Хеширование кукушки
- Идеальное хеширование
- Перехеширование
- Фильтр Блума
- Quotient filter
- Универсальное семейство хеш-функций
- Расширяемое хеширование
Сортировки
Квадратичные сортировки
Сортировки на сравнениях
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Терпеливая сортировка
- Timsort
- Smoothsort
- Теорема о нижней оценке для сортировки сравнениями
Многопоточные сортировки
Другие сортировки
- Поиск k-ой порядковой статистики
- Поиск k-ой порядковой статистики за линейное время
- Поиск k-ой порядковой статистики в двух массивах
- Сортировка подсчетом
- Цифровая сортировка
- Карманная сортировка
- Сортировка Хана
- Задача флага Нидерландов
- Блинная сортировка
Сортирующие сети
- Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортирующие сети для квадратичных сортировок
- Сортировочные сети с особыми свойствами
- Сеть Бетчера
Алгоритмы поиска
- Целочисленный двоичный поиск
- Поиск в матрице
- Вещественный двоичный поиск
- Троичный поиск
- Поиск с помощью золотого сечения
- Интерполяционный поиск
- Метод Фибоначчи
Связь между структурами данных
Третий семестр
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
- Алгоритмы на деревьях
- Двудольные графы
- Дополнительный, самодополнительный граф
- Теоретико-множественные операции над графами
- Рёберное ядро
- Факторизация графов
- Группы графов
- Гиперграфы
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
- Задача о динамической связности оффлайн
Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
- Минимально узкое остовное дерево
- Остовное дерево в планарном графе
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие рёбер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Деревья Эйлерова обхода
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Теорема Гринберга
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Теорема Вагнера
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
- Разрез в планарных графах
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Верхние и нижние оценки хроматического числа
- Хроматическое число планарного графа
- Многочлен Татта
- Теория Рамсея
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
Задача о паросочетании
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Рёберное ядро
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
- Декомпозиция Эдмондса-Галлаи
- Задача об устойчивом паросочетании
- Совершенное паросочетание в кубическом графе
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Сложение и разность потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Алгоритм масштабирования потока
- Блокирующий поток
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм Голдберга-Тарьяна
- Алгоритм поиска блокирующего потока в ациклической сети
- Метод проталкивания предпотока
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Штор-Вагнера нахождения минимального разреза
- Алгоритм Каргера для нахождения минимального разреза
- Примеры сведения к задачам поиска потока
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
- Алгоритм отмены цикла минимального среднего веса
Четвертый семестр
Основные определения. Простые комбинаторные свойства слов
- Основные определения, связанные со строками
- Период и бордер, их связь
- Слово Фибоначчи
- Слово Туэ-Морса
- Декомпозиция Линдона
- Алгоритм Ландау-Шмидта
- Алгоритм Крочемора
- Алгоритм Мейна-Лоренца
- Алгоритм Манакера
- Дерево палиндромов
Поиск подстроки в строке
Точный поиск
- Наивный алгоритм поиска подстроки в строке
- Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
- Префикс-функция
- Алгоритм Кнута-Морриса-Пратта
- Автомат Кнута-Морриса-Пратта
- Z-функция
- Бор
- Алгоритм Ахо-Корасик
- Суффиксный автомат
- Алгоритм Бойера-Мура
- Алгоритм Апостолико-Крочемора
- Алгоритм Колусси
- Алгоритм Райта
- Алгоритм Shift-And
- Двусторонний алгоритм
- Турбо-алгоритм Бойера-Мура
Нечёткий поиск
Суффиксное дерево
Суффиксный массив
- Суффиксный массив
- Построение суффиксного массива с помощью стандартных методов сортировки
- Алгоритм цифровой сортировки суффиксов циклической строки
- Алгоритм Касаи и др.
- Алгоритм Карккайнена-Сандерса
- Алгоритм поиска подстроки в строке с помощью суффиксного массива
- Количество подпалиндромов в строке
Задача о наименьшем общем предке
- Алгоритм Мо
- Сведение задачи LCA к задаче RMQ
- Сведение задачи RMQ к задаче LCA
- Метод двоичного подъема
- Решение RMQ с помощью разреженной таблицы
- Двумерная разреженная таблица
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четырех русских)
- Алгоритм Хьюи
- Heavy-light декомпозиция
- Алгоритм Шибера-Вишкина
- Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
- Link-Cut Tree
- Rake-Compress деревья
Матроиды
Основные факты теории матроидов
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Аксиоматизация матроида рангами
- Двойственный матроид
- Оператор замыкания для матроидов
- Покрытия, закрытые множества
- Матроид Вамоса
Пересечение матроидов
- Пересечение матроидов, определение, примеры
- Граф замен
- Алгоритм построения базы в пересечении матроидов
Объединение матроидов
- Объединение матроидов, проверка множества на независимость
- Объединение матроидов, доказательство того, что объединение является матроидом
- Алгоритм построения базы в объединении матроидов