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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Система непересекающихся множеств)
м (rollbackEdits.php mass rollback)
 
(не показаны 465 промежуточные версии, сделанные более чем 100 участниками)
Строка 1: Строка 1:
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 +
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
  
−
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].
+
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
  
 
= Первый семестр =
 
= Первый семестр =
Строка 8: Строка 9:
 
== Отношения ==
 
== Отношения ==
 
*[[Определение отношения]]
 
*[[Определение отношения]]
−
*[[Степень отношений]]
+
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
 
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
*[[Симметричное отношение]]
 
*[[Симметричное отношение]]
 
*[[Антисимметричное отношение]]
 
*[[Антисимметричное отношение]]
−
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
 
 
*[[Транзитивное отношение]]
 
*[[Транзитивное отношение]]
−
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
 
*[[Отношение порядка]]
 
*[[Отношение порядка]]
 +
*[[Изоморфизмы упорядоченных множеств]]<tex>^\star</tex>
 
*[[Отношение эквивалентности]]
 
*[[Отношение эквивалентности]]
 +
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 +
*[[Транзитивный остов]]
  
 
== Булевы функции ==
 
== Булевы функции ==
 
*[[Определение булевой функции]]
 
*[[Определение булевой функции]]
 +
*[[Побитовые операции]]<tex>^\star</tex>
 
*[[Суперпозиции]]
 
*[[Суперпозиции]]
 
*[[ДНФ]]
 
*[[ДНФ]]
 +
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
 
*[[КНФ]]
 
*[[КНФ]]
−
*[[Полином Жегалкина]]
+
*[[2-SAT]]
 +
*[[XOR-SAT]]<tex>^\star</tex>
 +
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 +
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
−
*[[Сокращенная и минимальная ДНФ]]
 
−
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
 
−
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
−
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
 
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Пороговая функция]]
 
*[[Пороговая функция]]
 +
*[[Троичная логика]]<tex>^\star</tex>
  
 
== Схемы из функциональных элементов ==
 
== Схемы из функциональных элементов ==
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 +
*[[Простейшие методы синтеза схем из функциональных элементов]]
 +
*[[Метод Лупанова синтеза схем]]
 
*[[Cумматор]]
 
*[[Cумматор]]
 
*[[Каскадный сумматор]]
 
*[[Каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
 +
*[[Троичный сумматор]]<tex>^\star</tex>
 
*[[Реализация вычитания сумматором]]
 
*[[Реализация вычитания сумматором]]
 
*[[Матричный умножитель]]
 
*[[Матричный умножитель]]
 
*[[Дерево Уоллеса]]
 
*[[Дерево Уоллеса]]
 +
*[[Контактная схема]]
 +
*[[Триггеры]]<tex>^\star</tex>
 +
*[[Квантовые гейты]]<tex>^\star</tex>
  
 
== Представление информации ==
 
== Представление информации ==
Строка 46: Строка 56:
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление вещественных чисел]]
 
*[[Представление вещественных чисел]]
−
*[[Представление символов, таблицы кодировок]]
+
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
  
 
== Алгоритмы сжатия ==
 
