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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Задача о паросочетании)
м (rollbackEdits.php mass rollback)
 
(не показано 290 промежуточных версий 86 участников)
Строка 1: Строка 1:
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 +
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
  
−
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
+
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
  
 
= Первый семестр =
 
= Первый семестр =
Строка 8: Строка 9:
 
== Отношения ==
 
== Отношения ==
 
*[[Определение отношения]]
 
*[[Определение отношения]]
−
*[[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]
+
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
 
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
*[[Симметричное отношение]]
 
*[[Симметричное отношение]]
 
*[[Антисимметричное отношение]]
 
*[[Антисимметричное отношение]]
 
*[[Транзитивное отношение]]
 
*[[Транзитивное отношение]]
−
*[[Связное отношение]]
 
 
*[[Отношение порядка]]
 
*[[Отношение порядка]]
 +
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
*[[Отношение эквивалентности]]
 
*[[Отношение эквивалентности]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
Строка 22: Строка 23:
 
== Булевы функции ==
 
== Булевы функции ==
 
*[[Определение булевой функции]]
 
*[[Определение булевой функции]]
 +
*[[Побитовые операции]]<tex>^\star</tex>
 
*[[Суперпозиции]]
 
*[[Суперпозиции]]
 
*[[ДНФ]]
 
*[[ДНФ]]
 
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[КНФ]]
 
*[[КНФ]]
 +
*[[2-SAT]]
 +
*[[XOR-SAT]]<tex>^\star</tex>
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
Строка 31: Строка 35:
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Пороговая функция]]
 
*[[Пороговая функция]]
 +
*[[Троичная логика]]<tex>^\star</tex>
  
 
== Схемы из функциональных элементов ==
 
== Схемы из функциональных элементов ==
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 +
*[[Простейшие методы синтеза схем из функциональных элементов]]
 
*[[Метод Лупанова синтеза схем]]
 
*[[Метод Лупанова синтеза схем]]
 
*[[Cумматор]]
 
*[[Cумматор]]
 
*[[Каскадный сумматор]]
 
*[[Каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
 +
*[[Троичный сумматор]]<tex>^\star</tex>
 
*[[Реализация вычитания сумматором]]
 
*[[Реализация вычитания сумматором]]
 
*[[Матричный умножитель]]
 
*[[Матричный умножитель]]
 
*[[Дерево Уоллеса]]
 
*[[Дерево Уоллеса]]
 +
*[[Контактная схема]]
 +
*[[Триггеры]]<tex>^\star</tex>
 +
*[[Квантовые гейты]]<tex>^\star</tex>
  
 
== Представление информации ==
 
== Представление информации ==
Строка 46: Строка 56:
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление вещественных чисел]]
 
*[[Представление вещественных чисел]]
−
*[[Представление символов, таблицы кодировок]]
+
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
  
 
== Алгоритмы сжатия ==
 
== Алгоритмы сжатия ==
 
* [[Алгоритм Хаффмана]]
 
* [[Алгоритм Хаффмана]]
−
* [[Алгоритм Ху-Таккера]]
+
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
 +
* [[Алгоритм Хаффмана за O(n)]]
 +
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
 
* [[Неравенство Крафта]]
 
* [[Неравенство Крафта]]
 
* [[Неравенство Макмиллана]]
 
* [[Неравенство Макмиллана]]
 +
* [[Код Шеннона]]
 +
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
 +
* [[Алгоритмы LZ77 и LZ78]]
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZW]]
−
* [[Алгоритмы LZ77 и LZ78]]
+
* [[Алгоритм LZSS]]<tex>^\star</tex>
 +
* [[Алгоритм LZMA]]<tex>^\star</tex>
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование MTF]]
 
* [[Преобразование MTF]]
 
* [[Расстояние Хэмминга]]
 
