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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Полностью удалено содержимое страницы)
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 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>]]

Текущая версия на 19:43, 4 сентября 2022

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

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

Содержание

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

Отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Точный поиск

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

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

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

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

Матроиды

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

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

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

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

Общая теория

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

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

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

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