== Алгоритмы сжатия ==
−
*[[Алгоритм Хаффмана]]
+
* [[Алгоритм Хаффмана]]
−
*[[Алгоритм LZW]]
+
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
−
*[[Алгоритмы LZ77 и LZ78]]
+
* [[Алгоритм Хаффмана за O(n)]]
−
*[[Преобразование Барроуза-Уиллера]]
+
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
−
*[[Обратное преобразование Барроуза-Уиллера]]
+
* [[Неравенство Крафта]]
−
*[[Преобразование MTF]]
+
* [[Неравенство Макмиллана]]
−
*[[Расстояние Хэмминга]]
+
* [[Код Шеннона]]
−
*[[Избыточное кодирование, код Хэмминга]]
+
* [[Оптимальный префиксный код с длиной кодового слова не более 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>
 +
*[[Динамика по поддеревьям]]
  
 
== Теория вероятностей ==
 
== Теория вероятностей ==
Строка 102: Строка 150:
 
*[[Независимые события]]
 
*[[Независимые события]]
 
*[[Условная вероятность]]
 
*[[Условная вероятность]]
 +
*[[Формула полной вероятности]]
 
*[[Формула Байеса]]
 
*[[Формула Байеса]]
−
*[[Формула полной вероятности]]
 
 
*[[Дискретная случайная величина]]
 
*[[Дискретная случайная величина]]
 
*[[Независимые случайные величины]]
 
*[[Независимые случайные величины]]
 
*[[Математическое ожидание случайной величины]]
 
*[[Математическое ожидание случайной величины]]
 +
*[[Дисперсия случайной величины]]
 
*[[Ковариация случайных величин]]
 
*[[Ковариация случайных величин]]
−
*[[Дисперсия случайной величины]]
+
*[[Корреляция случайных величин]]
 +
*[[Неравенство Маркова]]
 
*[[Энтропия случайного источника]]
 
*[[Энтропия случайного источника]]
 
*[[Симуляция одним распределением другого]]
 
*[[Симуляция одним распределением другого]]
 
*[[Арифметическое кодирование]]
 
*[[Арифметическое кодирование]]
−
*[[Задача о двух конвертах]]
+
*[[Парадоксы теории вероятностей]]<tex>^\star</tex>
 +
*[[Схема Бернулли]]<tex>^\star</tex>
  
−
== [[Марковская цепь|Марковские цепи]] ==
+
== Марковские цепи ==
  
 +
* [[Марковская цепь]]
 
* [[Теорема о поглощении]]
 
* [[Теорема о поглощении]]
 
* [[Фундаментальная матрица]]
 
* [[Фундаментальная матрица]]
Строка 122: Строка 174:
 
* [[Эргодическая марковская цепь]]
 
* [[Эргодическая марковская цепь]]
 
* [[Регулярная марковская цепь]]
 
* [[Регулярная марковская цепь]]
 +
* [[Примеры использования Марковских цепей]]
 +
* [[Скрытые Марковские модели]]<tex>^\star</tex>
 +
* [[Алгоритм Витерби]]<tex>^\star</tex>
 +
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
 +
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>
  
 
= Второй семестр =
 
= Второй семестр =
Строка 127: Строка 184:
 
== Амортизационный анализ ==
 
== Амортизационный анализ ==
 
* [[Амортизационный анализ]]
 
* [[Амортизационный анализ]]
−
* [[Саморасширяющийся массив]]
+
* [[Динамический массив]]
−
* [[Массив с увеличением/уменьшением размера]]
+
* [[Hashed Array Tree]]<tex>^\star</tex>
 +
* [[Список]]
 
* [[Стек]]
 
* [[Стек]]
 
* [[Очередь]]
 
* [[Очередь]]
−
* [[Список]]
+
* [[Дек]]
 +
* [[Мажорирующий элемент]]
 +
* [[Счетчик Кнута]]
 +
* [[Мастер-теорема]]<tex>^\star</tex>
 +
* [[List order maintenance]]<tex>^\star</tex>
 +
 
 +
== Персистентные структуры данных ==
 +
* [[Персистентные структуры данных]]
 
* [[Персистентный стек]]
 
* [[Персистентный стек]]
 +
* [[Персистентная очередь]]
 
* [[Персистентный дек]]
 
* [[Персистентный дек]]
 +
* [[Персистентная приоритетная очередь]]
  
−
== Приоритетные очереди ==
+
== [[Приоритетные очереди]] ==
−
 
 
 
* [[Двоичная куча]]
 
* [[Двоичная куча]]
 
* [[Биномиальная куча]]
 
* [[Биномиальная куча]]
 
* [[Фибоначчиева куча]]
 
* [[Фибоначчиева куча]]
 +
* [[Левосторонняя куча]]
 +
* [[Тонкая куча]]
 +
* [[Толстая куча на избыточном счетчике]]
 +
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>
  
 
== Система непересекающихся множеств ==
 
== Система непересекающихся множеств ==
 
* [[СНМ (наивные реализации) | Наивные реализации]]
 
* [[СНМ (наивные реализации) | Наивные реализации]]
−
* [[СНМ(списки с весовой эвристикой) | Списки с весовой эвристикой]]
+
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
 
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
−
* [[Анализ реализации с ранговой эвристикой  | Анализ реализации с ранговой эвристикой]]
+
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>
  
−
== Деревья поиска ==
+
== [[Поисковые структуры данных]] ==
 
* [[Упорядоченное множество]]
 
* [[Упорядоченное множество]]
 
* [[Дерево поиска, наивная реализация]]
 
* [[Дерево поиска, наивная реализация]]
Строка 155: Строка 225:
 
* [[Красно-черное дерево]]
 
* [[Красно-черное дерево]]
 
* [[Декартово дерево]]
 
* [[Декартово дерево]]
 +
* [[Декартово дерево по неявному ключу]]
 
* [[Splay-дерево]]
 
* [[Splay-дерево]]
−
* [[Декартово дерево по неявному ключу]]
+
* [[Взвешенное дерево]]
 +
* [[Tango-дерево]]<tex>^\star</tex>
 +
* [[Рандомизированное бинарное дерево поиска]]
 
* [[Дерево ван Эмде Боаса]]
 
* [[Дерево ван Эмде Боаса]]
 +
* [[Список с пропусками]]
 +
* [[Fusion tree]]<tex>^\star</tex>
 +
* [[Сверхбыстрый цифровой бор]]
 +
* [[Rope]]<tex>^\star</tex>
 +
* [[AA-дерево]]<tex>^\star</tex>
  
 
== Дерево отрезков ==
 
== Дерево отрезков ==
−
 
 
* [[Статистики на отрезках. Корневая эвристика]]
 
* [[Статистики на отрезках. Корневая эвристика]]
 +
* [[Корневая декомпозиция с операциями: get, insert, erase]]
 
* [[Дерево отрезков. Построение]]
 
* [[Дерево отрезков. Построение]]
 
* [[Реализация запроса в дереве отрезков сверху]]
 
* [[Реализация запроса в дереве отрезков сверху]]
Строка 176: Строка 254:
  
 
== Хеширование ==
 
== Хеширование ==
−
* [[Хеширование]]
+
* [[Хеш-таблица]]
−
* [[Открытое и закрытое хеширование]]
+
* [[Разрешение коллизий]]
−
* [[Поиск свободного места при закрытом хешировании]]
 
 
* [[Хеширование кукушки]]
 
* [[Хеширование кукушки]]
−
* [[Двойное хеширование]]
+
* [[Идеальное хеширование]]
−
* [[Перехеширование. Амортизационный анализ]]
+
* [[Перехеширование]]
 
* [[Фильтр Блума]]
 
* [[Фильтр Блума]]
 +
* [[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-ой порядковой статистики]]
+
* [[Карманная сортировка]]
−
* [[Поиск k-й порядковой статистики за линейное время]]
+
* [[Сортировка Хана]]<tex>^\star</tex>
−
* [[Теорема о нижней оценке для сортировки сравнениями]]
+
* [[Задача флага Нидерландов]]<tex>^\star</tex>
−
* [[Быстрая сортировка]]
+
* [[Блинная сортировка]]<tex>^\star</tex>
  
−
== [[Сортирующие сети]] ==
+
== Сортирующие сети ==
 +
* [[Сортирующие сети]]
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
 
* [[Сортирующие сети для квадратичных сортировок]]
 
* [[Сортирующие сети для квадратичных сортировок]]
 +
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
 
* [[Сеть Бетчера]]
 
* [[Сеть Бетчера]]
  
 
== Алгоритмы поиска ==
 
== Алгоритмы поиска ==
 +
* [[Целочисленный двоичный поиск]]
 +
* [[Поиск в матрице]]<tex>^\star</tex>
 +
* [[Вещественный двоичный поиск]]
 
* [[Троичный поиск]]
 
* [[Троичный поиск]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Поиск с помощью золотого сечения]]
 
* [[Интерполяционный поиск]]
 
* [[Интерполяционный поиск]]
−
* [[Вещественный двоичный поиск]]
+
* [[Метод Фибоначчи]]<tex>^\star</tex>
 +
 
 +
== Связь между структурами данных ==
 +
* [[Связь между структурами данных]]
  
 
= Третий семестр =
 
= Третий семестр =
Строка 217: Строка 321:
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Теорема о существовании простого цикла в случае существования цикла]]
 