* [[Расстояние Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 +
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
  
 
== Комбинаторика ==
 
== Комбинаторика ==
 +
=== Комбинаторные объекты ===
 
* [[Комбинаторные объекты]]
 
* [[Комбинаторные объекты]]
 
* [[Лексикографический порядок]]
 
* [[Лексикографический порядок]]
−
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
 
−
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
 
−
* [[Получение номера по объекту]]
 
−
* [[Получение объекта по номеру]]
 
−
* [[Получение следующего объекта]]
 
 
* [[Коды Грея]]
 
* [[Коды Грея]]
 
* [[Коды Грея для перестановок]]
 
* [[Коды Грея для перестановок]]
 
* [[Коды антигрея]]
 
* [[Коды антигрея]]
 +
* [[Монотонный код Грея]]
 
* [[Цепные коды]]
 
* [[Цепные коды]]
 
* [[Правильные скобочные последовательности]]
 
* [[Правильные скобочные последовательности]]
−
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
+
 
 +
=== Генерация комбинаторных объектов ===
 +
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
* [[Получение номера по объекту]]
 +
* [[Получение объекта по номеру]]
 +
* [[Получение следующего объекта]]
 +
* [[Получение предыдущего объекта]]<tex>^\star</tex> 
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
−
* [[Методы генерации случайного сочетания]]
+
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
−
* [[Таблица инверсий]]
+
 
−
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
+
=== Подсчёт числа объектов ===
−
* [[Теорема Кэли]]
+
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
−
* [[Матричное представление перестановок]]
 
−
* [[Задача о минимуме/максимуме скалярного произведения]]
 
−
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
 
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 
* [[Производящая функция]]
 
* [[Производящая функция]]
Строка 88: Строка 105:
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга второго рода]]
 
* [[Числа Стирлинга второго рода]]
 +
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
 +
* [[Числа Каталана]]
 +
 +
=== Свойства комбинаторных объектов ===
 +
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
 +
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
 +
* [[Таблица инверсий]]
 +
* [[Теорема Кэли]]
 +
* [[Матричное представление перестановок]]
 +
* [[Задача о минимуме/максимуме скалярного произведения]]
 +
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
  
 
== [[Динамическое программирование]] ==
 
== [[Динамическое программирование]] ==
 +
=== Классические задачи динамического программирования ===
 
*[[Кратчайший путь в ациклическом графе]]
 
*[[Кратчайший путь в ациклическом графе]]
 +
*[[Задача о числе путей в ациклическом графе]]
 
*[[Задача о расстановке знаков в выражении]]
 
*[[Задача о расстановке знаков в выражении]]
 +
*[[Задача о порядке перемножения матриц]]
 
*[[Задача о наибольшей общей подпоследовательности]]
 
*[[Задача о наибольшей общей подпоследовательности]]
−
*[[Задача о порядке перемножения матриц]]
 
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
−
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
+
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
−
*[[Метод четырех русских для умножения матриц]]
 
−
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача коммивояжера, ДП по подмножествам]]
−
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
−
*[[Задача о расстоянии Дамерау-Левенштейна]]
+
*[[Задача о рюкзаке]]
 +
 
 +
=== Способы оптимизации методов динамического программирования ===
 +
*[[Метод четырех русских для умножения матриц]]
 +
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 +
*[[Meet-in-the-middle]]<tex>^\star</tex>
 +
*[[Convex hull trick]]
 +
 +
=== Другие задачи ===
 +
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
 +
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
−
*[[Meet-in-the-middle]]
+
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
−
*[[Динамическое программирование по профилю]]
+
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
−
*[[Задача о рюкзаке]]
+
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 
*[[Динамика по поддеревьям]]
 
*[[Динамика по поддеревьям]]
  
Строка 113: Строка 150:
 
*[[Независимые события]]
 
*[[Независимые события]]
 
*[[Условная вероятность]]
 
*[[Условная вероятность]]
 +
*[[Формула полной вероятности]]
 
*[[Формула Байеса]]
 
*[[Формула Байеса]]
−
*[[Формула полной вероятности]]
 
 
*[[Дискретная случайная величина]]
 
*[[Дискретная случайная величина]]
 
*[[Независимые случайные величины]]
 
*[[Независимые случайные величины]]
Строка 121: Строка 158:
 
*[[Ковариация случайных величин]]
 
*[[Ковариация случайных величин]]
 
*[[Корреляция случайных величин]]
 
*[[Корреляция случайных величин]]
 +
*[[Неравенство Маркова]]
 
*[[Энтропия случайного источника]]
 
*[[Энтропия случайного источника]]
 
*[[Симуляция одним распределением другого]]
 
