|
|
| Строка 1: |
Строка 1: |
| − | [[Категория:Дискретная математика и алгоритмы]]
| |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
| |
| | | | |
| − | Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
| |
| − |
| |
| − | = Первый семестр =
| |
| − |
| |
| − | == Отношения ==
| |
| − | *[[Определение отношения]]
| |
| − | *[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
| |
| − | *[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
| |
| − | *[[Симметричное отношение]]
| |
| − | *[[Антисимметричное отношение]]
| |
| − | *[[Транзитивное отношение]]
| |
| − | *[[Отношение порядка]]
| |
| − | *[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
| |
| − | *[[Отношение эквивалентности]]
| |
| − | *[[Транзитивное замыкание|Транзитивное замыкание отношения]]
| |
| − | *[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
| |
| − | *[[Транзитивный остов]]
| |
| − |
| |
| − | == Булевы функции ==
| |
| − | *[[Определение булевой функции]]
| |
| − | *[[Побитовые операции]]<tex>^\star</tex>
| |
| − | *[[Суперпозиции]]
| |
| − | *[[ДНФ]]
| |
| − | *[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
| |
| − | *[[КНФ]]
| |
| − | *[[2-SAT]]
| |
| − | *[[XOR-SAT]]<tex>^\star</tex>
| |
| − | *[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
| |
| − | *[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
| |
| − | *[[Полные системы функций. Теорема Поста о полной системе функций]]
| |
| − | *[[Представление функции класса DM с помощью медианы]]
| |
| − | *[[Пороговая функция]]
| |
| − | *[[Троичная логика]]<tex>^\star</tex>
| |
| − |
| |
| − | == Схемы из функциональных элементов ==
| |
| − | *[[Реализация булевой функции схемой из функциональных элементов]]
| |
| − | *[[Простейшие методы синтеза схем из функциональных элементов]]
| |
| − | *[[Метод Лупанова синтеза схем]]
| |
| − | *[[Cумматор]]
| |
| − | *[[Каскадный сумматор]]
| |
| − | *[[Двоичный каскадный сумматор]]
| |
| − | *[[Троичный сумматор]]<tex>^\star</tex>
| |
| − | *[[Реализация вычитания сумматором]]
| |
| − | *[[Матричный умножитель]]
| |
| − | *[[Дерево Уоллеса]]
| |
| − | *[[Контактная схема]]
| |
| − | *[[Триггеры]]<tex>^\star</tex>
| |
| − | *[[Квантовые гейты]]<tex>^\star</tex>
| |
| − |
| |
| − | == Представление информации ==
| |
| − | *[[Кодирование информации]]
| |
| − | *[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
| |
| − | *[[Представление вещественных чисел]]
| |
| − | *[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
| |
| − |
| |
| − | == Алгоритмы сжатия ==
| |
| − | * [[Алгоритм Хаффмана]]
| |
| − | * [[Оптимальное хранение словаря в алгоритме Хаффмана]]
| |
| − | * [[Алгоритм Хаффмана за O(n)]]
| |
| − | * [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
| |
| − | * [[Неравенство Крафта]]
| |
| − | * [[Неравенство Макмиллана]]
| |
| − | * [[Код Шеннона]]
| |
| − | * [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
| |
| − | * [[Алгоритмы LZ77 и LZ78]]
| |
| − | * [[Алгоритм LZW]]
| |
| − | * [[Алгоритм LZSS]]<tex>^\star</tex>
| |
| − | * [[Алгоритм LZMA]]<tex>^\star</tex>
| |
| − | * [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
| |
| − | * [[Преобразование MTF]]
| |
| − | * [[Расстояние Хэмминга]]
| |
| − | * [[Избыточное кодирование, код Хэмминга]]
| |
| − | * [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
| |
| − |
| |
| − | == Комбинаторика ==
| |
| − | === Комбинаторные объекты ===
| |
| − | * [[Комбинаторные объекты]]
| |
| − | * [[Лексикографический порядок]]
| |
| − | * [[Коды Грея]]
| |
| − | * [[Коды Грея для перестановок]]
| |
| − | * [[Коды антигрея]]
| |
| − | * [[Монотонный код Грея]]
| |
| − | * [[Цепные коды]]
| |
| − | * [[Правильные скобочные последовательности]]
| |
| − |
| |
| − | === Генерация комбинаторных объектов ===
| |
| − | * [[Генерация комбинаторных объектов в лексикографическом порядке]]
| |
| − | * [[Получение номера по объекту]]
| |
| − | * [[Получение объекта по номеру]]
| |
| − | * [[Получение следующего объекта]]
| |
| − | * [[Получение предыдущего объекта]]<tex>^\star</tex>
| |
| − | * [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
| |
| − | * [[Методы генерации случайного сочетания]]<tex>^\star</tex>
| |
| − |
| |
| − | === Подсчёт числа объектов ===
| |
| − | * [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
| |
| − | * [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
| |
| − | * [[Производящая функция]]
| |
| − | * [[Лемма Бёрнсайда и Теорема Пойа]]
| |
| − | * [[Задача об ожерельях]]
| |
| − | * [[Числа Стирлинга первого рода]]
| |
| − | * [[Числа Стирлинга второго рода]]
| |
| − | * [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
| |
| − | * [[Числа Каталана]]
| |
| − |
| |
| − | === Свойства комбинаторных объектов ===
| |
| − | * [[Умножение перестановок, обратная перестановка, группа перестановок]]
| |
| − | * [[Действие перестановки на набор из элементов, представление в виде циклов]]
| |
| − | * [[Таблица инверсий]]
| |
| − | * [[Теорема Кэли]]
| |
| − | * [[Матричное представление перестановок]]
| |
| − | * [[Задача о минимуме/максимуме скалярного произведения]]
| |
| − | * [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
| |
| − |
| |
| − | == [[Динамическое программирование]] ==
| |
| − | === Классические задачи динамического программирования ===
| |
| − | *[[Кратчайший путь в ациклическом графе]]
| |
| − | *[[Задача о числе путей в ациклическом графе]]
| |
| − | *[[Задача о расстановке знаков в выражении]]
| |
| − | *[[Задача о порядке перемножения матриц]]
| |
| − | *[[Задача о наибольшей общей подпоследовательности]]
| |
| − | *[[Задача о наибольшей возрастающей подпоследовательности]]
| |
| − | *[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
| |
| − | *[[Задача коммивояжера, ДП по подмножествам]]
| |
| − | *[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
| |
| − | *[[Задача о рюкзаке]]
| |
| − |
| |
| − | === Способы оптимизации методов динамического программирования ===
| |
| − | *[[Метод четырех русских для умножения матриц]]
| |
| − | *[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
| |
| − | *[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
| |
| − | *[[Meet-in-the-middle]]<tex>^\star</tex>
| |
| − | *[[Convex hull trick]]
| |
| − |
| |
| − | === Другие задачи ===
| |
| − | *[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
| |
| − | *[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
| |
| − | *[[Задача о наибольшей подпоследовательности-палиндроме]]
| |
| − | *[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
| |
| − | *[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
| |
| − | *[[Динамическое программирование по профилю]]<tex>^\star</tex>
| |
| − | *[[Динамика по поддеревьям]]
| |
| − |
| |
| − | == Теория вероятностей ==
| |
| − | *[[Вероятностное пространство, элементарный исход, событие]]
| |
| − | *[[Независимые события]]
| |
| − | *[[Условная вероятность]]
| |
| − | *[[Формула полной вероятности]]
| |
| − | *[[Формула Байеса]]
| |
| − | *[[Дискретная случайная величина]]
| |
| − | *[[Независимые случайные величины]]
| |
| − | *[[Математическое ожидание случайной величины]]
| |
| − | *[[Дисперсия случайной величины]]
| |
| − | *[[Ковариация случайных величин]]
| |
| − | *[[Корреляция случайных величин]]
| |
| − | *[[Неравенство Маркова]]
| |
| − | *[[Энтропия случайного источника]]
| |
| − | *[[Симуляция одним распределением другого]]
| |
| − | *[[Арифметическое кодирование]]
| |
| − | *[[Парадоксы теории вероятностей]]<tex>^\star</tex>
| |
| − | *[[Схема Бернулли]]<tex>^\star</tex>
| |
| − |
| |
| − | == Марковские цепи ==
| |
| − |
| |
| − | * [[Марковская цепь]]
| |
| − | * [[Теорема о поглощении]]
| |
| − | * [[Фундаментальная матрица]]
| |
| − | * [[Математическое ожидание времени поглощения]]
| |
| − | * [[Расчет вероятности поглощения в состоянии]]
| |
| − | * [[Эргодическая марковская цепь]]
| |
| − | * [[Регулярная марковская цепь]]
| |
| − | * [[Примеры использования Марковских цепей]]
| |
| − | * [[Скрытые Марковские модели]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Витерби]]<tex>^\star</tex>
| |
| − | * [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Баума-Велша]]<tex>^\star</tex>
| |
| − |
| |
| − | = Второй семестр =
| |
| − |
| |
| − | == Амортизационный анализ ==
| |
| − | * [[Амортизационный анализ]]
| |
| − | * [[Динамический массив]]
| |
| − | * [[Hashed Array Tree]]<tex>^\star</tex>
| |
| − | * [[Список]]
| |
| − | * [[Стек]]
| |
| − | * [[Очередь]]
| |
| − | * [[Дек]]
| |
| − | * [[Мажорирующий элемент]]
| |
| − | * [[Счетчик Кнута]]
| |
| − | * [[Мастер-теорема]]<tex>^\star</tex>
| |
| − | * [[List order maintenance]]<tex>^\star</tex>
| |
| − |
| |
| − | == Персистентные структуры данных ==
| |
| − | * [[Персистентные структуры данных]]
| |
| − | * [[Персистентный стек]]
| |
| − | * [[Персистентная очередь]]
| |
| − | * [[Персистентный дек]]
| |
| − | * [[Персистентная приоритетная очередь]]
| |
| − |
| |
| − | == [[Приоритетные очереди]] ==
| |
| − | * [[Двоичная куча]]
| |
| − | * [[Биномиальная куча]]
| |
| − | * [[Фибоначчиева куча]]
| |
| − | * [[Левосторонняя куча]]
| |
| − | * [[Тонкая куча]]
| |
| − | * [[Толстая куча на избыточном счетчике]]
| |
| − | * [[Куча Бродала-Окасаки]]<tex>^\star</tex>
| |
| − |
| |
| − | == Система непересекающихся множеств ==
| |
| − | * [[СНМ (наивные реализации) | Наивные реализации]]
| |
| − | * [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
| |
| − | * [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
| |
| − | * [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
| |
| − |
| |
| − | == [[Поисковые структуры данных]] ==
| |
| − | * [[Упорядоченное множество]]
| |
| − | * [[Дерево поиска, наивная реализация]]
| |
| − | * [[АВЛ-дерево]]
| |
| − | * [[2-3 дерево]]
| |
| − | * [[B-дерево]]
| |
| − | * [[Красно-черное дерево]]
| |
| − | * [[Декартово дерево]]
| |
| − | * [[Декартово дерево по неявному ключу]]
| |
| − | * [[Splay-дерево]]
| |
| − | * [[Взвешенное дерево]]
| |
| − | * [[Tango-дерево]]<tex>^\star</tex>
| |
| − | * [[Рандомизированное бинарное дерево поиска]]
| |
| − | * [[Дерево ван Эмде Боаса]]
| |
| − | * [[Список с пропусками]]
| |
| − | * [[Fusion tree]]<tex>^\star</tex>
| |
| − | * [[Сверхбыстрый цифровой бор]]
| |
| − | * [[Rope]]<tex>^\star</tex>
| |
| − | * [[AA-дерево]]<tex>^\star</tex>
| |
| − |
| |
| − | == Дерево отрезков ==
| |
| − | * [[Статистики на отрезках. Корневая эвристика]]
| |
| − | * [[Корневая декомпозиция с операциями: get, insert, erase]]
| |
| − | * [[Дерево отрезков. Построение]]
| |
| − | * [[Реализация запроса в дереве отрезков сверху]]
| |
| − | * [[Реализация запроса в дереве отрезков снизу]]
| |
| − | * [[Несогласованные поддеревья. Реализация массового обновления]]
| |
| − | * [[Многомерное дерево отрезков]]
| |
| − | * [[Сжатое многомерное дерево отрезков]]
| |
| − |
| |
| − | == Дерево Фенвика ==
| |
| − | * [[Дерево Фенвика]]
| |
| − | * [[Встречное дерево Фенвика]]
| |
| − | * [[Дерево Фенвика для некоммутативных операций]]
| |
| − | * [[Многомерное дерево Фенвика]]
| |
| − |
| |
| − | == Хеширование ==
| |
| − | * [[Хеш-таблица]]
| |
| − | * [[Разрешение коллизий]]
| |
| − | * [[Хеширование кукушки]]
| |
| − | * [[Идеальное хеширование]]
| |
| − | * [[Перехеширование]]
| |
| − | * [[Фильтр Блума]]
| |
| − | * [[Quotient filter]]<tex>^\star</tex>
| |
| − | * [[Универсальное семейство хеш-функций]]
| |
| − | * [[Расширяемое хеширование]]<tex>^\star</tex>
| |
| − |
| |
| − | == [[Сортировки]] ==
| |
| − | === Квадратичные сортировки ===
| |
| − | * [[Сортировка выбором]]
| |
| − | * [[Сортировка пузырьком]]
| |
| − | * [[Сортировка вставками]]
| |
| − | === Сортировки на сравнениях ===
| |
| − | * [[Сортировка Шелла]]<tex>^\star</tex>
| |
| − | * [[Сортировка кучей]]
| |
| − | * [[Быстрая сортировка]]
| |
| − | * [[Сортировка слиянием]]
| |
| − | * [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
| |
| − | * [[Терпеливая сортировка]]<tex>^\star</tex>
| |
| − | * [[Timsort]]<tex>^\star</tex>
| |
| − | * [[Smoothsort]]<tex>^\star</tex>
| |
| − | * [[Теорема о нижней оценке для сортировки сравнениями]]
| |
| − |
| |
| − | === Многопоточные сортировки ===
| |
| − | * [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
| |
| − | * [[PSRS-сортировка]]<tex>^\star</tex>
| |
| − | === Другие сортировки ===
| |
| − | * [[Поиск k-ой порядковой статистики]]
| |
| − | * [[Поиск k-ой порядковой статистики за линейное время]]
| |
| − | * [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
| |
| − | * [[Сортировка подсчетом]]
| |
| − | * [[Цифровая сортировка]]
| |
| − | * [[Карманная сортировка]]
| |
| − | * [[Сортировка Хана]]<tex>^\star</tex>
| |
| − | * [[Задача флага Нидерландов]]<tex>^\star</tex>
| |
| − | * [[Блинная сортировка]]<tex>^\star</tex>
| |
| − |
| |
| − | == Сортирующие сети ==
| |
| − | * [[Сортирующие сети]]
| |
| − | * [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
| |
| − | * [[Сортирующие сети для квадратичных сортировок]]
| |
| − | * [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
| |
| − | * [[Сеть Бетчера]]
| |
| − |
| |
| − | == Алгоритмы поиска ==
| |
| − | * [[Целочисленный двоичный поиск]]
| |
| − | * [[Поиск в матрице]]<tex>^\star</tex>
| |
| − | * [[Вещественный двоичный поиск]]
| |
| − | * [[Троичный поиск]]
| |
| − | * [[Поиск с помощью золотого сечения]]
| |
| − | * [[Интерполяционный поиск]]
| |
| − | * [[Метод Фибоначчи]]<tex>^\star</tex>
| |
| − |
| |
| − | == Связь между структурами данных ==
| |
| − | * [[Связь между структурами данных]]
| |
| − |
| |
| − | = Третий семестр =
| |
| − |
| |
| − | == Основные определения теории графов ==
| |
| − | * [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
| |
| − | * [[Лемма о рукопожатиях]]
| |
| − | * [[Теорема о существовании простого пути в случае существования пути]]
| |
| − | * [[Теорема о существовании простого цикла в случае существования цикла]]
| |
| − | * [[Матрица смежности графа]]
| |
| − | * [[Матрица инцидентности графа]]
| |
| − | * [[Циклическое пространство графа]]<tex>^\star</tex>
| |
| − | * [[Фундаментальные циклы графа]]<tex>^\star</tex>
| |
| − | * [[Дерево, эквивалентные определения]]
| |
| − | * [[Алгоритмы на деревьях]]<tex>^\star</tex>
| |
| − | * [[Двудольные графы]]
| |
| − | * [[Дополнительный, самодополнительный граф]]
| |
| − | * [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
| |
| − | * [[Рёберное ядро]]
| |
| − | * [[Факторизация графов]]<tex>^\star</tex>
| |
| − | * [[Группы графов]]<tex>^\star</tex>
| |
| − | * [[Гиперграфы]]<tex>^\star</tex>
| |
| − |
| |
| − | == Связность в графах ==
| |
| − | * [[Отношение связности, компоненты связности]]
| |
| − | * [[Отношение реберной двусвязности]]
| |
| − | * [[Отношение вершинной двусвязности]]
| |
| − | * [[Точка сочленения, эквивалентные определения]]
| |
| − | * [[Мост, эквивалентные определения]]
| |
| − | * [[Граф компонент реберной двусвязности]]
| |
| − | * [[Граф блоков-точек сочленения]]
| |
| − | * [[k-связность]]
| |
| − | * [[Теорема Менгера]]
| |
| − | * [[Теорема Менгера, альтернативное доказательство]]
| |
| − | * [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
| |
| − | * [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
| |
| − |
| |
| − | == Остовные деревья ==
| |
| − | === Построение остовных деревьев ===
| |
| − | * [[Остовные деревья: определения, лемма о безопасном ребре]]
| |
| − | * [[Алгоритм Прима]]
| |
| − | * [[Алгоритм Краскала]]
| |
| − | * [[Алгоритм Борувки]]
| |
| − | * [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
| |
| − | * [[Алгоритм двух китайцев]]
| |
| − | * [[Минимально узкое остовное дерево]]
| |
| − | * [[Остовное дерево в планарном графе]]
| |
| − |
| |
| − | === Свойства остовных деревьев ===
| |
| − | * [[Матрица Кирхгофа]]
| |
| − | * [[Связь матрицы Кирхгофа и матрицы инцидентности]]
| |
| − | * [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
| |
| − | * [[Количество помеченных деревьев]]
| |
| − | * [[Коды Прюфера]]
| |
| − |
| |
| − | == Обходы графов ==
| |
| − | === Эйлеровы графы ===
| |
| − | * [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
| |
| − | * [[Покрытие рёбер графа путями]]
| |
| − | * [[Алгоритм построения Эйлерова цикла]]
| |
| − | * [[Произвольно вычерчиваемые из заданной вершины графы]]
| |
| − | * [[Деревья Эйлерова обхода]]<tex>^\star</tex>
| |
| − |
| |
| − | === Гамильтоновы графы ===
| |
| − | * [[Гамильтоновы графы]]
| |
| − | * [[Теорема Хватала]]
| |
| − | * [[Теорема Дирака]]
| |
| − | * [[Теорема Оре]]
| |
| − | * [[Теорема Поша]]<tex>^\star</tex>
| |
| − | * [[Теорема Гуйя-Ури]]<tex>^\star</tex>
| |
| − | * [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
| |
| − | * [[Теорема Гринберга]]<tex>^\star</tex>
| |
| − | * [[Турниры]]
| |
| − | * [[Теорема Редеи-Камиона]]
| |
| − |
| |
| − | == Укладки графов ==
| |
| − | * [[Укладка графа на плоскости]]
| |
| − | * [[Формула Эйлера]]
| |
| − | * [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
| |
| − | * [[Укладка дерева]]
| |
| − | * [[Укладка графа с планарными компонентами реберной двусвязности]]
| |
| − | * [[Укладка графа с планарными компонентами вершинной двусвязности]]
| |
| − | * [[Теорема Понтрягина-Куратовского]]
| |
| − | * [[Теорема Вагнера]]
| |
| − | * [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
| |
| − | * [[Двойственный граф планарного графа]]
| |
| − | * [[Теорема Фари]]<tex>^\star</tex>
| |
| − | * [[Гамма-алгоритм]]
| |
| − | * [[Разрез в планарных графах]]
| |
| − |
| |
| − | == Раскраски графов ==
| |
| − | * [[Раскраска графа]]
| |
| − | * [[Двудольные графы и раскраска в 2 цвета]]
| |
| − | * [[Хроматический многочлен]]
| |
| − | * [[Формула Зыкова]]
| |
| − | * [[Формула Уитни]]
| |
| − | * [[Теорема Брукса]]
| |
| − | * [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
| |
| − | * [[Хроматическое число планарного графа]]
| |
| − | * [[Многочлен Татта]]<tex>^\star</tex>
| |
| − | * [[Теория Рамсея]]<tex>^\star</tex>
| |
| − |
| |
| − | == Обход в глубину ==
| |
| − | * [[Обход в глубину, цвета вершин]]
| |
| − | * [[Лемма о белых путях]]
| |
| − | * [[Использование обхода в глубину для проверки связности]]
| |
| − | * [[Использование обхода в глубину для поиска цикла]]
| |
| − | * [[Использование обхода в глубину для топологической сортировки]]
| |
| − | * [[Использование обхода в глубину для поиска компонент сильной связности]]
| |
| − | * [[Использование обхода в глубину для поиска точек сочленения]]
| |
| − | * [[Построение компонент вершинной двусвязности]]
| |
| − | * [[Использование обхода в глубину для поиска мостов]]
| |
| − | * [[Построение компонент реберной двусвязности]]
| |
| − |
| |
| − | == Кратчайшие пути в графах ==
| |
| − | * [[Обход в ширину]]
| |
| − | * [[Алгоритм Форда-Беллмана]]
| |
| − | * [[Алгоритм Дейкстры]]
| |
| − | * [[Алгоритм Флойда]]
| |
| − | * [[Алгоритм Джонсона]]
| |
| − | * [[Алгоритм Левита]]<tex>^\star</tex>
| |
| − | * [[Алгоритм A*]] <tex>^\star</tex>
| |
| − | * [[Алгоритм D*]] <tex>^\star</tex>
| |
| − | * [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
| |
| − |
| |
| − | == Задача о паросочетании ==
| |
| − | * [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
| |
| − | * [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
| |
| − | * [[Алгоритм Куна для поиска максимального паросочетания]]
| |
| − | * [[Теорема Холла]]
| |
| − | * [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
| |
| − | * [[Связь вершинного покрытия и независимого множества]]
| |
| − | * [[Рёберное ядро]]<tex>^\star</tex>
| |
| − | * [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
| |
| − | * [[Теорема Татта о существовании полного паросочетания]]
| |
| − | * [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
| |
| − | * [[Декомпозиция Эдмондса-Галлаи]]
| |
| − | * [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
| |
| − | * [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
| |
| − |
| |
| − | == Задача о максимальном потоке ==
| |
| − | * [[Определение сети, потока]]
| |
| − | * [[Разрез, лемма о потоке через разрез]]
| |
| − | * [[Дополняющая сеть, дополняющий путь]]
| |
| − | * [[Сложение и разность потоков]]
| |
| − | * [[Теорема Форда-Фалкерсона]]
| |
| − | * [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
| |
| − | * [[Алоритм Эдмондса-Карпа]]
| |
| − | * [[Алгоритм масштабирования потока]]
| |
| − | * [[Блокирующий поток]]
| |
| − | * [[Схема алгоритма Диница]]
| |
| − | * [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
| |
| − | * [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
| |
| − | * [[Алгоритм поиска блокирующего потока в ациклической сети]]
| |
| − | * [[Метод проталкивания предпотока]]
| |
| − | * [[Алгоритм "поднять-в-начало"]]
| |
| − | * [[Теорема о декомпозиции]]
| |
| − | * [[Теорема о декомпозиционном барьере]]
| |
| − | * [[Циркуляция потока]]
| |
| − | * [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
| |
| − | * [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
| |
| − | * [[Примеры сведения к задачам поиска потока]]
| |
| − |
| |
| − | == Задача о потоке минимальной стоимости ==
| |
| − | * [[Поток минимальной стоимости]]
| |
| − | * [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
| |
| − | * [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
| |
| − | * [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
| |
| − | * [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
| |
| − | * [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
| |
| − | * [[Венгерский алгоритм решения задачи о назначениях]]
| |
| − | * [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
| |
| − |
| |
| − | = Четвертый семестр =
| |
| − |
| |
| − | == Основные определения. Простые комбинаторные свойства слов ==
| |
| − | * [[Основные определения, связанные со строками]]
| |
| − | * [[Период и бордер, их связь]]
| |
| − | * [[Слово Фибоначчи]]
| |
| − | * [[Слово Туэ-Морса]]
| |
| − | * [[Декомпозиция Линдона]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Крочемора]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Манакера]]<tex>^\star</tex>
| |
| − | * [[Дерево палиндромов]]<tex>^\star</tex>
| |
| − |
| |
| − | == [[Поиск подстроки в строке]] ==
| |
| − | === Точный поиск ===
| |
| − | * [[Наивный алгоритм поиска подстроки в строке]]
| |
| − | * [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
| |
| − | * [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
| |
| − | * [[Префикс-функция]]
| |
| − | * [[Алгоритм Кнута-Морриса-Пратта]]
| |
| − | * [[Автомат Кнута-Морриса-Пратта]]
| |
| − | * [[Z-функция]]
| |
| − | * [[Бор]]
| |
| − | * [[Алгоритм Ахо-Корасик]]
| |
| − | * [[Суффиксный автомат]]
| |
| − | * [[Алгоритм Бойера-Мура]]
| |
| − | * [[Алгоритм Апостолико-Крочемора]]<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>
| |
| − |
| |
| − | == Суффиксное дерево ==
| |
| − | * [[Суффиксный бор]]
| |
| − | * [[Сжатое суффиксное дерево]]
| |
| − | * [[Алгоритм Укконена]]
| |
| − | * [[Алгоритм МакКрейта]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Фарача]]<tex>^\star</tex>
| |
| − |
| |
| − | == Суффиксный массив ==
| |
| − | * [[Суффиксный массив]]
| |
| − | * [[Построение суффиксного массива с помощью стандартных методов сортировки]]
| |
| − | * [[Алгоритм цифровой сортировки суффиксов циклической строки]]
| |
| − | * [[Алгоритм Касаи и др.]]
| |
| − | * [[Алгоритм Карккайнена-Сандерса]]
| |
| − | * [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
| |
| − | * [[Количество подпалиндромов в строке]]<tex>^\star</tex>
| |
| − |
| |
| − | == Задача о наименьшем общем предке ==
| |
| − | * [[Алгоритм Мо]]
| |
| − | * [[Сведение задачи LCA к задаче RMQ]]
| |
| − | * [[Сведение задачи RMQ к задаче LCA]]
| |
| − | * [[Метод двоичного подъема]]
| |
| − | * [[Решение RMQ с помощью разреженной таблицы]]
| |
| − | * [[Двумерная разреженная таблица]]
| |
| − | * [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
| |
| − | * [[Алгоритм Хьюи]]
| |
| − | * [[Heavy-light декомпозиция]]
| |
| − | * [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
| |
| − | * [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
| |
| − | * [[Link-Cut Tree]]<tex>^\star</tex>
| |
| − | * [[Rake-Compress деревья]]<tex>^\star</tex>
| |
| − |
| |
| − | == Матроиды ==
| |
| − | === Основные факты теории матроидов ===
| |
| − | * [[Определение матроида]]
| |
| − | * [[Примеры матроидов]]
| |
| − | * [[Прямая сумма матроидов]]
| |
| − | * [[Теорема Радо-Эдмондса (жадный алгоритм)]]
| |
| − | * [[Теорема о базах]]
| |
| − | * [[Аксиоматизация матроида базами]]
| |
| − | * [[Теорема о циклах]]
| |
| − | * [[Аксиоматизация матроида циклами]]
| |
| − | * [[Ранговая функция, полумодулярность]]
| |
| − | * [[Аксиоматизация матроида рангами]]
| |
| − | * [[Двойственный матроид]]
| |
| − | * [[Оператор замыкания для матроидов]]
| |
| − | * [[Покрытия, закрытые множества]]
| |
| − | * [[Матроид Вамоса]]<tex>^\star</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>]]
| |
| − | * [[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>]]
| |
| − | * [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
| |
| − | * [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
| |
| − |
| |
| − | === Специальные случаи задач для двух станков ===
| |
| − | * [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
| |
| − | * [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
| |
| − | * [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
| |
| − | * [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
| |
| − | * [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]
| |
| − | * [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
| |
| − |
| |
| − | === Задачи для произвольного числа станков ===
| |
| − | * [[Flow shop]]
| |
| − | * [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
| |
| − | * [[PSumCi|<tex>P \mid \mid \sum C_{i}</tex>]]
| |
| − | * [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
| |
| − | * [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
| |
| − | * [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]
| |
| − | * [[Ppi1riintegerLmax|<tex>P \mid p_i=1; r_i - integer \mid L_{max}</tex>]]
| |
| − | * [[RSumCi|<tex>R \mid \mid \sum C_i</tex>]]
| |
| − | * [[RpmtnCmax|<tex>R \mid pmtn \mid C_{max}</tex>]]
| |
| − | * [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
| |
| − | * [[QpmtnSumCi|<tex> Q \mid pmtn \mid \sum C_i </tex>]]
| |
| − | * [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
| |
| − | * [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
| |
| − | * [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
| |
| − | * [[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>]]
| |
| − | * [[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>]]
| |