* [[Матрица смежности графа]]
 
* [[Матрица смежности графа]]
−
* [[Связь степени матрицы смежности и количества путей]]
 
 
* [[Матрица инцидентности графа]]
 
* [[Матрица инцидентности графа]]
−
* [[Циклическое пространство графа]]
+
* [[Циклическое пространство графа]]<tex>^\star</tex>
−
* [[Фундаментальные циклы графа]]
+
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
 
* [[Дерево, эквивалентные определения]]
 
* [[Дерево, эквивалентные определения]]
 +
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
 +
* [[Двудольные графы]]
 +
* [[Дополнительный, самодополнительный граф]]
 +
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>
 +
* [[Рёберное ядро]]
 +
* [[Факторизация графов]]<tex>^\star</tex>
 +
* [[Группы графов]]<tex>^\star</tex>
 +
* [[Гиперграфы]]<tex>^\star</tex>
  
 
== Связность в графах ==
 
== Связность в графах ==
Строка 227: Строка 338:
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение реберной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 
* [[Отношение вершинной двусвязности]]
 +
* [[Точка сочленения, эквивалентные определения]]
 +
* [[Мост, эквивалентные определения]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф компонент реберной двусвязности]]
 
* [[Граф блоков-точек сочленения]]
 
* [[Граф блоков-точек сочленения]]
−
* [[Точка сочленения, эквивалентные определения]]
 