*[[Симуляция одним распределением другого]]
 
*[[Арифметическое кодирование]]
 
*[[Арифметическое кодирование]]
−
*[[Парадоксы теории вероятностей]]
+
*[[Парадоксы теории вероятностей]]<tex>^\star</tex>
−
*[[Схема Бернулли]]
+
*[[Схема Бернулли]]<tex>^\star</tex>
  
 
== Марковские цепи ==
 
== Марковские цепи ==
Строка 137: Строка 175:
 
* [[Регулярная марковская цепь]]
 
* [[Регулярная марковская цепь]]
 
* [[Примеры использования Марковских цепей]]
 
* [[Примеры использования Марковских цепей]]
−
* [[Скрытые Марковские модели]]
+
* [[Скрытые Марковские модели]]<tex>^\star</tex>
−
* [[Алгоритм Витерби]]
+
* [[Алгоритм Витерби]]<tex>^\star</tex>
−
* [[Алгоритм "Вперед-Назад"]]
+
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
 +
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>
  
 
= Второй семестр =
 
= Второй семестр =
Строка 145: Строка 184:
 
== Амортизационный анализ ==
 
== Амортизационный анализ ==
 
* [[Амортизационный анализ]]
 
* [[Амортизационный анализ]]
−
* [[Саморасширяющийся массив]]
+
* [[Динамический массив]]
−
* [[Массив с увеличением/уменьшением размера]]
+
* [[Hashed Array Tree]]<tex>^\star</tex>
 
* [[Список]]
 
* [[Список]]
 
* [[Стек]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Очередь]]
 +
* [[Дек]]
 +
* [[Мажорирующий элемент]]
 +
* [[Счетчик Кнута]]
 +
* [[Мастер-теорема]]<tex>^\star</tex>
 +
* [[List order maintenance]]<tex>^\star</tex>
 +
 +
== Персистентные структуры данных ==
 +
* [[Персистентные структуры данных]]
 
* [[Персистентный стек]]
 
* [[Персистентный стек]]
 
* [[Персистентная очередь]]
 
* [[Персистентная очередь]]
 
* [[Персистентный дек]]
 
* [[Персистентный дек]]
−
* [[Мажорирующий элемент]]
+
* [[Персистентная приоритетная очередь]]
−
* [[Счетчик Кнута]]
 
−
 
 
−
== Приоритетные очереди ==
 
  
 +
== [[Приоритетные очереди]] ==
 
* [[Двоичная куча]]
 
* [[Двоичная куча]]
 
* [[Биномиальная куча]]
 
* [[Биномиальная куча]]
Строка 164: Строка 209:
 
* [[Тонкая куча]]
 
* [[Тонкая куча]]
 
* [[Толстая куча на избыточном счетчике]]
 
* [[Толстая куча на избыточном счетчике]]
−
* [[Куча Бродала-Окасаки]]
+
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
  
 
== Система непересекающихся множеств ==
 
== Система непересекающихся множеств ==
Строка 170: Строка 215:
 
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 +
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
  
−
== Поисковые структуры данных ==
+
== [[Поисковые структуры данных]] ==
 
* [[Упорядоченное множество]]
 
* [[Упорядоченное множество]]
 
* [[Дерево поиска, наивная реализация]]
 
* [[Дерево поиска, наивная реализация]]
Строка 181: Строка 227:
 
* [[Декартово дерево по неявному ключу]]
 
* [[Декартово дерево по неявному ключу]]
 
* [[Splay-дерево]]
 
* [[Splay-дерево]]
 +
* [[Взвешенное дерево]]
 +
* [[Tango-дерево]]<tex>^\star</tex>
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Дерево ван Эмде Боаса]]
 
* [[Дерево ван Эмде Боаса]]
 
* [[Список с пропусками]]
 
* [[Список с пропусками]]
−
* [[Fusion tree]]
+
* [[Fusion tree]]<tex>^\star</tex>
 
* [[Сверхбыстрый цифровой бор]]
 
* [[Сверхбыстрый цифровой бор]]
 +
* [[Rope]]<tex>^\star</tex>
 +
* [[AA-дерево]]<tex>^\star</tex>
  
 
== Дерево отрезков ==
 
