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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Задача о паросочетании)
м (Откат правок 93.85.153.53 (обсуждение) к версии Vitalik)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показано 285 промежуточных версий 84 участников)
Строка 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>
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 328: Строка 417:
 
* [[Лемма о белых путях]]
 
* [[Лемма о белых путях]]
 
* [[Использование обхода в глубину для проверки связности]]
 
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
+
* [[Использование обхода в глубину для поиска цикла]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
Строка 340: Строка 429:
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Дейкстры]]
* [[Алгоритм Левита]] '''(в процессе написания)'''
 
 
* [[Алгоритм Флойда]]
 
* [[Алгоритм Флойда]]
* [[Алгоритм A*]]
 
 
* [[Алгоритм Джонсона]]
 
* [[Алгоритм Джонсона]]
* [[Эвристики для поиска кратчайших путей]] '''(в процессе написания)'''
+
* [[Алгоритм Левита]]<tex>^\star</tex>
 
+
* [[Алгоритм A*]] <tex>^\star</tex>
== Построение остовных деревьев ==
+
* [[Алгоритм D*]] <tex>^\star</tex>
* [[Лемма о безопасном ребре]]
+
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
* [[Алгоритм Прима]]
 
* [[Алгоритм Краскала]]
 
* [[Алгоритм Борувки]]
 
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
* [[Алгоритм двух китайцев]]
 
  
 
== Задача о паросочетании ==
 
== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
+
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
Строка 361: Строка 443:
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь вершинного покрытия и независимого множества]]
 
* [[Связь вершинного покрытия и независимого множества]]
 +
* [[Рёберное ядро]]<tex>^\star</tex>
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]] (в разработке)
+
* [[Декомпозиция Эдмондса-Галлаи]]
 +
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 +
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 370: Строка 455:
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Дополняющая сеть, дополняющий путь]]
 
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
+
* [[Сложение и разность потоков]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
Строка 378: Строка 463:
 
* [[Схема алгоритма Диница]]
 
* [[Схема алгоритма Диница]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 +
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
* [[Метод проталкивания предпотока]]
 
* [[Метод проталкивания предпотока]]
Строка 384: Строка 470:
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
* [[Алгоритм Каргера для нахождения минимального разреза]]
+
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
 +
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
 +
* [[Примеры сведения к задачам поиска потока]]
  
 
== Задача о потоке минимальной стоимости ==
 
== Задача о потоке минимальной стоимости ==
Строка 394: Строка 482:
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
  
 
= Четвертый семестр =
 
= Четвертый семестр =
Строка 402: Строка 491:
 
* [[Слово Фибоначчи]]
 
* [[Слово Фибоначчи]]
 
* [[Слово Туэ-Морса]]
 
* [[Слово Туэ-Морса]]
 +
* [[Декомпозиция Линдона]]<tex>^\star</tex>
 +
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
 +
* [[Алгоритм Крочемора]]<tex>^\star</tex>
 +
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 +
* [[Алгоритм Манакера]]<tex>^\star</tex>
 +
* [[Дерево палиндромов]]<tex>^\star</tex>
  
== Поиск подстроки в строке ==
+
== [[Поиск подстроки в строке]] ==
 +
=== Точный поиск ===
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
Строка 409: Строка 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>
  
 
== Суффиксное дерево ==
 
== Суффиксное дерево ==
Строка 418: Строка 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>
  
 
== Матроиды ==
 
== Матроиды ==
 +
=== Основные факты теории матроидов ===
 
* [[Определение матроида]]
 
* [[Определение матроида]]
 
* [[Примеры матроидов]]
 
* [[Примеры матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Жадный алгоритм поиска базы минимального веса]]
 
 
* [[Теорема о базах]]
 
* [[Теорема о базах]]
 
* [[Аксиоматизация матроида базами]]
 
* [[Аксиоматизация матроида базами]]
Строка 447: Строка 564:
 
* [[Аксиоматизация матроида циклами]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Ранговая функция, полумодулярность]]
 +
* [[Аксиоматизация матроида рангами]]
 
* [[Двойственный матроид]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Оператор замыкания для матроидов]]
 +
* [[Покрытия, закрытые множества]]
 +
* [[Матроид Вамоса]]<tex>^\star</tex>
 +
 
=== Пересечение матроидов ===
 
=== Пересечение матроидов ===
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
+
* [[Граф замен]]
* [[Лемма о единственном паросочетании в графе замен]]
 
* [[Граф замен для двух матроидов]]
 
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Теорема Эдмондса-Лоулера]]
+
 
 
=== Объединение матроидов ===
 
=== Объединение матроидов ===
 
* [[Объединение матроидов, проверка множества на независимость]]
 
* [[Объединение матроидов, проверка множества на независимость]]
Строка 463: Строка 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>]]

Текущая версия на 20:45, 12 марта 2018

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

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

Содержание

Первый семестр[править]

Отношения[править]

Булевы функции[править]

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

Представление информации[править]

Алгоритмы сжатия[править]

Комбинаторика[править]

Комбинаторные объекты[править]

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

Подсчёт числа объектов[править]

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

Динамическое программирование[править]

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

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

Другие задачи[править]

Теория вероятностей[править]

Марковские цепи[править]

Второй семестр[править]

Амортизационный анализ[править]

Персистентные структуры данных[править]

Приоритетные очереди[править]

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

Поисковые структуры данных[править]

Дерево отрезков[править]

Дерево Фенвика[править]

Хеширование[править]

Сортировки[править]

Квадратичные сортировки[править]

Сортировки на сравнениях[править]

Многопоточные сортировки[править]

Другие сортировки[править]

Сортирующие сети[править]

Алгоритмы поиска[править]

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

Третий семестр[править]

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

Связность в графах[править]

Остовные деревья[править]

Построение остовных деревьев[править]

Свойства остовных деревьев[править]

Обходы графов[править]

Эйлеровы графы[править]

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

Укладки графов[править]

Раскраски графов[править]

Обход в глубину[править]

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

Задача о паросочетании[править]

Задача о максимальном потоке[править]

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

Четвертый семестр[править]

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

Поиск подстроки в строке[править]

Точный поиск[править]

Нечёткий поиск[править]

Суффиксное дерево[править]

Суффиксный массив[править]

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

Матроиды[править]

Основные факты теории матроидов[править]

Пересечение матроидов[править]

Объединение матроидов[править]

Теория расписаний[править]

Общая теория[править]

Задачи с одним станком[править]

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

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