−
* [[Мост, эквивалентные определения]]
 
 
* [[k-связность]]
 
* [[k-связность]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Теорема Менгера, альтернативное доказательство]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
  
 
== Остовные деревья ==
 
== Остовные деревья ==
 +
=== Построение остовных деревьев ===
 +
* [[Остовные деревья: определения, лемма о безопасном ребре]]
 +
* [[Алгоритм Прима]]
 +
* [[Алгоритм Краскала]]
 +
* [[Алгоритм Борувки]]
 +
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 +
* [[Алгоритм двух китайцев]]
 +
* [[Минимально узкое остовное дерево]]
 +
* [[Остовное дерево в планарном графе]]
 +
 +
=== Свойства остовных деревьев ===
 
* [[Матрица Кирхгофа]]
 
* [[Матрица Кирхгофа]]
 
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
 
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
Строка 244: Строка 367:
  
 
== Обходы графов ==
 
== Обходы графов ==
 +
=== Эйлеровы графы ===
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
−
* [[Покрытие ребер графа путями]]
+
* [[Покрытие рёбер графа путями]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 
* [[Произвольно вычерчиваемые из заданной вершины графы]]
 +
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>
 +
 +
=== Гамильтоновы графы ===
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
 
* [[Теорема Хватала]]
 
* [[Теорема Хватала]]
−
* Следствия теоремы Хватала:
+
* [[Теорема Дирака]]
−
** [[Теорема Дирака]]
 
 
* [[Теорема Оре]]
 
* [[Теорема Оре]]
 +
* [[Теорема Поша]]<tex>^\star</tex>
 +
* [[Теорема Гуйя-Ури]]<tex>^\star</tex>
 +
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 +
* [[Теорема Гринберга]]<tex>^\star</tex>
 
* [[Турниры]]
 
* [[Турниры]]
 
* [[Теорема Редеи-Камиона]]
 
* [[Теорема Редеи-Камиона]]
Строка 264: Строка 394:
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
* [[Теорема Понтрягина-Куратовского]]
 
* [[Теорема Понтрягина-Куратовского]]
 +
* [[Теорема Вагнера]]
 +
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex>
 
* [[Двойственный граф планарного графа]]
 
* [[Двойственный граф планарного графа]]
 +
* [[Теорема Фари]]<tex>^\star</tex>
 +
* [[Гамма-алгоритм]]
 +
* [[Разрез в планарных графах]]
  
 
== Раскраски графов ==
 
== Раскраски графов ==
Строка 270: Строка 405:
 
* [[Двудольные графы и раскраска в 2 цвета]]
 
* [[Двудольные графы и раскраска в 2 цвета]]
 
* [[Хроматический многочлен]]
 
* [[Хроматический многочлен]]
−
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
 
−
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
 
−
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
 
−
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
 
−
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
 
 
* [[Формула Зыкова]]
 
* [[Формула Зыкова]]
 
* [[Формула Уитни]]
 
* [[Формула Уитни]]
 +
* [[Теорема Брукса]]
 +
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
 +
* [[Хроматическое число планарного графа]]
 +
* [[Многочлен Татта]]<tex>^\star</tex>
 +
* [[Теория Рамсея]]<tex>^\star</tex>
  
 
== Обход в глубину ==
 
== Обход в глубину ==
Строка 282: Строка 417:
 
* [[Лемма о белых путях]]
 
* [[Лемма о белых путях]]
 
* [[Использование обхода в глубину для проверки связности]]
 
* [[Использование обхода в глубину для проверки связности]]
−
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
+
* [[Использование обхода в глубину для поиска цикла]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для топологической сортировки]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
 
* [[Использование обхода в глубину для поиска компонент сильной связности]]
Строка 295: Строка 430:
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Флойда]]
 