== Дерево отрезков ==
−
 
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 
* [[Дерево отрезков. Построение]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков сверху]]
Строка 208: Строка 258:
 
* [[Хеширование кукушки]]
 
* [[Хеширование кукушки]]
 
* [[Идеальное хеширование]]
 
* [[Идеальное хеширование]]
−
* [[Перехеширование. Амортизационный анализ]]
+
* [[Перехеширование]]
 
* [[Фильтр Блума]]
 
* [[Фильтр Блума]]
 +
* [[Quotient filter]]<tex>^\star</tex>
 
* [[Универсальное семейство хеш-функций]]
 
* [[Универсальное семейство хеш-функций]]
 +
* [[Расширяемое хеширование]]<tex>^\star</tex>
  
−
== [[Сортировка]] ==
+
== [[Сортировки]] ==
 +
=== Квадратичные сортировки ===
 
* [[Сортировка выбором]]
 
* [[Сортировка выбором]]
 
* [[Сортировка пузырьком]]
 
* [[Сортировка пузырьком]]
 
* [[Сортировка вставками]]
 
* [[Сортировка вставками]]
−
* [[Сортировка Шелла]]
+
=== Сортировки на сравнениях ===
 +
* [[Сортировка Шелла]]<tex>^\star</tex>
 
* [[Сортировка кучей]]
 
* [[Сортировка кучей]]
 
* [[Быстрая сортировка]]
 
* [[Быстрая сортировка]]
 
* [[Сортировка слиянием]]
 
* [[Сортировка слиянием]]
 
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
 
* [[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>
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом]]
−
* [[Сортировка подсчетом сложных объектов]]
 
 
* [[Цифровая сортировка]]
 
* [[Цифровая сортировка]]
 
* [[Карманная сортировка]]
 
* [[Карманная сортировка]]
−
* [[Поиск k-ой порядковой статистики]]
+
* [[Сортировка Хана]]<tex>^\star</tex>
−
* [[Поиск k-ой порядковой статистики за линейное время]]
+
* [[Задача флага Нидерландов]]<tex>^\star</tex>
−
* [[Сортировка Хана]]
+
* [[Блинная сортировка]]<tex>^\star</tex>
−
* [[Timsort]]
 
  
 
== Сортирующие сети ==
 
== Сортирующие сети ==
 
* [[Сортирующие сети]]
 
* [[Сортирующие сети]]
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
−
* [[Сортировочные сети с особыми свойствами]]
 
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сортирующие сети для квадратичных сортировок]]
 +
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 
* [[Сеть Бетчера]]
 
* [[Сеть Бетчера]]
  
 
== Алгоритмы поиска ==
 
== Алгоритмы поиска ==
 
* [[Целочисленный двоичный поиск]]
 
* [[Целочисленный двоичный поиск]]
 +
* [[Поиск в матрице]]<tex>^\star</tex>
 
* [[Вещественный двоичный поиск]]
 
* [[Вещественный двоичный поиск]]
 
* [[Троичный поиск]]
 
* [[Троичный поиск]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Интерполяционный поиск]]
 
* [[Интерполяционный поиск]]
 +
* [[Метод Фибоначчи]]<tex>^\star</tex>
  
 
== Связь между структурами данных ==
 
== Связь между структурами данных ==
Строка 256: Строка 321:
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Матрица смежности графа]]
 
* [[Матрица смежности графа]]
−
* [[Связь степени матрицы смежности и количества путей]]
 
 
* [[Матрица инцидентности графа]]
 
* [[Матрица инцидентности графа]]
−
* [[Циклическое пространство графа]]
+
* [[Циклическое пространство графа]]<tex>^\star</tex>
−
* [[Фундаментальные циклы графа]]
+
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
 
* [[Дерево, эквивалентные определения]]
 
* [[Дерево, эквивалентные определения]]
 +
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 +
* [[Двудольные графы]]
 
* [[Дополнительный, самодополнительный граф]]
 
* [[Дополнительный, самодополнительный граф]]
−
* [[Диаметр дерева]]
+
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 +
* [[Рёберное ядро]]
 +
* [[Факторизация графов]]<tex>^\star</tex>
 +
* [[Группы графов]]<tex>^\star</tex>
 +