* [[Алгоритм Флойда]]
−
* [[Алгоритм A*]]
 
 
* [[Алгоритм Джонсона]]
 
* [[Алгоритм Джонсона]]
−
 
+
* [[Алгоритм Левита]]<tex>^\star</tex>
−
== Остовные деревья ==
+
* [[Алгоритм A*]] <tex>^\star</tex>
−
* [[Лемма о безопасном ребре]]
+
* [[Алгоритм D*]] <tex>^\star</tex>
−
* [[Алгоритм Прима]]
+
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
−
* [[Алгоритм Краскала]]
 
−
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
 
−
* [[Алгоритм двух китайцев]]
 
  
 
== Задача о паросочетании ==
 
== Задача о паросочетании ==
−
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
+
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
 
* [[Алгоритм Куна для поиска максимального паросочетания]]
 +
* [[Теорема Холла]]
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
* [[Связь вершинного покрытия и независимого множества]]
 
* [[Связь вершинного покрытия и независимого множества]]
 +
* [[Рёберное ядро]]<tex>^\star</tex>
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 +
* [[Теорема Татта о существовании полного паросочетания]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
 +
* [[Декомпозиция Эдмондса-Галлаи]]
 +
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>
 +
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex>
  
 
== Задача о максимальном потоке ==
 
== Задача о максимальном потоке ==
Строка 318: Строка 455:
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Разрез, лемма о потоке через разрез]]
 
* [[Дополняющая сеть, дополняющий путь]]
 
* [[Дополняющая сеть, дополняющий путь]]
−
* [[Лемма о сложении потоков]]
+
* [[Сложение и разность потоков]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Теорема Форда-Фалкерсона]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
* [[Алоритм Эдмондса-Карпа]]
 
* [[Алоритм Эдмондса-Карпа]]
 +
* [[Алгоритм масштабирования потока]]
 +
* [[Блокирующий поток]]
 +
* [[Схема алгоритма Диница]]
 +
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
 +
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex>
 +
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
 +
* [[Метод проталкивания предпотока]]
 +
* [[Алгоритм "поднять-в-начало"]]
 
* [[Теорема о декомпозиции]]
 
* [[Теорема о декомпозиции]]
 