* [[Гиперграфы]]<tex>^\star</tex>
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 268: Строка 338:
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 +
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Мост, эквивалентные определения]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф блоков-точек сочленения]]
 
* [[Граф блоков-точек сочленения]]
−
* [[Точка сочленения, эквивалентные определения]]
 
−
* [[Мост, эквивалентные определения]]
 
 
* [[k-связность]]
 
* [[k-связность]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
  
 
== Остовные деревья ==
 
== Остовные деревья ==
 +
=== Построение остовных деревьев ===
 +
* [[Остовные деревья: определения, лемма о безопасном ребре]]
 +
* [[Алгоритм Прима]]
 +
* [[Алгоритм Краскала]]
 +
* [[Алгоритм Борувки]]
 +
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 +
* [[Алгоритм двух китайцев]]
 +
* [[Минимально узкое остовное дерево]]
 +
* [[Остовное дерево в планарном графе]]
 +
 +
=== Свойства остовных деревьев ===
 
* [[Матрица Кирхгофа]]
 
* [[Матрица Кирхгофа]]
 
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
 
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
Строка 285: Строка 367:
  
 
== Обходы графов ==
 
== Обходы графов ==
 +
=== Эйлеровы графы ===
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
−
* [[Покрытие ребер графа путями]]
+
* [[Покрытие рёбер графа путями]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 +
 +
=== Гамильтоновы графы ===
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
 
* [[Теорема Хватала]]
 
* [[Теорема Хватала]]
 
* [[Теорема Дирака]]
 
* [[Теорема Дирака]]
 
* [[Теорема Оре]]
 
* [[Теорема Оре]]
 +
* [[Теорема Поша]]<tex>^\star</tex>
 +
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
 
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 +
* [[Теорема Гринберга]]<tex>^\star</tex>
 
* [[Турниры]]
 
* [[Турниры]]
 
* [[Теорема Редеи-Камиона]]
 
* [[Теорема Редеи-Камиона]]
Строка 305: Строка 394:
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Теорема Вагнера]]
 +
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Двойственный граф планарного графа]]
 
* [[Двойственный граф планарного графа]]
−
* [[Теорема Фари]]
+
* [[Теорема Фари]]<tex>^\star</tex>
 +
* [[Гамма-алгоритм]]
 +
* [[Разрез в планарных графах]]
  
 
== Раскраски графов ==
 
== Раскраски графов ==
Строка 312: Строка 405:
 
* [[Двудольные графы и раскраска в 2 цвета]]
 
* [[Двудольные графы и раскраска в 2 цвета]]
 
* [[Хроматический многочлен]]
 
* [[Хроматический многочлен]]
−
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
 
−
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
 
−
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
 
−
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
 
−
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
 
 
* [[Формула Зыкова]]
 
* [[Формула Зыкова]]
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 
* [[Теорема Брукса]]
 
* [[Теорема Брукса]]
−
* [[Верхние и нижние оценки хроматического числа]]
+
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 
* [[Хроматическое число планарного графа]]
 
* [[Хроматическое число планарного графа]]
 +
* [[Многочлен Татта]]<tex>^\star</tex>
 +
* [[Теория Рамсея]]<tex>^\star</tex>
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 327: Строка 417:
 
* [[Лемма о белых путях]]
 
* [[Лемма о белых путях]]
 
* [[Использование обхода в глубину для проверки связности]]
 
* [[Использование обхода в глубину для проверки связности]]
−
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
+
* [[Использование обхода в глубину для поиска цикла]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
Строка 339: Строка 429:
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Дейкстры]]
−
* [[Алгоритм Левита]] '''(в процессе написания)'''
 
 
* [[Алгоритм Флойда]]
 
* [[Алгоритм Флойда]]
−
* [[Алгоритм A*]]
 
 
* [[Алгоритм Джонсона]]
 
* [[Алгоритм Джонсона]]
−
* [[Эвристики для поиска кратчайших путей]] '''(в процессе написания)'''
+
* [[Алгоритм Левита]]<tex>^\star</tex>
−
 
+
* [[Алгоритм A*]] <tex>^\star</tex>
−
== Построение остовных деревьев ==
+
* [[Алгоритм D*]] <tex>^\star</tex>
−
* [[Лемма о безопасном ребре]]
+
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
−
* [[Алгоритм Прима]]
 
−
* [[Алгоритм Краскала]]
 
−
* [[Алгоритм Борувки]]
 
−
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
−
* [[Алгоритм двух китайцев]]
 
  
 
== Задача о паросочетании ==
 
== Задача о паросочетании ==
−
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
+
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
Строка 360: Строка 443:
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь вершинного покрытия и независимого множества]]
 
* [[Связь вершинного покрытия и независимого множества]]
 +
* [[Рёберное ядро]]<tex>^\star</tex>
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
−
* [[Декомпозиция Эдмондса-Галлаи]] (в разработке)
+
* [[Декомпозиция Эдмондса-Галлаи]]
 +
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 +
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 369: Строка 455:
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Дополняющая сеть, дополняющий путь]]
 
* [[Дополняющая сеть, дополняющий путь]]
−
* [[Лемма о сложении потоков]]
+
* [[Сложение и разность потоков]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
Строка 377: Строка 463:
 
* [[Схема алгоритма Диница]]
 
* [[Схема алгоритма Диница]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 +
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Метод проталкивания предпотока]]
 
* [[Метод проталкивания предпотока]]
Строка 383: Строка 470:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
−
* [[Алгоритм Каргера для нахождения минимального разреза]]
+
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 +
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 +
* [[Примеры сведения к задачам поиска потока]]
  
 
== Задача о потоке минимальной стоимости ==
 
== Задача о потоке минимальной стоимости ==
Строка 393: Строка 482:
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
  
 
= Четвертый семестр =
 
= Четвертый семестр =
Строка 401: Строка 491:
 
* [[Слово Фибоначчи]]
 
* [[Слово Фибоначчи]]
 
* [[Слово Туэ-Морса]]
 
* [[Слово Туэ-Морса]]
 +
* [[Декомпозиция Линдона]]<tex>^\star</tex>
 +
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
 +
* [[Алгоритм Крочемора]]<tex>^\star</tex>
 +
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 +
* [[Алгоритм Манакера]]<tex>^\star</tex>
 +
* [[Дерево палиндромов]]<tex>^\star</tex>
  
−
== Поиск подстроки в строке ==
+
== [[Поиск подстроки в строке]] ==
 +
=== Точный поиск ===
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
Строка 408: Строка 505:
 
* [[Префикс-функция]]
 
* [[Префикс-функция]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
 
* [[Алгоритм Кнута-Морриса-Пратта]]
 +
* [[Автомат Кнута-Морриса-Пратта]]
 
* [[Z-функция]]
 
* [[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>
  
 
== Суффиксное дерево ==
 
== Суффиксное дерево ==
Строка 417: Строка 526:
 
* [[Сжатое суффиксное дерево]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Алгоритм Укконена]]
 
* [[Алгоритм Укконена]]
 +
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
 +
* [[Алгоритм Фарача]]<tex>^\star</tex>
  
 
== Суффиксный массив ==
 
== Суффиксный массив ==
 
* [[Суффиксный массив]]
 
* [[Суффиксный массив]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
−
* [[Цифровая сортировка]]
 
 
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
* [[Алгоритм Касаи и др.]]
 
* [[Алгоритм Касаи и др.]]
 
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 +
* [[Количество подпалиндромов в строке]]<tex>^\star</tex>
  
 
== Задача о наименьшем общем предке ==
 
== Задача о наименьшем общем предке ==
 +
* [[Алгоритм Мо]]
 +
* [[Сведение задачи LCA к задаче RMQ]]
 +
* [[Сведение задачи RMQ к задаче LCA]]
 
* [[Метод двоичного подъема]]
 
* [[Метод двоичного подъема]]
−
* [[Сведение задачи LCA к задаче RMQ]]
 
 
* [[Решение RMQ с помощью разреженной таблицы]]
 
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Двумерная разреженная таблица]]
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
−
* [[Алгоритм Шибера-Вишкина]]
+
* [[Алгоритм Хьюи]]
−
* [[Сведение задачи RMQ к задаче LCA]]
+
* [[Heavy-light декомпозиция]]
 +
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
 +
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
 +
* [[Link-Cut Tree]]<tex>^\star</tex>
 +
* [[Rake-Compress деревья]]<tex>^\star</tex>
  
 
== Матроиды ==
 
== Матроиды ==
 +
=== Основные факты теории матроидов ===
 
* [[Определение матроида]]
 
* [[Определение матроида]]
 
* [[Примеры матроидов]]
 
* [[Примеры матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
−
* [[Жадный алгоритм поиска базы минимального веса]]
 
 
* [[Теорема о базах]]
 
* [[Теорема о базах]]
 
* [[Аксиоматизация матроида базами]]
 
* [[Аксиоматизация матроида базами]]
Строка 446: Строка 564:
 
* [[Аксиоматизация матроида циклами]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Ранговая функция, полумодулярность]]
 +
* [[Аксиоматизация матроида рангами]]
 
* [[Двойственный матроид]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Оператор замыкания для матроидов]]
 +
* [[Покрытия, закрытые множества]]
 +
* [[Матроид Вамоса]]<tex>^\star</tex>
 +
 
=== Пересечение матроидов ===
 
=== Пересечение матроидов ===
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]
−
* [[Лемма о паросочетании в графе замен]]
+
* [[Граф замен]]
−
* [[Лемма о единственном паросочетании в графе замен]]
 