* [[Теорема о декомпозиционном барьере]]
 
* [[Теорема о декомпозиционном барьере]]
−
* [[Блокирующий поток]]
 
−
* [[Схема алгоритма Диница]]
 
 
* [[Циркуляция потока]]
 
* [[Циркуляция потока]]
−
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
+
* [[Алгоритм Штор-Вагнера нахождения минимального разреза]]
−
* [[Алгоритм масштабирования потока]]
+
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>
−
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
+
* [[Примеры сведения к задачам поиска потока]]
  
 
== Задача о потоке минимальной стоимости ==
 
== Задача о потоке минимальной стоимости ==
Строка 339: Строка 482:
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 
* [[Венгерский алгоритм решения задачи о назначениях]]
 +
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex>
  
 
= Четвертый семестр =
 
= Четвертый семестр =
  
 
== Основные определения. Простые комбинаторные свойства слов ==
 
== Основные определения. Простые комбинаторные свойства слов ==
−
* [[Основные определения связанные со строками]]
+
* [[Основные определения, связанные со строками]]
 
* [[Период и бордер, их связь]]
 
* [[Период и бордер, их связь]]
 
* [[Слово Фибоначчи]]
 
* [[Слово Фибоначчи]]
 
* [[Слово Туэ-Морса]]
 
* [[Слово Туэ-Морса]]
 +
* [[Декомпозиция Линдона]]<tex>^\star</tex>
 +
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
 +
* [[Алгоритм Крочемора]]<tex>^\star</tex>
 +
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
 +
* [[Алгоритм Манакера]]<tex>^\star</tex>
 +
* [[Дерево палиндромов]]<tex>^\star</tex>
  
−
== Поиск подстроки в строке ==
+
== [[Поиск подстроки в строке]] ==
 +
=== Точный поиск ===
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Наивный алгоритм поиска подстроки в строке]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
 
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
Строка 354: Строка 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>
  
−
== Словарные структуры данных ==
+
== Суффиксное дерево ==
 
* [[Суффиксный бор]]
 
* [[Суффиксный бор]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Сжатое суффиксное дерево]]
 
* [[Алгоритм Укконена]]
 
* [[Алгоритм Укконена]]
−
 
+
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
−
== Задача о наименьшем общем предке ==
+
* [[Алгоритм Фарача]]<tex>^\star</tex>
−
* [[Метод двоичного подъема]]
 
−
* [[Сведение задачи LCA к задаче RMQ]]
 
−
* [[Решение RMQ с помощью разреженной таблицы]]
 
−
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)
 
−
* [[Сведение задачи RMQ к задаче LCA]]
 
  
 
== Суффиксный массив ==
 
== Суффиксный массив ==
 
* [[Суффиксный массив]]
 
* [[Суффиксный массив]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
−
* [[Алгоритм цифровой сортировки]]
 
 
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
* [[Алгоритм Касаи и др.]]
 
* [[Алгоритм Касаи и др.]]
−
* [[Алгоритм Каркайнена-Сандерса]]
+
* [[Алгоритм Карккайнена-Сандерса]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 +
* [[Количество подпалиндромов в строке]]<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>
  
 
== Матроиды ==
 
== Матроиды ==
 +
=== Основные факты теории матроидов ===
 
* [[Определение матроида]]
 
* [[Определение матроида]]
 
* [[Примеры матроидов]]
 
* [[Примеры матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
−
* [[Жадный алгоритм поиска базы минимального веса]]
 
 
* [[Теорема о базах]]
 
* [[Теорема о базах]]
 
* [[Аксиоматизация матроида базами]]
 
* [[Аксиоматизация матроида базами]]
Строка 391: Строка 564:
 
* [[Аксиоматизация матроида циклами]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Ранговая функция, полумодулярность]]
 +
* [[Аксиоматизация матроида рангами]]
 
* [[Двойственный матроид]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Оператор замыкания для матроидов]]
 +
* [[Покрытия, закрытые множества]]
 +
* [[Матроид Вамоса]]<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»