−
* [[Граф замен для двух матроидов]]
 
−
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
−
* [[Теорема Эдмондса-Лоулера]]
+
 
 
=== Объединение матроидов ===
 
=== Объединение матроидов ===
 
* [[Объединение матроидов, проверка множества на независимость]]
 
* [[Объединение матроидов, проверка множества на независимость]]
Строка 462: Строка 581:
  
 
== Теория расписаний ==
 
== Теория расписаний ==
 +
=== Общая теория ===
 
* [[Классификация задач]]
 
* [[Классификация задач]]
 
* [[Методы решения задач теории расписаний]]
 
* [[Методы решения задач теории расписаний]]
 
* [[Правило Лаулера]]
 
* [[Правило Лаулера]]
−
* [[Flow shop]]
+
 
−
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
+
=== Задачи с одним станком ===
 +
* [[1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
 +
* [[1sumwu|<tex> 1 \mid\mid \sum w_i U_i </tex>]]
 +
* [[1sumwT|<tex> 1 \mid\mid \sum w_i T_i </tex>]]
 +
* [[1p1sumu|<tex>1 \mid p_{i} = 1 \mid \sum U_{i}</tex>]]
 +
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
 +
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
 
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
 
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
−
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
+
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]]
 +
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
 +
* [[1ripippmtnsumwu| <tex> 1 \mid r_i,p_i=p, pmtn \mid \sum w_i U_i</tex>]]
 +
* [[1ripmtnsumwu|<tex>1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex>]]
 
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
 
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
−
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
 
 
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
 
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
 
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
 
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
 +
 +
=== Специальные случаи задач для двух станков ===
 
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
 
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
 +
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
 +
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
 +
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
 +
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]
 +
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
 +
 +
=== Задачи для произвольного числа станков ===
 +
* [[Flow shop]]
 +
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
 +
* [[PSumCi|<tex>P \mid \mid \sum C_{i}</tex>]]
 +
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
 
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
 
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
 +
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]
 +
* [[Ppi1riintegerLmax|<tex>P \mid p_i=1; r_i - integer \mid L_{max}</tex>]]
 +
* [[RSumCi|<tex>R \mid \mid \sum C_i</tex>]]
 +
* [[RpmtnCmax|<tex>R \mid pmtn \mid C_{max}</tex>]]
 
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
 
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
 +
* [[QpmtnSumCi|<tex> Q \mid pmtn \mid \sum C_i </tex>]]
 
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
 
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
 
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
 
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
−
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
 
−
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
 
−
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
 
−
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
 
 
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
 
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
−
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
+
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]
−
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
+
* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]]
 +
* [[Opij1SumTi|<tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>]]
 +
* [[Opij1Cmax|<tex> O \mid p_{ij} = 1 \mid C_{max} </tex>]]
 +
* [[Opij1Sumwc|<tex> O \mid p_{ij} = 1 \mid \sum w_i C_i </tex>]]

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

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

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

Содержание

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

Отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Точный поиск

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

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

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

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

Матроиды

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

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

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

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

Общая теория

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

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

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

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