http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=95.161.239.161&feedformat=atom
Викиконспекты - Вклад участника [ru]
2024-03-29T10:56:56Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=Pintreepi1Lmax&diff=54184
Pintreepi1Lmax
2016-05-22T15:36:47Z
<p>95.161.239.161: /* Первый шаг */</p>
<hr />
<div><tex dpi = "200">P \mid intree, p_{i} = 1 \mid L_{max}</tex><br />
<br />
{{Задача<br />
|definition=Рассмотрим задачу на нахождение расписания:<br />
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.<br />
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист [[Классификация задач#Характеристики работ|intree-дерева]].<br />
# Любая работа на любом станке выполняется единицу времени.<br />
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>.<br />
}}<br />
<br />
== Описание алгоритма ==<br />
[[Файл:Intree_example.jpg|thumb|Right|Пример intree-дерева]]<br />
=== Идея ===<br />
<br />
Все работы хранятся в качестве вершин [[Классификация задач#Характеристики работ|intree-дерева]], состоящем из <tex>n</tex> вершин, нескольких корней и одного листа. В intree-дереве у одной вершины может быть два и более родителей.<br />
Решение задачи состоит из двух шагов: на первом шаге мы меняем сроки выполнения работ в соответствии с их очередностью.<br />
<br />
# Для всех <tex>i, j</tex> таких, что существует ребро из <tex>i</tex> в <tex>j</tex> будем менять <tex>{d_i}</tex> на <tex>\min ({d_i}, {d_j} - 1) </tex>. <br />
# Работы расставляются в неубывающем порядке сроков.<br />
=== Псевдокод ===<br />
==== Первый шаг ====<br />
Алгоритм изменения сроков:<br />
i = 0<br />
'''for''' k = 1 .. n<br />
'''if''' k.leave == <tex>\varnothing</tex><br />
i = k <font color=green> // такая вершина только одна (intree-дерево) </font> <br />
deque.push(i) <font color=green> // пустой дек </font> <br />
'''while''' deque '''not''' empty<br />
i = deque.remove_first<br />
'''for''' j : i.parents<br />
j.deadline = '''min''' (j.deadline, i.deadline - 1)<br />
stack.add_last(j)<br />
<br />
==== Второй шаг ====<br />
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>.<br />
* В переменной <tex>\mathtt F</tex> хранится время, когда станок освободится.<br />
* В массиве <tex>\mathtt r</tex> хранится информация о максимальном времени завершении обработки родителя.<br />
* Массив <tex>\mathtt q</tex> хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени <tex>t</tex>.<br />
* Массив <tex>\mathtt x</tex> хранит информацию о начале выполнения работы <tex>i</tex>.<br />
<br />
F = 0<br />
'''for''' i = 1 .. n<br />
r[i] = 0<br />
'''for''' t = 0 .. n<br />
q[t] = 0<br />
'''for''' i = 1 .. n<br />
t = '''max''' (r[i], F)<br />
x[i] = t<br />
q[t] = q[t] + 1<br />
'''if''' q[t] == m<br />
F = t + 1<br />
j = i.child()<br />
r[j] = '''max''' (r[j], t + 1)<br />
<br />
=== Доказательство корректности ===<br />
==== Первый шаг ====<br />
{{Лемма<br />
|statement=<br />
Работа с новым сроком <tex>{d'_i}</tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}</tex>.<br />
|proof=<br />
<tex>\Rightarrow </tex><br />
:Т.к. <tex>{d'_i} \leqslant {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.<br />
<br />
<tex>\Leftarrow </tex><br />
:Пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом. <br />
:Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков, причём <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leqslant {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем <tex>{C_n} \leqslant {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leqslant n</tex> мы имеем <tex>{C_n} \leqslant {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leqslant \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex><br />
}}<br />
<br />
==== Второй шаг ====<br />
Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени <tex>t</tex> меньше, чем в момент <tex>t + 1</tex>. Действительно, пусть во время <tex>t</tex> мы выполняем <tex>k</tex> работ, и хотя бы <tex>k + 1 \leqslant m</tex> работ готовы к выполению в момент времени <tex>t + 1</tex>. Но т.к. <tex>k + 1 \leqslant m</tex>, значит каждой из работ предшествовала как минимум одна, поскольку у всех вершин, кроме корней, есть как минимум один предок. Значит, в момент времени <tex>t</tex> исполнялось не менее <tex>k + 1</tex> работ, противоречие.<br />
<br />
{{Лемма<br />
|statement=<br />
Если существует такое расписание, в котором ни одна из работ не будет выполнена с опозданием, то тогда это свойство сохранится в построенном данным алгоритмом расписании<br />
|proof=<br />
Предположим, что существует работа из <tex>x_{1} \dots x_{n}</tex> расписания, построенного алгоритмом. В таком случае существует работа, которая опоздала по отношению к измененным срокам. Возьмем наименьшее <tex>i</tex> такое, что <tex>x(i) + 1 > d'_{i}</tex>. Пусть <tex>t < d'_{i}</tex> {{---}} наибольшее из удовлетворяющих условию <tex>j < m \mid x(j) = t, d'_{j} \leqslant d'_{i}</tex><br />
Такое <tex>t</tex> существует, потому что иначе <tex>m \cdot d'_{i}</tex> работ <tex>j</tex> с <tex>d'_{j} \leqslant d'_{i}</tex> находятся в очереди до <tex>d'_{i}</tex>. Работа <tex>i</tex> к ним не принадлежит, поскольку <tex>x(i) + 1 > d'_{i}</tex>, а значит, что <tex>m \cdot d'_{i} + 1</tex> должны быть в очереди в момент времени <tex>0 \dots d'_{i}</tex> и ни одна работа не должна опаздывать. Противоречие.<br />
Любая работа <tex>j</tex> с <tex>d'_{j} \leqslant d'_{i} </tex> и <tex> x(j) > t </tex> должна иметь предка, начавшего работать в момент времени <tex>t</tex>. Теперь рассмотрим два случая:<br />
<br />
'''Первый случай:''' <tex>t = d'_{i} - 1</tex>.<br />
<br />
:Мы имеем <tex>x(i)>d'_{i}-1 = t</tex>. Таким образом, предок <tex>k</tex> работы <tex>i</tex> должен начать работать во время <tex>t</tex> и закончить в <tex>d'_{i}</tex>. Но т.к. <tex>d'_{k} \leqslant d'_{i} - 1 < d'_{i} = x(k) + 1</tex>, работа <tex>k</tex> так же опоздает, однако <tex>i</tex> было выбрано минимальным. Противоречие.<br />
<br />
'''Второй случай:''' <tex>t < d'_{i} - 1</tex>.<br />
<br />
:В этом случае <tex>m</tex> работ <tex>j</tex> таких, что <tex>d'_{j} \leqslant d'_{i}</tex> начнут работать в момент времени <tex>t + 1</tex>, каждая из которых имеет как минимум работающего в <tex>t</tex> предка. По структуре дерева все эти предки различны, кроме того, если <tex>k</tex> {{---}} такой предок <tex>j</tex>, тогда <tex>d'_{k} \leqslant d'_{j} - 1 < d'_{j} \leqslant d'_{i}</tex>, что противоречит выбору <tex>t</tex> <br />
}}<br />
==== Корректность алгоритма ====<br />
{{Теорема<br />
|statement=<br />
Данный алгоритм корректно решает задачу <tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex><br />
|proof=<br />
Пусть <tex>L'_{max}</tex> {{---}} оптимальное значение. В таком случае, существует расписание, удовлетворяющее <tex>\max\limits_i \{C_i - d_i\} \leqslant L'_{max}</tex>, что эквивалетно выражению <tex>C_{i} \leqslant d_{i} + L'_{max}</tex> для <tex>i = 1 \dots n </tex>. По первой лемме расписание <tex>S</tex>, построенное для сдвинутых дат <tex>d_{i} + L'_{max}</tex> удовлетворяет данным выражениям. Таким образом, оно оптимально. Нетрудно заметить, что <tex>S</tex> идентично расписанию, построенному алгоритмом, т.к. <tex>(d_{i}+L'_{max})' = d'_{i} + L'_{max} </tex> для <tex>i = 1 \dots n </tex><br />
}}<br />
<br />
==== Асимптотика ====<br />
# Посещаем каждую вершину ровно один раз (для изменения времени) за <tex>O(n)</tex> времени<br />
# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем для каждой вершины считаем время за линейное время.<br />
Итоговая сложность {{---}} <tex>O(n \log n)</tex><br />
<br />
==Источники информации==<br />
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 151-156 ISBN 978-3-540-69515-8<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Теория расписаний]]</div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=54169
Дискретная математика, алгоритмы и структуры данных
2016-05-22T13:25:57Z
<p>95.161.239.161: /* Задачи для произвольного числа станков */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
<br />
= Первый семестр =<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Отношение порядка]]<br />
*[[Отношение эквивалентности]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
*[[Транзитивный остов]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Побитовые операции]]<tex>^\star</tex><br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br />
*[[КНФ]]<br />
*[[2-SAT]]<br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
*[[Троичная логика]]<tex>^\star</tex><br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Простейшие методы синтеза схем из функциональных элементов]]<br />
*[[Метод Лупанова синтеза схем]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Троичный сумматор]]<tex>^\star</tex><br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
*[[Контактная схема]]<br />
*[[Триггеры]]<tex>^\star</tex><br />
*[[Квантовые гейты]]<tex>^\star</tex><br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex><br />
<br />
== Алгоритмы сжатия ==<br />
* [[Алгоритм Хаффмана]]<br />
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]<br />
* [[Алгоритм Хаффмана за O(n)]]<br />
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex><br />
* [[Неравенство Крафта]]<br />
* [[Неравенство Макмиллана]]<br />
* [[Код Шеннона]]<br />
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex><br />
* [[Алгоритмы LZ77 и LZ78]]<br />
* [[Алгоритм LZW]]<br />
* [[Алгоритм LZSS]]<tex>^\star</tex><br />
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br />
* [[Преобразование MTF]]<br />
* [[Расстояние Хэмминга]]<br />
* [[Избыточное кодирование, код Хэмминга]]<br />
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex><br />
<br />
== Комбинаторика ==<br />
=== Комбинаторные объекты ===<br />
* [[Комбинаторные объекты]]<br />
* [[Лексикографический порядок]]<br />
* [[Коды Грея]]<br />
* [[Коды Грея для перестановок]]<br />
* [[Коды антигрея]]<br />
* [[Цепные коды]]<br />
* [[Правильные скобочные последовательности]]<br />
<br />
=== Генерация комбинаторных объектов ===<br />
* [[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
* [[Получение номера по объекту]]<br />
* [[Получение объекта по номеру]]<br />
* [[Получение следующего объекта]]<br />
* [[Получение предыдущего объекта]]<tex>^\star</tex> <br />
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
* [[Методы генерации случайного сочетания]]<tex>^\star</tex><br />
<br />
=== Подсчёт числа объектов ===<br />
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]<br />
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
* [[Производящая функция]]<br />
* [[Лемма Бёрнсайда и Теорема Пойа]]<br />
* [[Задача об ожерельях]]<br />
* [[Числа Стирлинга первого рода]]<br />
* [[Числа Стирлинга второго рода]]<br />
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex><br />
* [[Числа Каталана]]<br />
<br />
=== Свойства комбинаторных объектов ===<br />
* [[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
* [[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
* [[Таблица инверсий]]<br />
* [[Теорема Кэли]]<br />
* [[Матричное представление перестановок]]<br />
* [[Задача о минимуме/максимуме скалярного произведения]]<br />
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
<br />
== [[Динамическое программирование]] ==<br />
=== Классические задачи динамического программирования ===<br />
*[[Кратчайший путь в ациклическом графе]]<br />
*[[Задача о числе путей в ациклическом графе]]<br />
*[[Задача о расстановке знаков в выражении]]<br />
*[[Задача о порядке перемножения матриц]]<br />
*[[Задача о наибольшей общей подпоследовательности]]<br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
*[[Задача о рюкзаке]]<br />
<br />
=== Способы оптимизации методов динамического программирования ===<br />
*[[Метод четырех русских для умножения матриц]]<br />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex><br />
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br />
*[[Meet-in-the-middle]]<tex>^\star</tex><br />
<br />
=== Другие задачи ===<br />
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex><br />
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br />
*[[Задача о наибольшей подпоследовательности-палиндроме]]<br />
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex><br />
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex><br />
*[[Динамическое программирование по профилю]]<tex>^\star</tex><br />
*[[Динамика по поддеревьям]]<br />
<br />
== Теория вероятностей ==<br />
*[[Вероятностное пространство, элементарный исход, событие]]<br />
*[[Независимые события]]<br />
*[[Условная вероятность]]<br />
*[[Формула полной вероятности]]<br />
*[[Формула Байеса]]<br />
*[[Дискретная случайная величина]]<br />
*[[Независимые случайные величины]]<br />
*[[Математическое ожидание случайной величины]]<br />
*[[Дисперсия случайной величины]]<br />
*[[Ковариация случайных величин]]<br />
*[[Корреляция случайных величин]]<br />
*[[Неравенство Маркова]]<br />
*[[Энтропия случайного источника]]<br />
*[[Симуляция одним распределением другого]]<br />
*[[Арифметическое кодирование]]<br />
*[[Парадоксы теории вероятностей]]<tex>^\star</tex><br />
*[[Схема Бернулли]]<tex>^\star</tex><br />
<br />
== Марковские цепи ==<br />
<br />
* [[Марковская цепь]]<br />
* [[Теорема о поглощении]]<br />
* [[Фундаментальная матрица]]<br />
* [[Математическое ожидание времени поглощения]]<br />
* [[Расчет вероятности поглощения в состоянии]]<br />
* [[Эргодическая марковская цепь]]<br />
* [[Регулярная марковская цепь]]<br />
* [[Примеры использования Марковских цепей]]<br />
* [[Скрытые Марковские модели]]<tex>^\star</tex><br />
* [[Алгоритм Витерби]]<tex>^\star</tex><br />
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex><br />
* [[Алгоритм Баума-Велша]]<tex>^\star</tex><br />
<br />
= Второй семестр =<br />
<br />
== Амортизационный анализ ==<br />
* [[Амортизационный анализ]]<br />
* [[Динамический массив]]<br />
* [[Hashed Array Tree]]<tex>^\star</tex><br />
* [[Список]]<br />
* [[Стек]]<br />
* [[Очередь]]<br />
* [[Дек]]<br />
* [[Мажорирующий элемент]]<br />
* [[Счетчик Кнута]]<br />
* [[Мастер-теорема]]<tex>^\star</tex><br />
* [[List order maintenance]]<tex>^\star</tex><br />
<br />
== Персистентные структуры данных ==<br />
* [[Персистентные структуры данных]]<br />
* [[Персистентный стек]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентный дек]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== [[Приоритетные очереди]] ==<br />
* [[Двоичная куча]]<br />
* [[Биномиальная куча]]<br />
* [[Фибоначчиева куча]]<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<tex>^\star</tex><br />
<br />
== Система непересекающихся множеств ==<br />
* [[СНМ (наивные реализации) | Наивные реализации]]<br />
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br />
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br />
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex><br />
<br />
== [[Поисковые структуры данных]] ==<br />
* [[Упорядоченное множество]]<br />
* [[Дерево поиска, наивная реализация]]<br />
* [[АВЛ-дерево]]<br />
* [[2-3 дерево]]<br />
* [[B-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[Декартово дерево]]<br />
* [[Декартово дерево по неявному ключу]]<br />
* [[Splay-дерево]]<br />
* [[Tango-дерево]]<tex>^\star</tex><br />
* [[Рандомизированное бинарное дерево поиска]]<br />
* [[Дерево ван Эмде Боаса]]<br />
* [[Список с пропусками]]<br />
* [[Fusion tree]]<tex>^\star</tex><br />
* [[Сверхбыстрый цифровой бор]]<br />
* [[Rope]]<tex>^\star</tex><br />
<br />
== Дерево отрезков ==<br />
<br />
* [[Статистики на отрезках. Корневая эвристика]]<br />
* [[Дерево отрезков. Построение]]<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
* [[Несогласованные поддеревья. Реализация массового обновления]]<br />
* [[Многомерное дерево отрезков]]<br />
* [[Сжатое многомерное дерево отрезков]]<br />
<br />
== Дерево Фенвика ==<br />
* [[Дерево Фенвика]]<br />
* [[Встречное дерево Фенвика]]<br />
* [[Дерево Фенвика для некоммутативных операций]]<br />
* [[Многомерное дерево Фенвика]]<br />
<br />
== Хеширование ==<br />
* [[Хеш-таблица]]<br />
* [[Разрешение коллизий]]<br />
* [[Хеширование кукушки]]<br />
* [[Идеальное хеширование]]<br />
* [[Перехеширование]]<br />
* [[Фильтр Блума]]<br />
* [[Quotient filter]]<tex>^\star</tex><br />
* [[Универсальное семейство хеш-функций]]<br />
* [[Расширяемое хеширование]]<tex>^\star</tex><br />
<br />
== [[Сортировки]] ==<br />
=== Квадратичные сортировки ===<br />
* [[Сортировка выбором]]<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка вставками]]<br />
=== Сортировки на сравнениях ===<br />
* [[Сортировка Шелла]]<tex>^\star</tex><br />
* [[Сортировка кучей]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка слиянием]]<br />
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br />
* [[Терпеливая сортировка]]<tex>^\star</tex><br />
* [[Timsort]]<tex>^\star</tex><br />
* [[Smoothsort]]<tex>^\star</tex><br />
* [[Теорема о нижней оценке для сортировки сравнениями]]<br />
<br />
=== Многопоточные сортировки ===<br />
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex><br />
* [[PSRS-сортировка]]<tex>^\star</tex><br />
=== Другие сортировки ===<br />
* [[Поиск k-ой порядковой статистики]]<br />
* [[Поиск k-ой порядковой статистики за линейное время]]<br />
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex><br />
* [[Сортировка подсчетом]]<br />
* [[Цифровая сортировка]]<br />
* [[Карманная сортировка]]<br />
* [[Сортировка Хана]]<tex>^\star</tex><br />
* [[Задача флага Нидерландов]]<tex>^\star</tex><br />
* [[Блинная сортировка]]<tex>^\star</tex><br />
<br />
== Сортирующие сети ==<br />
* [[Сортирующие сети]]<br />
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br />
* [[Сортирующие сети для квадратичных сортировок]]<br />
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex><br />
* [[Сеть Бетчера]]<br />
<br />
== Алгоритмы поиска ==<br />
* [[Целочисленный двоичный поиск]]<br />
* [[Поиск в матрице]]<tex>^\star</tex><br />
* [[Вещественный двоичный поиск]]<br />
* [[Троичный поиск]]<br />
* [[Поиск с помощью золотого сечения]]<br />
* [[Интерполяционный поиск]]<br />
* [[Метод Фибоначчи]]<tex>^\star</tex><br />
<br />
== Связь между структурами данных ==<br />
* [[Связь между структурами данных]]<br />
<br />
= Третий семестр =<br />
<br />
== Основные определения теории графов ==<br />
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]<br />
* [[Лемма о рукопожатиях]]<br />
* [[Теорема о существовании простого пути в случае существования пути]]<br />
* [[Теорема о существовании простого цикла в случае существования цикла]]<br />
* [[Матрица смежности графа]]<br />
* [[Матрица инцидентности графа]]<br />
* [[Циклическое пространство графа]]<tex>^\star</tex><br />
* [[Фундаментальные циклы графа]]<tex>^\star</tex><br />
* [[Дерево, эквивалентные определения]]<br />
* [[Алгоритмы на деревьях]]<tex>^\star</tex><br />
* [[Дополнительный, самодополнительный граф]]<br />
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex><br />
* [[Рёберное ядро]]<br />
* [[Факторизация графов]]<tex>^\star</tex><br />
<br />
== Связность в графах ==<br />
* [[Отношение связности, компоненты связности]]<br />
* [[Отношение реберной двусвязности]]<br />
* [[Отношение вершинной двусвязности]]<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Мост, эквивалентные определения]]<br />
* [[Граф компонент реберной двусвязности]]<br />
* [[Граф блоков-точек сочленения]]<br />
* [[k-связность]]<br />
* [[Теорема Менгера]]<br />
* [[Теорема Менгера, альтернативное доказательство]]<br />
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]<br />
<br />
== Остовные деревья ==<br />
=== Построение остовных деревьев ===<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
* [[Алгоритм Прима]]<br />
* [[Алгоритм Краскала]]<br />
* [[Алгоритм Борувки]]<br />
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<br />
* [[Алгоритм двух китайцев]]<br />
<br />
=== Свойства остовных деревьев ===<br />
* [[Матрица Кирхгофа]]<br />
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]<br />
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]<br />
* [[Количество помеченных деревьев]]<br />
* [[Коды Прюфера]]<br />
<br />
== Обходы графов ==<br />
=== Эйлеровы графы ===<br />
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Алгоритм построения Эйлерова цикла]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
=== Гамильтоновы графы ===<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Хватала]]<br />
* [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
* [[Теорема Поша]]<tex>^\star</tex><br />
* [[Теорема Гуйя-Ури]]<tex>^\star</tex><br />
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]<br />
* [[Теорема Гринберга]]<tex>^\star</tex><br />
* [[Турниры]]<br />
* [[Теорема Редеи-Камиона]]<br />
<br />
== Укладки графов ==<br />
* [[Укладка графа на плоскости]]<br />
* [[Формула Эйлера]]<br />
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]<br />
* [[Укладка дерева]]<br />
* [[Укладка графа с планарными компонентами реберной двусвязности]]<br />
* [[Укладка графа с планарными компонентами вершинной двусвязности]]<br />
* [[Теорема Понтрягина-Куратовского]]<br />
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex><br />
* [[Двойственный граф планарного графа]]<br />
* [[Теорема Фари]]<tex>^\star</tex><br />
* [[Гамма-алгоритм]]<br />
<br />
== Раскраски графов ==<br />
* [[Раскраска графа]]<br />
* [[Двудольные графы и раскраска в 2 цвета]]<br />
* [[Хроматический многочлен]]<br />
* [[Формула Зыкова]]<br />
* [[Формула Уитни]]<br />
* [[Теорема Брукса]]<br />
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex><br />
* [[Хроматическое число планарного графа]]<br />
* [[Многочлен Татта]]<tex>^\star</tex><br />
* [[Теория Рамсея]]<tex>^\star</tex><br />
<br />
== Обход в глубину ==<br />
* [[Обход в глубину, цвета вершин]]<br />
* [[Лемма о белых путях]]<br />
* [[Использование обхода в глубину для проверки связности]]<br />
* [[Использование обхода в глубину для поиска цикла]]<br />
* [[Использование обхода в глубину для топологической сортировки]]<br />
* [[Использование обхода в глубину для поиска компонент сильной связности]]<br />
* [[Использование обхода в глубину для поиска точек сочленения]]<br />
* [[Построение компонент вершинной двусвязности]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
* [[Построение компонент реберной двусвязности]]<br />
<br />
== Кратчайшие пути в графах ==<br />
* [[Обход в ширину]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Левита]]<tex>^\star</tex><br />
* [[Алгоритм A*]] <tex>^\star</tex><br />
* [[Алгоритм D*]] <tex>^\star</tex><br />
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex><br />
<br />
== Задача о паросочетании ==<br />
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]<br />
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]<br />
* [[Алгоритм Куна для поиска максимального паросочетания]]<br />
* [[Теорема Холла]]<br />
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]<br />
* [[Связь вершинного покрытия и независимого множества]]<br />
* [[Рёберное ядро]]<tex>^\star</tex><br />
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]<br />
* [[Теорема Татта о существовании полного паросочетания]]<br />
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]<br />
* [[Декомпозиция Эдмондса-Галлаи]]<br />
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex><br />
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex><br />
<br />
== Задача о максимальном потоке ==<br />
* [[Определение сети, потока]]<br />
* [[Разрез, лемма о потоке через разрез]]<br />
* [[Дополняющая сеть, дополняющий путь]]<br />
* [[Сложение и разность потоков]]<br />
* [[Теорема Форда-Фалкерсона]]<br />
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]<br />
* [[Алоритм Эдмондса-Карпа]]<br />
* [[Алгоритм масштабирования потока]]<br />
* [[Блокирующий поток]]<br />
* [[Схема алгоритма Диница]]<br />
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]<br />
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex><br />
* [[Алгоритм поиска блокирующего потока в ациклической сети]]<br />
* [[Метод проталкивания предпотока]]<br />
* [[Алгоритм "поднять-в-начало"]]<br />
* [[Теорема о декомпозиции]]<br />
* [[Теорема о декомпозиционном барьере]]<br />
* [[Циркуляция потока]]<br />
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex><br />
<br />
== Задача о потоке минимальной стоимости ==<br />
* [[Поток минимальной стоимости]]<br />
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]<br />
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]<br />
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]<br />
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]<br />
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]<br />
* [[Венгерский алгоритм решения задачи о назначениях]]<br />
<br />
= Четвертый семестр =<br />
<br />
== Основные определения. Простые комбинаторные свойства слов ==<br />
* [[Основные определения, связанные со строками]]<br />
* [[Период и бордер, их связь]]<br />
* [[Слово Фибоначчи]]<br />
* [[Слово Туэ-Морса]]<br />
* [[Декомпозиция Линдона]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex><br />
* [[Алгоритм Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex><br />
* [[Алгоритм Манакера]]<tex>^\star</tex><br />
<br />
== [[Поиск подстроки в строке]] ==<br />
=== Точный поиск ===<br />
* [[Наивный алгоритм поиска подстроки в строке]]<br />
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
* [[Префикс-функция]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
* [[Автомат Кнута-Морриса-Пратта]]<br />
* [[Z-функция]]<br />
* [[Бор]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
* [[Суффиксный автомат]]<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Колусси]]<tex>^\star</tex><br />
* [[Алгоритм Райта]]<tex>^\star</tex><br />
* [[Алгоритм Shift-And]]<tex>^\star</tex><br />
* [[Двусторонний алгоритм]]<tex>^\star</tex><br />
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex><br />
<br />
=== Нечёткий поиск ===<br />
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex><br />
<br />
== Суффиксное дерево ==<br />
* [[Суффиксный бор]]<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Алгоритм МакКрейта]]<tex>^\star</tex><br />
* [[Алгоритм Фарача]]<tex>^\star</tex><br />
<br />
== Суффиксный массив ==<br />
* [[Суффиксный массив]]<br />
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]<br />
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]<br />
* [[Алгоритм Касаи и др.]]<br />
* [[Алгоритм Карккайнена-Сандерса]]<br />
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]<br />
* [[Количество подпалиндромов в строке]]<tex>^\star</tex><br />
<br />
== Задача о наименьшем общем предке ==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
* [[Метод двоичного подъема]]<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)<br />
* [[Алгоритм Хьюи]]<br />
* [[Heavy-light декомпозиция]]<br />
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex><br />
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex><br />
* [[Link-Cut Tree]]<tex>^\star</tex><br />
* [[Rake-Compress деревья]]<tex>^\star</tex><br />
<br />
== Матроиды ==<br />
=== Основные факты теории матроидов ===<br />
* [[Определение матроида]]<br />
* [[Примеры матроидов]]<br />
* [[Прямая сумма матроидов]]<br />
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]<br />
* [[Теорема о базах]]<br />
* [[Аксиоматизация матроида базами]]<br />
* [[Теорема о циклах]]<br />
* [[Аксиоматизация матроида циклами]]<br />
* [[Ранговая функция, полумодулярность]]<br />
* [[Аксиоматизация матроида рангами]]<br />
* [[Двойственный матроид]]<br />
* [[Оператор замыкания для матроидов]]<br />
* [[Покрытия, закрытые множества]]<br />
* [[Матроид Вамоса]]<tex>^\star</tex><br />
<br />
=== Пересечение матроидов ===<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Граф замен]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
=== Объединение матроидов ===<br />
* [[Объединение матроидов, проверка множества на независимость]]<br />
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]<br />
* [[Алгоритм построения базы в объединении матроидов]]<br />
<br />
== Теория расписаний ==<br />
=== Общая теория ===<br />
* [[Классификация задач]]<br />
* [[Методы решения задач теории расписаний]]<br />
* [[Правило Лаулера]]<br />
<br />
=== Задачи с одним станком ===<br />
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]<br />
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]<br />
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]<br />
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]<br />
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]<br />
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]<br />
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]]<br />
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]<br />
<br />
=== Специальные случаи задач для двух станков ===<br />
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]<br />
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]<br />
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]<br />
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]<br />
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]<br />
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]<br />
<br />
=== Задачи для произвольного числа станков ===<br />
* [[Flow shop]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]<br />
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]<br />
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]<br />
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]<br />
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]<br />
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]<br />
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]<br />
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]<br />
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]<br />
* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]]</div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=54167
Дискретная математика, алгоритмы и структуры данных
2016-05-22T13:25:13Z
<p>95.161.239.161: /* Задачи для произвольного числа станков */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
<br />
= Первый семестр =<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Отношение порядка]]<br />
*[[Отношение эквивалентности]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
*[[Транзитивный остов]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Побитовые операции]]<tex>^\star</tex><br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br />
*[[КНФ]]<br />
*[[2-SAT]]<br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
*[[Троичная логика]]<tex>^\star</tex><br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Простейшие методы синтеза схем из функциональных элементов]]<br />
*[[Метод Лупанова синтеза схем]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Троичный сумматор]]<tex>^\star</tex><br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
*[[Контактная схема]]<br />
*[[Триггеры]]<tex>^\star</tex><br />
*[[Квантовые гейты]]<tex>^\star</tex><br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex><br />
<br />
== Алгоритмы сжатия ==<br />
* [[Алгоритм Хаффмана]]<br />
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]<br />
* [[Алгоритм Хаффмана за O(n)]]<br />
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex><br />
* [[Неравенство Крафта]]<br />
* [[Неравенство Макмиллана]]<br />
* [[Код Шеннона]]<br />
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex><br />
* [[Алгоритмы LZ77 и LZ78]]<br />
* [[Алгоритм LZW]]<br />
* [[Алгоритм LZSS]]<tex>^\star</tex><br />
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br />
* [[Преобразование MTF]]<br />
* [[Расстояние Хэмминга]]<br />
* [[Избыточное кодирование, код Хэмминга]]<br />
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex><br />
<br />
== Комбинаторика ==<br />
=== Комбинаторные объекты ===<br />
* [[Комбинаторные объекты]]<br />
* [[Лексикографический порядок]]<br />
* [[Коды Грея]]<br />
* [[Коды Грея для перестановок]]<br />
* [[Коды антигрея]]<br />
* [[Цепные коды]]<br />
* [[Правильные скобочные последовательности]]<br />
<br />
=== Генерация комбинаторных объектов ===<br />
* [[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
* [[Получение номера по объекту]]<br />
* [[Получение объекта по номеру]]<br />
* [[Получение следующего объекта]]<br />
* [[Получение предыдущего объекта]]<tex>^\star</tex> <br />
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
* [[Методы генерации случайного сочетания]]<tex>^\star</tex><br />
<br />
=== Подсчёт числа объектов ===<br />
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]<br />
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
* [[Производящая функция]]<br />
* [[Лемма Бёрнсайда и Теорема Пойа]]<br />
* [[Задача об ожерельях]]<br />
* [[Числа Стирлинга первого рода]]<br />
* [[Числа Стирлинга второго рода]]<br />
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex><br />
* [[Числа Каталана]]<br />
<br />
=== Свойства комбинаторных объектов ===<br />
* [[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
* [[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
* [[Таблица инверсий]]<br />
* [[Теорема Кэли]]<br />
* [[Матричное представление перестановок]]<br />
* [[Задача о минимуме/максимуме скалярного произведения]]<br />
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
<br />
== [[Динамическое программирование]] ==<br />
=== Классические задачи динамического программирования ===<br />
*[[Кратчайший путь в ациклическом графе]]<br />
*[[Задача о числе путей в ациклическом графе]]<br />
*[[Задача о расстановке знаков в выражении]]<br />
*[[Задача о порядке перемножения матриц]]<br />
*[[Задача о наибольшей общей подпоследовательности]]<br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
*[[Задача о рюкзаке]]<br />
<br />
=== Способы оптимизации методов динамического программирования ===<br />
*[[Метод четырех русских для умножения матриц]]<br />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex><br />
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br />
*[[Meet-in-the-middle]]<tex>^\star</tex><br />
<br />
=== Другие задачи ===<br />
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex><br />
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br />
*[[Задача о наибольшей подпоследовательности-палиндроме]]<br />
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex><br />
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex><br />
*[[Динамическое программирование по профилю]]<tex>^\star</tex><br />
*[[Динамика по поддеревьям]]<br />
<br />
== Теория вероятностей ==<br />
*[[Вероятностное пространство, элементарный исход, событие]]<br />
*[[Независимые события]]<br />
*[[Условная вероятность]]<br />
*[[Формула полной вероятности]]<br />
*[[Формула Байеса]]<br />
*[[Дискретная случайная величина]]<br />
*[[Независимые случайные величины]]<br />
*[[Математическое ожидание случайной величины]]<br />
*[[Дисперсия случайной величины]]<br />
*[[Ковариация случайных величин]]<br />
*[[Корреляция случайных величин]]<br />
*[[Неравенство Маркова]]<br />
*[[Энтропия случайного источника]]<br />
*[[Симуляция одним распределением другого]]<br />
*[[Арифметическое кодирование]]<br />
*[[Парадоксы теории вероятностей]]<tex>^\star</tex><br />
*[[Схема Бернулли]]<tex>^\star</tex><br />
<br />
== Марковские цепи ==<br />
<br />
* [[Марковская цепь]]<br />
* [[Теорема о поглощении]]<br />
* [[Фундаментальная матрица]]<br />
* [[Математическое ожидание времени поглощения]]<br />
* [[Расчет вероятности поглощения в состоянии]]<br />
* [[Эргодическая марковская цепь]]<br />
* [[Регулярная марковская цепь]]<br />
* [[Примеры использования Марковских цепей]]<br />
* [[Скрытые Марковские модели]]<tex>^\star</tex><br />
* [[Алгоритм Витерби]]<tex>^\star</tex><br />
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex><br />
* [[Алгоритм Баума-Велша]]<tex>^\star</tex><br />
<br />
= Второй семестр =<br />
<br />
== Амортизационный анализ ==<br />
* [[Амортизационный анализ]]<br />
* [[Динамический массив]]<br />
* [[Hashed Array Tree]]<tex>^\star</tex><br />
* [[Список]]<br />
* [[Стек]]<br />
* [[Очередь]]<br />
* [[Дек]]<br />
* [[Мажорирующий элемент]]<br />
* [[Счетчик Кнута]]<br />
* [[Мастер-теорема]]<tex>^\star</tex><br />
* [[List order maintenance]]<tex>^\star</tex><br />
<br />
== Персистентные структуры данных ==<br />
* [[Персистентные структуры данных]]<br />
* [[Персистентный стек]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентный дек]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== [[Приоритетные очереди]] ==<br />
* [[Двоичная куча]]<br />
* [[Биномиальная куча]]<br />
* [[Фибоначчиева куча]]<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<tex>^\star</tex><br />
<br />
== Система непересекающихся множеств ==<br />
* [[СНМ (наивные реализации) | Наивные реализации]]<br />
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br />
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br />
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex><br />
<br />
== [[Поисковые структуры данных]] ==<br />
* [[Упорядоченное множество]]<br />
* [[Дерево поиска, наивная реализация]]<br />
* [[АВЛ-дерево]]<br />
* [[2-3 дерево]]<br />
* [[B-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[Декартово дерево]]<br />
* [[Декартово дерево по неявному ключу]]<br />
* [[Splay-дерево]]<br />
* [[Tango-дерево]]<tex>^\star</tex><br />
* [[Рандомизированное бинарное дерево поиска]]<br />
* [[Дерево ван Эмде Боаса]]<br />
* [[Список с пропусками]]<br />
* [[Fusion tree]]<tex>^\star</tex><br />
* [[Сверхбыстрый цифровой бор]]<br />
* [[Rope]]<tex>^\star</tex><br />
<br />
== Дерево отрезков ==<br />
<br />
* [[Статистики на отрезках. Корневая эвристика]]<br />
* [[Дерево отрезков. Построение]]<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
* [[Несогласованные поддеревья. Реализация массового обновления]]<br />
* [[Многомерное дерево отрезков]]<br />
* [[Сжатое многомерное дерево отрезков]]<br />
<br />
== Дерево Фенвика ==<br />
* [[Дерево Фенвика]]<br />
* [[Встречное дерево Фенвика]]<br />
* [[Дерево Фенвика для некоммутативных операций]]<br />
* [[Многомерное дерево Фенвика]]<br />
<br />
== Хеширование ==<br />
* [[Хеш-таблица]]<br />
* [[Разрешение коллизий]]<br />
* [[Хеширование кукушки]]<br />
* [[Идеальное хеширование]]<br />
* [[Перехеширование]]<br />
* [[Фильтр Блума]]<br />
* [[Quotient filter]]<tex>^\star</tex><br />
* [[Универсальное семейство хеш-функций]]<br />
* [[Расширяемое хеширование]]<tex>^\star</tex><br />
<br />
== [[Сортировки]] ==<br />
=== Квадратичные сортировки ===<br />
* [[Сортировка выбором]]<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка вставками]]<br />
=== Сортировки на сравнениях ===<br />
* [[Сортировка Шелла]]<tex>^\star</tex><br />
* [[Сортировка кучей]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка слиянием]]<br />
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br />
* [[Терпеливая сортировка]]<tex>^\star</tex><br />
* [[Timsort]]<tex>^\star</tex><br />
* [[Smoothsort]]<tex>^\star</tex><br />
* [[Теорема о нижней оценке для сортировки сравнениями]]<br />
<br />
=== Многопоточные сортировки ===<br />
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex><br />
* [[PSRS-сортировка]]<tex>^\star</tex><br />
=== Другие сортировки ===<br />
* [[Поиск k-ой порядковой статистики]]<br />
* [[Поиск k-ой порядковой статистики за линейное время]]<br />
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex><br />
* [[Сортировка подсчетом]]<br />
* [[Цифровая сортировка]]<br />
* [[Карманная сортировка]]<br />
* [[Сортировка Хана]]<tex>^\star</tex><br />
* [[Задача флага Нидерландов]]<tex>^\star</tex><br />
* [[Блинная сортировка]]<tex>^\star</tex><br />
<br />
== Сортирующие сети ==<br />
* [[Сортирующие сети]]<br />
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br />
* [[Сортирующие сети для квадратичных сортировок]]<br />
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex><br />
* [[Сеть Бетчера]]<br />
<br />
== Алгоритмы поиска ==<br />
* [[Целочисленный двоичный поиск]]<br />
* [[Поиск в матрице]]<tex>^\star</tex><br />
* [[Вещественный двоичный поиск]]<br />
* [[Троичный поиск]]<br />
* [[Поиск с помощью золотого сечения]]<br />
* [[Интерполяционный поиск]]<br />
* [[Метод Фибоначчи]]<tex>^\star</tex><br />
<br />
== Связь между структурами данных ==<br />
* [[Связь между структурами данных]]<br />
<br />
= Третий семестр =<br />
<br />
== Основные определения теории графов ==<br />
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]<br />
* [[Лемма о рукопожатиях]]<br />
* [[Теорема о существовании простого пути в случае существования пути]]<br />
* [[Теорема о существовании простого цикла в случае существования цикла]]<br />
* [[Матрица смежности графа]]<br />
* [[Матрица инцидентности графа]]<br />
* [[Циклическое пространство графа]]<tex>^\star</tex><br />
* [[Фундаментальные циклы графа]]<tex>^\star</tex><br />
* [[Дерево, эквивалентные определения]]<br />
* [[Алгоритмы на деревьях]]<tex>^\star</tex><br />
* [[Дополнительный, самодополнительный граф]]<br />
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex><br />
* [[Рёберное ядро]]<br />
* [[Факторизация графов]]<tex>^\star</tex><br />
<br />
== Связность в графах ==<br />
* [[Отношение связности, компоненты связности]]<br />
* [[Отношение реберной двусвязности]]<br />
* [[Отношение вершинной двусвязности]]<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Мост, эквивалентные определения]]<br />
* [[Граф компонент реберной двусвязности]]<br />
* [[Граф блоков-точек сочленения]]<br />
* [[k-связность]]<br />
* [[Теорема Менгера]]<br />
* [[Теорема Менгера, альтернативное доказательство]]<br />
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]<br />
<br />
== Остовные деревья ==<br />
=== Построение остовных деревьев ===<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
* [[Алгоритм Прима]]<br />
* [[Алгоритм Краскала]]<br />
* [[Алгоритм Борувки]]<br />
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<br />
* [[Алгоритм двух китайцев]]<br />
<br />
=== Свойства остовных деревьев ===<br />
* [[Матрица Кирхгофа]]<br />
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]<br />
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]<br />
* [[Количество помеченных деревьев]]<br />
* [[Коды Прюфера]]<br />
<br />
== Обходы графов ==<br />
=== Эйлеровы графы ===<br />
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Алгоритм построения Эйлерова цикла]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
=== Гамильтоновы графы ===<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Хватала]]<br />
* [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
* [[Теорема Поша]]<tex>^\star</tex><br />
* [[Теорема Гуйя-Ури]]<tex>^\star</tex><br />
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]<br />
* [[Теорема Гринберга]]<tex>^\star</tex><br />
* [[Турниры]]<br />
* [[Теорема Редеи-Камиона]]<br />
<br />
== Укладки графов ==<br />
* [[Укладка графа на плоскости]]<br />
* [[Формула Эйлера]]<br />
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]<br />
* [[Укладка дерева]]<br />
* [[Укладка графа с планарными компонентами реберной двусвязности]]<br />
* [[Укладка графа с планарными компонентами вершинной двусвязности]]<br />
* [[Теорема Понтрягина-Куратовского]]<br />
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex><br />
* [[Двойственный граф планарного графа]]<br />
* [[Теорема Фари]]<tex>^\star</tex><br />
* [[Гамма-алгоритм]]<br />
<br />
== Раскраски графов ==<br />
* [[Раскраска графа]]<br />
* [[Двудольные графы и раскраска в 2 цвета]]<br />
* [[Хроматический многочлен]]<br />
* [[Формула Зыкова]]<br />
* [[Формула Уитни]]<br />
* [[Теорема Брукса]]<br />
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex><br />
* [[Хроматическое число планарного графа]]<br />
* [[Многочлен Татта]]<tex>^\star</tex><br />
* [[Теория Рамсея]]<tex>^\star</tex><br />
<br />
== Обход в глубину ==<br />
* [[Обход в глубину, цвета вершин]]<br />
* [[Лемма о белых путях]]<br />
* [[Использование обхода в глубину для проверки связности]]<br />
* [[Использование обхода в глубину для поиска цикла]]<br />
* [[Использование обхода в глубину для топологической сортировки]]<br />
* [[Использование обхода в глубину для поиска компонент сильной связности]]<br />
* [[Использование обхода в глубину для поиска точек сочленения]]<br />
* [[Построение компонент вершинной двусвязности]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
* [[Построение компонент реберной двусвязности]]<br />
<br />
== Кратчайшие пути в графах ==<br />
* [[Обход в ширину]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Левита]]<tex>^\star</tex><br />
* [[Алгоритм A*]] <tex>^\star</tex><br />
* [[Алгоритм D*]] <tex>^\star</tex><br />
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex><br />
<br />
== Задача о паросочетании ==<br />
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]<br />
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]<br />
* [[Алгоритм Куна для поиска максимального паросочетания]]<br />
* [[Теорема Холла]]<br />
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]<br />
* [[Связь вершинного покрытия и независимого множества]]<br />
* [[Рёберное ядро]]<tex>^\star</tex><br />
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]<br />
* [[Теорема Татта о существовании полного паросочетания]]<br />
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]<br />
* [[Декомпозиция Эдмондса-Галлаи]]<br />
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex><br />
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex><br />
<br />
== Задача о максимальном потоке ==<br />
* [[Определение сети, потока]]<br />
* [[Разрез, лемма о потоке через разрез]]<br />
* [[Дополняющая сеть, дополняющий путь]]<br />
* [[Сложение и разность потоков]]<br />
* [[Теорема Форда-Фалкерсона]]<br />
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]<br />
* [[Алоритм Эдмондса-Карпа]]<br />
* [[Алгоритм масштабирования потока]]<br />
* [[Блокирующий поток]]<br />
* [[Схема алгоритма Диница]]<br />
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]<br />
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex><br />
* [[Алгоритм поиска блокирующего потока в ациклической сети]]<br />
* [[Метод проталкивания предпотока]]<br />
* [[Алгоритм "поднять-в-начало"]]<br />
* [[Теорема о декомпозиции]]<br />
* [[Теорема о декомпозиционном барьере]]<br />
* [[Циркуляция потока]]<br />
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex><br />
<br />
== Задача о потоке минимальной стоимости ==<br />
* [[Поток минимальной стоимости]]<br />
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]<br />
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]<br />
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]<br />
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]<br />
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]<br />
* [[Венгерский алгоритм решения задачи о назначениях]]<br />
<br />
= Четвертый семестр =<br />
<br />
== Основные определения. Простые комбинаторные свойства слов ==<br />
* [[Основные определения, связанные со строками]]<br />
* [[Период и бордер, их связь]]<br />
* [[Слово Фибоначчи]]<br />
* [[Слово Туэ-Морса]]<br />
* [[Декомпозиция Линдона]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex><br />
* [[Алгоритм Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex><br />
* [[Алгоритм Манакера]]<tex>^\star</tex><br />
<br />
== [[Поиск подстроки в строке]] ==<br />
=== Точный поиск ===<br />
* [[Наивный алгоритм поиска подстроки в строке]]<br />
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
* [[Префикс-функция]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
* [[Автомат Кнута-Морриса-Пратта]]<br />
* [[Z-функция]]<br />
* [[Бор]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
* [[Суффиксный автомат]]<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Колусси]]<tex>^\star</tex><br />
* [[Алгоритм Райта]]<tex>^\star</tex><br />
* [[Алгоритм Shift-And]]<tex>^\star</tex><br />
* [[Двусторонний алгоритм]]<tex>^\star</tex><br />
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex><br />
<br />
=== Нечёткий поиск ===<br />
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex><br />
<br />
== Суффиксное дерево ==<br />
* [[Суффиксный бор]]<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Алгоритм МакКрейта]]<tex>^\star</tex><br />
* [[Алгоритм Фарача]]<tex>^\star</tex><br />
<br />
== Суффиксный массив ==<br />
* [[Суффиксный массив]]<br />
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]<br />
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]<br />
* [[Алгоритм Касаи и др.]]<br />
* [[Алгоритм Карккайнена-Сандерса]]<br />
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]<br />
* [[Количество подпалиндромов в строке]]<tex>^\star</tex><br />
<br />
== Задача о наименьшем общем предке ==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
* [[Метод двоичного подъема]]<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)<br />
* [[Алгоритм Хьюи]]<br />
* [[Heavy-light декомпозиция]]<br />
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex><br />
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex><br />
* [[Link-Cut Tree]]<tex>^\star</tex><br />
* [[Rake-Compress деревья]]<tex>^\star</tex><br />
<br />
== Матроиды ==<br />
=== Основные факты теории матроидов ===<br />
* [[Определение матроида]]<br />
* [[Примеры матроидов]]<br />
* [[Прямая сумма матроидов]]<br />
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]<br />
* [[Теорема о базах]]<br />
* [[Аксиоматизация матроида базами]]<br />
* [[Теорема о циклах]]<br />
* [[Аксиоматизация матроида циклами]]<br />
* [[Ранговая функция, полумодулярность]]<br />
* [[Аксиоматизация матроида рангами]]<br />
* [[Двойственный матроид]]<br />
* [[Оператор замыкания для матроидов]]<br />
* [[Покрытия, закрытые множества]]<br />
* [[Матроид Вамоса]]<tex>^\star</tex><br />
<br />
=== Пересечение матроидов ===<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Граф замен]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
=== Объединение матроидов ===<br />
* [[Объединение матроидов, проверка множества на независимость]]<br />
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]<br />
* [[Алгоритм построения базы в объединении матроидов]]<br />
<br />
== Теория расписаний ==<br />
=== Общая теория ===<br />
* [[Классификация задач]]<br />
* [[Методы решения задач теории расписаний]]<br />
* [[Правило Лаулера]]<br />
<br />
=== Задачи с одним станком ===<br />
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]<br />
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]<br />
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]<br />
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]<br />
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]<br />
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]<br />
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]]<br />
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]<br />
<br />
=== Специальные случаи задач для двух станков ===<br />
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]<br />
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]<br />
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]<br />
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]<br />
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]<br />
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]<br />
<br />
=== Задачи для произвольного числа станков ===<br />
* [[Flow shop]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]<br />
* [[PIntreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]<br />
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]<br />
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]<br />
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]<br />
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]<br />
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]<br />
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]<br />
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]<br />
* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]]</div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=Pintreepi1Lmax&diff=53915
Pintreepi1Lmax
2016-05-14T14:35:04Z
<p>95.161.239.161: Новая страница: «<tex dpi = "200">P \mid Intree, p_{i} = 1 \mid L_{max}</tex> {{Задача |definition=Рассмотрим задачу на нахождение распис...»</p>
<hr />
<div><tex dpi = "200">P \mid Intree, p_{i} = 1 \mid L_{max}</tex><br />
<br />
{{Задача<br />
|definition=Рассмотрим задачу на нахождение расписания:<br />
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.<br />
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист intree-дереве<br />
# Любая работа на любом станке выполняется единицу времени.<br />
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex> <br />
}}<br />
<br />
== Описание алгоритма ==<br />
[[Файл:Intree_example.jpg|thumb|Right|Пример Intree-дерева]]<br />
=== Идея ===<br />
<br />
Все вершины хранятся в дереве (англ. Intree), которое имеет несколько корней и один лист.<br />
<br />
Работы хранятся в дереве, состоящем из <tex>n</tex> вершин с фиктивной нулевой работой, которая является родителем тех вершин, у которых изначально его не было. В intree-дереве у одной вершины может быть два и более родителей.<br />
Решение задачи состоит из двух шагов: на первом шаге мы меняем сроки выполнения работ в соответствии с их очередностью.<br />
<br />
На первом шаге изменения сроков состоит в следующем: для всех <tex>i, j</tex> таких, что существует ребро из <tex>i</tex> в <tex>j</tex> будем менять <tex>{d_i}</tex> на <tex>\min ({d_i}, {d_j} - 1) </tex>. На втором шаге работы расставляются в неубывающем порядке сроков.<br />
<br />
=== Первый шаг ===<br />
Алгоритм изменения сроков:<br />
deque = {i <tex>\mid</tex> i является листом}<br />
while (deque not empty)<br />
i = stack.remove_first()<br />
for (j <tex>\mid</tex> j является предком i):<br />
<tex>d_{j} := min(d_{j}, d_{i} - 1)</tex><br />
stack.add_last(j)<br />
<br />
{{Лемма<br />
|statement=<br />
Работа с новым сроком <tex>{d'_i}</tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}</tex>.<br />
|proof=<br />
В одну сторону утверждение очевидно: т.к. <tex>{d'_i} \leq {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.<br />
Докажем лемму в другую сторону: пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом. Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leq {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем <tex>{C_n} \leq {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leq n</tex> мы имеем <tex>{C_n} \leq {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leq \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex><br />
}}<br />
<br />
=== Второй шаг ===<br />
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. <tex>d_{i} \leq d_{j}</tex>, если <tex>i \leq j</tex>.<br />
<br />
В переменной <tex>F</tex> хранится время, когда станок освободится.<br />
<br />
В массиве <tex>r</tex> хранится информация о максимальном времени завершении обработки родителя.<br />
<br />
Массив <tex>c</tex> хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени <tex>t</tex>.<br />
<br />
Массив <tex>x</tex> хранит информацию о начале выполнения работы <tex>i</tex>.<br />
<br />
F = 0<br />
for (i = 1..n)<br />
r[i] = 0<br />
for (t = 0..n)<br />
c[t] = 0<br />
for (i = 1..n)<br />
t = max(r[i], F)<br />
x[i] = t<br />
c[t] = c[t] + 1<br />
if (n[t] == m)<br />
F = t + 1<br />
j = s[i]<br />
r[j] = max (r[j], t + 1)<br />
<br />
Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени <tex>t</tex> меньше, чем в момент <tex>t + 1</tex>. Действительно, пусть во время <tex>t</tex> мы выполняем <tex>k</tex> работ, и хотя бы <tex>k + 1 \leq m</tex> работ готовы к выполению в момент времени <tex>t + 1</tex>. Но т.к. <tex>k + 1 \leq m</tex>, значит каждой из работ предшествовала как минимум одна, поскольку у всех вершин, кроме корней, есть как минимум один предок. Значит, в момент времени <tex>t</tex> исполнялось не менее <tex>k + 1</tex> работ, противоречие.<br />
<br />
{{Лемма<br />
|statement=<br />
Если существует такое расписание, в котором ни одна из работ не будет выполнена с опозданием, то тогда это свойство сохранится в построенном данным алгоритмом расписании<br />
|proof=<br />
Предположим, что существует работа из <tex>x_{1} \dots x_{n}</tex> расписания, построенного алгоритмом. В таком случае существует работа, которая опоздала по отношению к измененным срокам. Возьмем наименьшее <tex>i</tex> такое, что <tex>x(i) + 1 > d'_{i}</tex>. Пусть <tex>t < d'_{i}</tex> {{---}} наибольшее из удовлетворяющих условию <tex>j < m \mid x(j) = t, d'_{j} \leq d'_{i}</tex><br />
Такое <tex>t</tex> существует, потому что иначе <tex>m \cdot d'_{i}</tex> работ <tex>j</tex> с <tex>d'_{j} \leq d'_{i}</tex> находятся в очереди до <tex>d'_{i}</tex>. Работа <tex>i</tex> к ним не принадлежит, поскольку <tex>x(i) + 1 > d'_{i}</tex>, а значит, что <tex>m \cdot d'_{i} + 1</tex> должны быть в очереди в момент времени <tex>0 \dots d'_{i}</tex> и ни одна работа не должна опаздывать. Противоречие.<br />
Любая работа <tex>j</tex> с <tex>d'_{j} \leq d'_{i} </tex> и <tex> x(j) > t </tex> должна иметь предка, начавшего работать в момент времени <tex>t</tex>. Теперь рассмотрим два случая:<br />
<br />
'''Первый случай.''' <tex>t = d'_{i} - 1</tex>.<br />
<br />
Мы имеем <tex>x(i)>d'_{i}-1 = t</tex>. Таким образом, предок <tex>k</tex> работы <tex>i</tex> должен начать работать во время <tex>t</tex> и закончить в <tex>d'_{i}</tex>. Но т.к. <tex>d'_{k} \leq d'_{i} - 1 < d'_{i} = x(k) + 1</tex>, работа <tex>k</tex> так же опоздает, однако <tex>i</tex> было выбрано минимальным. Противоречие.<br />
<br />
'''Второй случай.''' <tex>t < d'_{i} - 1</tex>.<br />
<br />
В этом случае <tex>m</tex> работ <tex>j</tex> таких, что <tex>d'_{j} \leq d'_{i}</tex> начнут работать в момент времени <tex>t + 1</tex>, каждая из которых имеет как минимум работающего в <tex>t</tex> предка. По структуре дерева все эти предки различны, кроме того, если <tex>k</tex> {{---}} такой предок <tex>j</tex>, тогда <tex>d'_{k} \leq d'_{j} - 1 < d'_{j} \leq d'_{i}</tex>, что противоречит выбору <tex>t</tex> <br />
}}<br />
<br />
{{Теорема<br />
|statement=<br />
Данный алгоритм корректно решает задачу <tex>P \mid Tree, p_{i} = 1 \mid L_{max}</tex><br />
|proof=<br />
Пусть <tex>L'_{max}</tex> {{---}} оптимальное значение. В таком случае, существует расписание, удовлетворяющее <tex>\max\limits_i \{C_i - d_i\} \leq L'_{max}</tex>, что эквивалетно выражению <tex>C_{i} \leq d_{i} + L'_{max}</tex> для <tex>i = 1 \dots n </tex>. По первой лемме расписание <tex>S</tex>, построенное для сдвинутых дат <tex>d_{i} + L'_{max}</tex> удовлетворяет данным выражениям. Таким образом, оно оптимально. Нетрудно заметить, что <tex>S</tex> идентично расписанию, построенному алгоритмом, т.к. <tex>(d_{i}+L'_{max})' = d'_{i} + L'_{max} </tex> для <tex>i = 1 \dots n </tex><br />
}}<br />
<br />
<br />
==Источники информации==<br />
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 151-156 ISBN 978-3-540-69515-8<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Теория расписаний]]</div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=53914
Дискретная математика, алгоритмы и структуры данных
2016-05-14T14:34:34Z
<p>95.161.239.161: /* Задачи для произвольного числа станков */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
<br />
= Первый семестр =<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Отношение порядка]]<br />
*[[Отношение эквивалентности]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
*[[Транзитивный остов]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Побитовые операции]]<tex>^\star</tex><br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br />
*[[КНФ]]<br />
*[[2-SAT]]<br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
*[[Троичная логика]]<tex>^\star</tex><br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Простейшие методы синтеза схем из функциональных элементов]]<br />
*[[Метод Лупанова синтеза схем]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Троичный сумматор]]<tex>^\star</tex><br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
*[[Контактная схема]]<br />
*[[Триггеры]]<tex>^\star</tex><br />
*[[Квантовые гейты]]<tex>^\star</tex><br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex><br />
<br />
== Алгоритмы сжатия ==<br />
* [[Алгоритм Хаффмана]]<br />
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]<br />
* [[Алгоритм Хаффмана за O(n)]]<br />
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex><br />
* [[Неравенство Крафта]]<br />
* [[Неравенство Макмиллана]]<br />
* [[Код Шеннона]]<br />
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex><br />
* [[Алгоритмы LZ77 и LZ78]]<br />
* [[Алгоритм LZW]]<br />
* [[Алгоритм LZSS]]<tex>^\star</tex><br />
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br />
* [[Преобразование MTF]]<br />
* [[Расстояние Хэмминга]]<br />
* [[Избыточное кодирование, код Хэмминга]]<br />
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex><br />
<br />
== Комбинаторика ==<br />
=== Комбинаторные объекты ===<br />
* [[Комбинаторные объекты]]<br />
* [[Лексикографический порядок]]<br />
* [[Коды Грея]]<br />
* [[Коды Грея для перестановок]]<br />
* [[Коды антигрея]]<br />
* [[Цепные коды]]<br />
* [[Правильные скобочные последовательности]]<br />
<br />
=== Генерация комбинаторных объектов ===<br />
* [[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
* [[Получение номера по объекту]]<br />
* [[Получение объекта по номеру]]<br />
* [[Получение следующего объекта]]<br />
* [[Получение предыдущего объекта]]<tex>^\star</tex> <br />
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
* [[Методы генерации случайного сочетания]]<tex>^\star</tex><br />
<br />
=== Подсчёт числа объектов ===<br />
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]<br />
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
* [[Производящая функция]]<br />
* [[Лемма Бёрнсайда и Теорема Пойа]]<br />
* [[Задача об ожерельях]]<br />
* [[Числа Стирлинга первого рода]]<br />
* [[Числа Стирлинга второго рода]]<br />
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex><br />
* [[Числа Каталана]]<br />
<br />
=== Свойства комбинаторных объектов ===<br />
* [[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
* [[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
* [[Таблица инверсий]]<br />
* [[Теорема Кэли]]<br />
* [[Матричное представление перестановок]]<br />
* [[Задача о минимуме/максимуме скалярного произведения]]<br />
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
<br />
== [[Динамическое программирование]] ==<br />
=== Классические задачи динамического программирования ===<br />
*[[Кратчайший путь в ациклическом графе]]<br />
*[[Задача о числе путей в ациклическом графе]]<br />
*[[Задача о расстановке знаков в выражении]]<br />
*[[Задача о порядке перемножения матриц]]<br />
*[[Задача о наибольшей общей подпоследовательности]]<br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
*[[Задача о рюкзаке]]<br />
<br />
=== Способы оптимизации методов динамического программирования ===<br />
*[[Метод четырех русских для умножения матриц]]<br />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex><br />
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br />
*[[Meet-in-the-middle]]<tex>^\star</tex><br />
<br />
=== Другие задачи ===<br />
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex><br />
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br />
*[[Задача о наибольшей подпоследовательности-палиндроме]]<br />
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex><br />
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex><br />
*[[Динамическое программирование по профилю]]<tex>^\star</tex><br />
*[[Динамика по поддеревьям]]<br />
<br />
== Теория вероятностей ==<br />
*[[Вероятностное пространство, элементарный исход, событие]]<br />
*[[Независимые события]]<br />
*[[Условная вероятность]]<br />
*[[Формула полной вероятности]]<br />
*[[Формула Байеса]]<br />
*[[Дискретная случайная величина]]<br />
*[[Независимые случайные величины]]<br />
*[[Математическое ожидание случайной величины]]<br />
*[[Дисперсия случайной величины]]<br />
*[[Ковариация случайных величин]]<br />
*[[Корреляция случайных величин]]<br />
*[[Неравенство Маркова]]<br />
*[[Энтропия случайного источника]]<br />
*[[Симуляция одним распределением другого]]<br />
*[[Арифметическое кодирование]]<br />
*[[Парадоксы теории вероятностей]]<tex>^\star</tex><br />
*[[Схема Бернулли]]<tex>^\star</tex><br />
<br />
== Марковские цепи ==<br />
<br />
* [[Марковская цепь]]<br />
* [[Теорема о поглощении]]<br />
* [[Фундаментальная матрица]]<br />
* [[Математическое ожидание времени поглощения]]<br />
* [[Расчет вероятности поглощения в состоянии]]<br />
* [[Эргодическая марковская цепь]]<br />
* [[Регулярная марковская цепь]]<br />
* [[Примеры использования Марковских цепей]]<br />
* [[Скрытые Марковские модели]]<tex>^\star</tex><br />
* [[Алгоритм Витерби]]<tex>^\star</tex><br />
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex><br />
* [[Алгоритм Баума-Велша]]<tex>^\star</tex><br />
<br />
= Второй семестр =<br />
<br />
== Амортизационный анализ ==<br />
* [[Амортизационный анализ]]<br />
* [[Динамический массив]]<br />
* [[Hashed Array Tree]]<tex>^\star</tex><br />
* [[Список]]<br />
* [[Стек]]<br />
* [[Очередь]]<br />
* [[Дек]]<br />
* [[Мажорирующий элемент]]<br />
* [[Счетчик Кнута]]<br />
* [[Мастер-теорема]]<tex>^\star</tex><br />
* [[List order maintenance]]<tex>^\star</tex><br />
<br />
== Персистентные структуры данных ==<br />
* [[Персистентные структуры данных]]<br />
* [[Персистентный стек]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентный дек]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== [[Приоритетные очереди]] ==<br />
* [[Двоичная куча]]<br />
* [[Биномиальная куча]]<br />
* [[Фибоначчиева куча]]<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<tex>^\star</tex><br />
<br />
== Система непересекающихся множеств ==<br />
* [[СНМ (наивные реализации) | Наивные реализации]]<br />
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br />
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br />
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex><br />
<br />
== [[Поисковые структуры данных]] ==<br />
* [[Упорядоченное множество]]<br />
* [[Дерево поиска, наивная реализация]]<br />
* [[АВЛ-дерево]]<br />
* [[2-3 дерево]]<br />
* [[B-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[Декартово дерево]]<br />
* [[Декартово дерево по неявному ключу]]<br />
* [[Splay-дерево]]<br />
* [[Tango-дерево]]<tex>^\star</tex><br />
* [[Рандомизированное бинарное дерево поиска]]<br />
* [[Дерево ван Эмде Боаса]]<br />
* [[Список с пропусками]]<br />
* [[Fusion tree]]<tex>^\star</tex><br />
* [[Сверхбыстрый цифровой бор]]<br />
* [[Rope]]<tex>^\star</tex><br />
<br />
== Дерево отрезков ==<br />
<br />
* [[Статистики на отрезках. Корневая эвристика]]<br />
* [[Дерево отрезков. Построение]]<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
* [[Несогласованные поддеревья. Реализация массового обновления]]<br />
* [[Многомерное дерево отрезков]]<br />
* [[Сжатое многомерное дерево отрезков]]<br />
<br />
== Дерево Фенвика ==<br />
* [[Дерево Фенвика]]<br />
* [[Встречное дерево Фенвика]]<br />
* [[Дерево Фенвика для некоммутативных операций]]<br />
* [[Многомерное дерево Фенвика]]<br />
<br />
== Хеширование ==<br />
* [[Хеш-таблица]]<br />
* [[Разрешение коллизий]]<br />
* [[Хеширование кукушки]]<br />
* [[Идеальное хеширование]]<br />
* [[Перехеширование]]<br />
* [[Фильтр Блума]]<br />
* [[Quotient filter]]<tex>^\star</tex><br />
* [[Универсальное семейство хеш-функций]]<br />
* [[Расширяемое хеширование]]<tex>^\star</tex><br />
<br />
== [[Сортировки]] ==<br />
=== Квадратичные сортировки ===<br />
* [[Сортировка выбором]]<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка вставками]]<br />
=== Сортировки на сравнениях ===<br />
* [[Сортировка Шелла]]<tex>^\star</tex><br />
* [[Сортировка кучей]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка слиянием]]<br />
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br />
* [[Терпеливая сортировка]]<tex>^\star</tex><br />
* [[Timsort]]<tex>^\star</tex><br />
* [[Smoothsort]]<tex>^\star</tex><br />
* [[Теорема о нижней оценке для сортировки сравнениями]]<br />
<br />
=== Многопоточные сортировки ===<br />
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex><br />
* [[PSRS-сортировка]]<tex>^\star</tex><br />
=== Другие сортировки ===<br />
* [[Поиск k-ой порядковой статистики]]<br />
* [[Поиск k-ой порядковой статистики за линейное время]]<br />
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex><br />
* [[Сортировка подсчетом]]<br />
* [[Цифровая сортировка]]<br />
* [[Карманная сортировка]]<br />
* [[Сортировка Хана]]<tex>^\star</tex><br />
* [[Задача флага Нидерландов]]<tex>^\star</tex><br />
* [[Блинная сортировка]]<tex>^\star</tex><br />
<br />
== Сортирующие сети ==<br />
* [[Сортирующие сети]]<br />
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br />
* [[Сортирующие сети для квадратичных сортировок]]<br />
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex><br />
* [[Сеть Бетчера]]<br />
<br />
== Алгоритмы поиска ==<br />
* [[Целочисленный двоичный поиск]]<br />
* [[Поиск в матрице]]<tex>^\star</tex><br />
* [[Вещественный двоичный поиск]]<br />
* [[Троичный поиск]]<br />
* [[Поиск с помощью золотого сечения]]<br />
* [[Интерполяционный поиск]]<br />
* [[Метод Фибоначчи]]<tex>^\star</tex><br />
<br />
== Связь между структурами данных ==<br />
* [[Связь между структурами данных]]<br />
<br />
= Третий семестр =<br />
<br />
== Основные определения теории графов ==<br />
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]<br />
* [[Лемма о рукопожатиях]]<br />
* [[Теорема о существовании простого пути в случае существования пути]]<br />
* [[Теорема о существовании простого цикла в случае существования цикла]]<br />
* [[Матрица смежности графа]]<br />
* [[Матрица инцидентности графа]]<br />
* [[Циклическое пространство графа]]<tex>^\star</tex><br />
* [[Фундаментальные циклы графа]]<tex>^\star</tex><br />
* [[Дерево, эквивалентные определения]]<br />
* [[Алгоритмы на деревьях]]<tex>^\star</tex><br />
* [[Дополнительный, самодополнительный граф]]<br />
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex><br />
* [[Рёберное ядро]]<br />
* [[Факторизация графов]]<tex>^\star</tex><br />
<br />
== Связность в графах ==<br />
* [[Отношение связности, компоненты связности]]<br />
* [[Отношение реберной двусвязности]]<br />
* [[Отношение вершинной двусвязности]]<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Мост, эквивалентные определения]]<br />
* [[Граф компонент реберной двусвязности]]<br />
* [[Граф блоков-точек сочленения]]<br />
* [[k-связность]]<br />
* [[Теорема Менгера]]<br />
* [[Теорема Менгера, альтернативное доказательство]]<br />
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]<br />
<br />
== Остовные деревья ==<br />
=== Построение остовных деревьев ===<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
* [[Алгоритм Прима]]<br />
* [[Алгоритм Краскала]]<br />
* [[Алгоритм Борувки]]<br />
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<br />
* [[Алгоритм двух китайцев]]<br />
<br />
=== Свойства остовных деревьев ===<br />
* [[Матрица Кирхгофа]]<br />
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]<br />
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]<br />
* [[Количество помеченных деревьев]]<br />
* [[Коды Прюфера]]<br />
<br />
== Обходы графов ==<br />
=== Эйлеровы графы ===<br />
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Алгоритм построения Эйлерова цикла]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
=== Гамильтоновы графы ===<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Хватала]]<br />
* [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
* [[Теорема Поша]]<tex>^\star</tex><br />
* [[Теорема Гуйя-Ури]]<tex>^\star</tex><br />
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]<br />
* [[Теорема Гринберга]]<tex>^\star</tex><br />
* [[Турниры]]<br />
* [[Теорема Редеи-Камиона]]<br />
<br />
== Укладки графов ==<br />
* [[Укладка графа на плоскости]]<br />
* [[Формула Эйлера]]<br />
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]<br />
* [[Укладка дерева]]<br />
* [[Укладка графа с планарными компонентами реберной двусвязности]]<br />
* [[Укладка графа с планарными компонентами вершинной двусвязности]]<br />
* [[Теорема Понтрягина-Куратовского]]<br />
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex><br />
* [[Двойственный граф планарного графа]]<br />
* [[Теорема Фари]]<tex>^\star</tex><br />
* [[Гамма-алгоритм]]<br />
<br />
== Раскраски графов ==<br />
* [[Раскраска графа]]<br />
* [[Двудольные графы и раскраска в 2 цвета]]<br />
* [[Хроматический многочлен]]<br />
* [[Формула Зыкова]]<br />
* [[Формула Уитни]]<br />
* [[Теорема Брукса]]<br />
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex><br />
* [[Хроматическое число планарного графа]]<br />
* [[Многочлен Татта]]<tex>^\star</tex><br />
* [[Теория Рамсея]]<tex>^\star</tex><br />
<br />
== Обход в глубину ==<br />
* [[Обход в глубину, цвета вершин]]<br />
* [[Лемма о белых путях]]<br />
* [[Использование обхода в глубину для проверки связности]]<br />
* [[Использование обхода в глубину для поиска цикла]]<br />
* [[Использование обхода в глубину для топологической сортировки]]<br />
* [[Использование обхода в глубину для поиска компонент сильной связности]]<br />
* [[Использование обхода в глубину для поиска точек сочленения]]<br />
* [[Построение компонент вершинной двусвязности]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
* [[Построение компонент реберной двусвязности]]<br />
<br />
== Кратчайшие пути в графах ==<br />
* [[Обход в ширину]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Левита]]<tex>^\star</tex><br />
* [[Алгоритм A*]] <tex>^\star</tex><br />
* [[Алгоритм D*]] <tex>^\star</tex><br />
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex><br />
<br />
== Задача о паросочетании ==<br />
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]<br />
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]<br />
* [[Алгоритм Куна для поиска максимального паросочетания]]<br />
* [[Теорема Холла]]<br />
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]<br />
* [[Связь вершинного покрытия и независимого множества]]<br />
* [[Рёберное ядро]]<tex>^\star</tex><br />
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]<br />
* [[Теорема Татта о существовании полного паросочетания]]<br />
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]<br />
* [[Декомпозиция Эдмондса-Галлаи]]<br />
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex><br />
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex><br />
<br />
== Задача о максимальном потоке ==<br />
* [[Определение сети, потока]]<br />
* [[Разрез, лемма о потоке через разрез]]<br />
* [[Дополняющая сеть, дополняющий путь]]<br />
* [[Сложение и разность потоков]]<br />
* [[Теорема Форда-Фалкерсона]]<br />
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]<br />
* [[Алоритм Эдмондса-Карпа]]<br />
* [[Алгоритм масштабирования потока]]<br />
* [[Блокирующий поток]]<br />
* [[Схема алгоритма Диница]]<br />
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]<br />
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex><br />
* [[Алгоритм поиска блокирующего потока в ациклической сети]]<br />
* [[Метод проталкивания предпотока]]<br />
* [[Алгоритм "поднять-в-начало"]]<br />
* [[Теорема о декомпозиции]]<br />
* [[Теорема о декомпозиционном барьере]]<br />
* [[Циркуляция потока]]<br />
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex><br />
<br />
== Задача о потоке минимальной стоимости ==<br />
* [[Поток минимальной стоимости]]<br />
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]<br />
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]<br />
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]<br />
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]<br />
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]<br />
* [[Венгерский алгоритм решения задачи о назначениях]]<br />
<br />
= Четвертый семестр =<br />
<br />
== Основные определения. Простые комбинаторные свойства слов ==<br />
* [[Основные определения, связанные со строками]]<br />
* [[Период и бордер, их связь]]<br />
* [[Слово Фибоначчи]]<br />
* [[Слово Туэ-Морса]]<br />
* [[Декомпозиция Линдона]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex><br />
* [[Алгоритм Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex><br />
* [[Алгоритм Манакера]]<tex>^\star</tex><br />
<br />
== [[Поиск подстроки в строке]] ==<br />
=== Точный поиск ===<br />
* [[Наивный алгоритм поиска подстроки в строке]]<br />
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
* [[Префикс-функция]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
* [[Автомат Кнута-Морриса-Пратта]]<br />
* [[Z-функция]]<br />
* [[Бор]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
* [[Суффиксный автомат]]<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Колусси]]<tex>^\star</tex><br />
* [[Алгоритм Райта]]<tex>^\star</tex><br />
* [[Алгоритм Shift-And]]<tex>^\star</tex><br />
* [[Двусторонний алгоритм]]<tex>^\star</tex><br />
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex><br />
<br />
=== Нечёткий поиск ===<br />
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex><br />
<br />
== Суффиксное дерево ==<br />
* [[Суффиксный бор]]<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Алгоритм МакКрейта]]<tex>^\star</tex><br />
* [[Алгоритм Фарача]]<tex>^\star</tex><br />
<br />
== Суффиксный массив ==<br />
* [[Суффиксный массив]]<br />
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]<br />
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]<br />
* [[Алгоритм Касаи и др.]]<br />
* [[Алгоритм Карккайнена-Сандерса]]<br />
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]<br />
* [[Количество подпалиндромов в строке]]<tex>^\star</tex><br />
<br />
== Задача о наименьшем общем предке ==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
* [[Метод двоичного подъема]]<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)<br />
* [[Алгоритм Хьюи]]<br />
* [[Heavy-light декомпозиция]]<br />
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex><br />
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex><br />
* [[Link-Cut Tree]]<tex>^\star</tex><br />
* [[Rake-Compress деревья]]<tex>^\star</tex><br />
<br />
== Матроиды ==<br />
=== Основные факты теории матроидов ===<br />
* [[Определение матроида]]<br />
* [[Примеры матроидов]]<br />
* [[Прямая сумма матроидов]]<br />
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]<br />
* [[Теорема о базах]]<br />
* [[Аксиоматизация матроида базами]]<br />
* [[Теорема о циклах]]<br />
* [[Аксиоматизация матроида циклами]]<br />
* [[Ранговая функция, полумодулярность]]<br />
* [[Аксиоматизация матроида рангами]]<br />
* [[Двойственный матроид]]<br />
* [[Оператор замыкания для матроидов]]<br />
* [[Покрытия, закрытые множества]]<br />
* [[Матроид Вамоса]]<tex>^\star</tex><br />
<br />
=== Пересечение матроидов ===<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Граф замен]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
=== Объединение матроидов ===<br />
* [[Объединение матроидов, проверка множества на независимость]]<br />
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]<br />
* [[Алгоритм построения базы в объединении матроидов]]<br />
<br />
== Теория расписаний ==<br />
=== Общая теория ===<br />
* [[Классификация задач]]<br />
* [[Методы решения задач теории расписаний]]<br />
* [[Правило Лаулера]]<br />
<br />
=== Задачи с одним станком ===<br />
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]<br />
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]<br />
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]<br />
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]<br />
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]<br />
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]<br />
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]<br />
<br />
=== Специальные случаи задач для двух станков ===<br />
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]<br />
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]<br />
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]<br />
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]<br />
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]<br />
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]<br />
<br />
=== Задачи для произвольного числа станков ===<br />
* [[Flow shop]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]<br />
* [[PIntreepi1Lmax|<tex>P \mid Intree, p_{i} = 1 \mid L_{max}</tex>]]<br />
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]<br />
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]<br />
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]<br />
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]<br />
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]<br />
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]<br />
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]<br />
<!--* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]]--></div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=53913
Дискретная математика, алгоритмы и структуры данных
2016-05-14T14:34:01Z
<p>95.161.239.161: /* Задачи для произвольного числа станков */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
<br />
= Первый семестр =<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Отношение порядка]]<br />
*[[Отношение эквивалентности]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
*[[Транзитивный остов]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Побитовые операции]]<tex>^\star</tex><br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br />
*[[КНФ]]<br />
*[[2-SAT]]<br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
*[[Троичная логика]]<tex>^\star</tex><br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Простейшие методы синтеза схем из функциональных элементов]]<br />
*[[Метод Лупанова синтеза схем]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Троичный сумматор]]<tex>^\star</tex><br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
*[[Контактная схема]]<br />
*[[Триггеры]]<tex>^\star</tex><br />
*[[Квантовые гейты]]<tex>^\star</tex><br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex><br />
<br />
== Алгоритмы сжатия ==<br />
* [[Алгоритм Хаффмана]]<br />
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]<br />
* [[Алгоритм Хаффмана за O(n)]]<br />
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex><br />
* [[Неравенство Крафта]]<br />
* [[Неравенство Макмиллана]]<br />
* [[Код Шеннона]]<br />
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex><br />
* [[Алгоритмы LZ77 и LZ78]]<br />
* [[Алгоритм LZW]]<br />
* [[Алгоритм LZSS]]<tex>^\star</tex><br />
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br />
* [[Преобразование MTF]]<br />
* [[Расстояние Хэмминга]]<br />
* [[Избыточное кодирование, код Хэмминга]]<br />
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex><br />
<br />
== Комбинаторика ==<br />
=== Комбинаторные объекты ===<br />
* [[Комбинаторные объекты]]<br />
* [[Лексикографический порядок]]<br />
* [[Коды Грея]]<br />
* [[Коды Грея для перестановок]]<br />
* [[Коды антигрея]]<br />
* [[Цепные коды]]<br />
* [[Правильные скобочные последовательности]]<br />
<br />
=== Генерация комбинаторных объектов ===<br />
* [[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
* [[Получение номера по объекту]]<br />
* [[Получение объекта по номеру]]<br />
* [[Получение следующего объекта]]<br />
* [[Получение предыдущего объекта]]<tex>^\star</tex> <br />
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
* [[Методы генерации случайного сочетания]]<tex>^\star</tex><br />
<br />
=== Подсчёт числа объектов ===<br />
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]<br />
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
* [[Производящая функция]]<br />
* [[Лемма Бёрнсайда и Теорема Пойа]]<br />
* [[Задача об ожерельях]]<br />
* [[Числа Стирлинга первого рода]]<br />
* [[Числа Стирлинга второго рода]]<br />
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex><br />
* [[Числа Каталана]]<br />
<br />
=== Свойства комбинаторных объектов ===<br />
* [[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
* [[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
* [[Таблица инверсий]]<br />
* [[Теорема Кэли]]<br />
* [[Матричное представление перестановок]]<br />
* [[Задача о минимуме/максимуме скалярного произведения]]<br />
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
<br />
== [[Динамическое программирование]] ==<br />
=== Классические задачи динамического программирования ===<br />
*[[Кратчайший путь в ациклическом графе]]<br />
*[[Задача о числе путей в ациклическом графе]]<br />
*[[Задача о расстановке знаков в выражении]]<br />
*[[Задача о порядке перемножения матриц]]<br />
*[[Задача о наибольшей общей подпоследовательности]]<br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
*[[Задача о рюкзаке]]<br />
<br />
=== Способы оптимизации методов динамического программирования ===<br />
*[[Метод четырех русских для умножения матриц]]<br />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex><br />
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br />
*[[Meet-in-the-middle]]<tex>^\star</tex><br />
<br />
=== Другие задачи ===<br />
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex><br />
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br />
*[[Задача о наибольшей подпоследовательности-палиндроме]]<br />
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex><br />
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex><br />
*[[Динамическое программирование по профилю]]<tex>^\star</tex><br />
*[[Динамика по поддеревьям]]<br />
<br />
== Теория вероятностей ==<br />
*[[Вероятностное пространство, элементарный исход, событие]]<br />
*[[Независимые события]]<br />
*[[Условная вероятность]]<br />
*[[Формула полной вероятности]]<br />
*[[Формула Байеса]]<br />
*[[Дискретная случайная величина]]<br />
*[[Независимые случайные величины]]<br />
*[[Математическое ожидание случайной величины]]<br />
*[[Дисперсия случайной величины]]<br />
*[[Ковариация случайных величин]]<br />
*[[Корреляция случайных величин]]<br />
*[[Неравенство Маркова]]<br />
*[[Энтропия случайного источника]]<br />
*[[Симуляция одним распределением другого]]<br />
*[[Арифметическое кодирование]]<br />
*[[Парадоксы теории вероятностей]]<tex>^\star</tex><br />
*[[Схема Бернулли]]<tex>^\star</tex><br />
<br />
== Марковские цепи ==<br />
<br />
* [[Марковская цепь]]<br />
* [[Теорема о поглощении]]<br />
* [[Фундаментальная матрица]]<br />
* [[Математическое ожидание времени поглощения]]<br />
* [[Расчет вероятности поглощения в состоянии]]<br />
* [[Эргодическая марковская цепь]]<br />
* [[Регулярная марковская цепь]]<br />
* [[Примеры использования Марковских цепей]]<br />
* [[Скрытые Марковские модели]]<tex>^\star</tex><br />
* [[Алгоритм Витерби]]<tex>^\star</tex><br />
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex><br />
* [[Алгоритм Баума-Велша]]<tex>^\star</tex><br />
<br />
= Второй семестр =<br />
<br />
== Амортизационный анализ ==<br />
* [[Амортизационный анализ]]<br />
* [[Динамический массив]]<br />
* [[Hashed Array Tree]]<tex>^\star</tex><br />
* [[Список]]<br />
* [[Стек]]<br />
* [[Очередь]]<br />
* [[Дек]]<br />
* [[Мажорирующий элемент]]<br />
* [[Счетчик Кнута]]<br />
* [[Мастер-теорема]]<tex>^\star</tex><br />
* [[List order maintenance]]<tex>^\star</tex><br />
<br />
== Персистентные структуры данных ==<br />
* [[Персистентные структуры данных]]<br />
* [[Персистентный стек]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентный дек]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== [[Приоритетные очереди]] ==<br />
* [[Двоичная куча]]<br />
* [[Биномиальная куча]]<br />
* [[Фибоначчиева куча]]<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<tex>^\star</tex><br />
<br />
== Система непересекающихся множеств ==<br />
* [[СНМ (наивные реализации) | Наивные реализации]]<br />
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br />
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br />
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex><br />
<br />
== [[Поисковые структуры данных]] ==<br />
* [[Упорядоченное множество]]<br />
* [[Дерево поиска, наивная реализация]]<br />
* [[АВЛ-дерево]]<br />
* [[2-3 дерево]]<br />
* [[B-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[Декартово дерево]]<br />
* [[Декартово дерево по неявному ключу]]<br />
* [[Splay-дерево]]<br />
* [[Tango-дерево]]<tex>^\star</tex><br />
* [[Рандомизированное бинарное дерево поиска]]<br />
* [[Дерево ван Эмде Боаса]]<br />
* [[Список с пропусками]]<br />
* [[Fusion tree]]<tex>^\star</tex><br />
* [[Сверхбыстрый цифровой бор]]<br />
* [[Rope]]<tex>^\star</tex><br />
<br />
== Дерево отрезков ==<br />
<br />
* [[Статистики на отрезках. Корневая эвристика]]<br />
* [[Дерево отрезков. Построение]]<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
* [[Несогласованные поддеревья. Реализация массового обновления]]<br />
* [[Многомерное дерево отрезков]]<br />
* [[Сжатое многомерное дерево отрезков]]<br />
<br />
== Дерево Фенвика ==<br />
* [[Дерево Фенвика]]<br />
* [[Встречное дерево Фенвика]]<br />
* [[Дерево Фенвика для некоммутативных операций]]<br />
* [[Многомерное дерево Фенвика]]<br />
<br />
== Хеширование ==<br />
* [[Хеш-таблица]]<br />
* [[Разрешение коллизий]]<br />
* [[Хеширование кукушки]]<br />
* [[Идеальное хеширование]]<br />
* [[Перехеширование]]<br />
* [[Фильтр Блума]]<br />
* [[Quotient filter]]<tex>^\star</tex><br />
* [[Универсальное семейство хеш-функций]]<br />
* [[Расширяемое хеширование]]<tex>^\star</tex><br />
<br />
== [[Сортировки]] ==<br />
=== Квадратичные сортировки ===<br />
* [[Сортировка выбором]]<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка вставками]]<br />
=== Сортировки на сравнениях ===<br />
* [[Сортировка Шелла]]<tex>^\star</tex><br />
* [[Сортировка кучей]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка слиянием]]<br />
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br />
* [[Терпеливая сортировка]]<tex>^\star</tex><br />
* [[Timsort]]<tex>^\star</tex><br />
* [[Smoothsort]]<tex>^\star</tex><br />
* [[Теорема о нижней оценке для сортировки сравнениями]]<br />
<br />
=== Многопоточные сортировки ===<br />
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex><br />
* [[PSRS-сортировка]]<tex>^\star</tex><br />
=== Другие сортировки ===<br />
* [[Поиск k-ой порядковой статистики]]<br />
* [[Поиск k-ой порядковой статистики за линейное время]]<br />
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex><br />
* [[Сортировка подсчетом]]<br />
* [[Цифровая сортировка]]<br />
* [[Карманная сортировка]]<br />
* [[Сортировка Хана]]<tex>^\star</tex><br />
* [[Задача флага Нидерландов]]<tex>^\star</tex><br />
* [[Блинная сортировка]]<tex>^\star</tex><br />
<br />
== Сортирующие сети ==<br />
* [[Сортирующие сети]]<br />
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br />
* [[Сортирующие сети для квадратичных сортировок]]<br />
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex><br />
* [[Сеть Бетчера]]<br />
<br />
== Алгоритмы поиска ==<br />
* [[Целочисленный двоичный поиск]]<br />
* [[Поиск в матрице]]<tex>^\star</tex><br />
* [[Вещественный двоичный поиск]]<br />
* [[Троичный поиск]]<br />
* [[Поиск с помощью золотого сечения]]<br />
* [[Интерполяционный поиск]]<br />
* [[Метод Фибоначчи]]<tex>^\star</tex><br />
<br />
== Связь между структурами данных ==<br />
* [[Связь между структурами данных]]<br />
<br />
= Третий семестр =<br />
<br />
== Основные определения теории графов ==<br />
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]<br />
* [[Лемма о рукопожатиях]]<br />
* [[Теорема о существовании простого пути в случае существования пути]]<br />
* [[Теорема о существовании простого цикла в случае существования цикла]]<br />
* [[Матрица смежности графа]]<br />
* [[Матрица инцидентности графа]]<br />
* [[Циклическое пространство графа]]<tex>^\star</tex><br />
* [[Фундаментальные циклы графа]]<tex>^\star</tex><br />
* [[Дерево, эквивалентные определения]]<br />
* [[Алгоритмы на деревьях]]<tex>^\star</tex><br />
* [[Дополнительный, самодополнительный граф]]<br />
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex><br />
* [[Рёберное ядро]]<br />
* [[Факторизация графов]]<tex>^\star</tex><br />
<br />
== Связность в графах ==<br />
* [[Отношение связности, компоненты связности]]<br />
* [[Отношение реберной двусвязности]]<br />
* [[Отношение вершинной двусвязности]]<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Мост, эквивалентные определения]]<br />
* [[Граф компонент реберной двусвязности]]<br />
* [[Граф блоков-точек сочленения]]<br />
* [[k-связность]]<br />
* [[Теорема Менгера]]<br />
* [[Теорема Менгера, альтернативное доказательство]]<br />
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]<br />
<br />
== Остовные деревья ==<br />
=== Построение остовных деревьев ===<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
* [[Алгоритм Прима]]<br />
* [[Алгоритм Краскала]]<br />
* [[Алгоритм Борувки]]<br />
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<br />
* [[Алгоритм двух китайцев]]<br />
<br />
=== Свойства остовных деревьев ===<br />
* [[Матрица Кирхгофа]]<br />
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]<br />
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]<br />
* [[Количество помеченных деревьев]]<br />
* [[Коды Прюфера]]<br />
<br />
== Обходы графов ==<br />
=== Эйлеровы графы ===<br />
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Алгоритм построения Эйлерова цикла]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
=== Гамильтоновы графы ===<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Хватала]]<br />
* [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
* [[Теорема Поша]]<tex>^\star</tex><br />
* [[Теорема Гуйя-Ури]]<tex>^\star</tex><br />
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]<br />
* [[Теорема Гринберга]]<tex>^\star</tex><br />
* [[Турниры]]<br />
* [[Теорема Редеи-Камиона]]<br />
<br />
== Укладки графов ==<br />
* [[Укладка графа на плоскости]]<br />
* [[Формула Эйлера]]<br />
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]<br />
* [[Укладка дерева]]<br />
* [[Укладка графа с планарными компонентами реберной двусвязности]]<br />
* [[Укладка графа с планарными компонентами вершинной двусвязности]]<br />
* [[Теорема Понтрягина-Куратовского]]<br />
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex><br />
* [[Двойственный граф планарного графа]]<br />
* [[Теорема Фари]]<tex>^\star</tex><br />
* [[Гамма-алгоритм]]<br />
<br />
== Раскраски графов ==<br />
* [[Раскраска графа]]<br />
* [[Двудольные графы и раскраска в 2 цвета]]<br />
* [[Хроматический многочлен]]<br />
* [[Формула Зыкова]]<br />
* [[Формула Уитни]]<br />
* [[Теорема Брукса]]<br />
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex><br />
* [[Хроматическое число планарного графа]]<br />
* [[Многочлен Татта]]<tex>^\star</tex><br />
* [[Теория Рамсея]]<tex>^\star</tex><br />
<br />
== Обход в глубину ==<br />
* [[Обход в глубину, цвета вершин]]<br />
* [[Лемма о белых путях]]<br />
* [[Использование обхода в глубину для проверки связности]]<br />
* [[Использование обхода в глубину для поиска цикла]]<br />
* [[Использование обхода в глубину для топологической сортировки]]<br />
* [[Использование обхода в глубину для поиска компонент сильной связности]]<br />
* [[Использование обхода в глубину для поиска точек сочленения]]<br />
* [[Построение компонент вершинной двусвязности]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
* [[Построение компонент реберной двусвязности]]<br />
<br />
== Кратчайшие пути в графах ==<br />
* [[Обход в ширину]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Левита]]<tex>^\star</tex><br />
* [[Алгоритм A*]] <tex>^\star</tex><br />
* [[Алгоритм D*]] <tex>^\star</tex><br />
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex><br />
<br />
== Задача о паросочетании ==<br />
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]<br />
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]<br />
* [[Алгоритм Куна для поиска максимального паросочетания]]<br />
* [[Теорема Холла]]<br />
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]<br />
* [[Связь вершинного покрытия и независимого множества]]<br />
* [[Рёберное ядро]]<tex>^\star</tex><br />
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]<br />
* [[Теорема Татта о существовании полного паросочетания]]<br />
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]<br />
* [[Декомпозиция Эдмондса-Галлаи]]<br />
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex><br />
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex><br />
<br />
== Задача о максимальном потоке ==<br />
* [[Определение сети, потока]]<br />
* [[Разрез, лемма о потоке через разрез]]<br />
* [[Дополняющая сеть, дополняющий путь]]<br />
* [[Сложение и разность потоков]]<br />
* [[Теорема Форда-Фалкерсона]]<br />
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]<br />
* [[Алоритм Эдмондса-Карпа]]<br />
* [[Алгоритм масштабирования потока]]<br />
* [[Блокирующий поток]]<br />
* [[Схема алгоритма Диница]]<br />
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]<br />
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex><br />
* [[Алгоритм поиска блокирующего потока в ациклической сети]]<br />
* [[Метод проталкивания предпотока]]<br />
* [[Алгоритм "поднять-в-начало"]]<br />
* [[Теорема о декомпозиции]]<br />
* [[Теорема о декомпозиционном барьере]]<br />
* [[Циркуляция потока]]<br />
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex><br />
<br />
== Задача о потоке минимальной стоимости ==<br />
* [[Поток минимальной стоимости]]<br />
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]<br />
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]<br />
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]<br />
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]<br />
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]<br />
* [[Венгерский алгоритм решения задачи о назначениях]]<br />
<br />
= Четвертый семестр =<br />
<br />
== Основные определения. Простые комбинаторные свойства слов ==<br />
* [[Основные определения, связанные со строками]]<br />
* [[Период и бордер, их связь]]<br />
* [[Слово Фибоначчи]]<br />
* [[Слово Туэ-Морса]]<br />
* [[Декомпозиция Линдона]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex><br />
* [[Алгоритм Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex><br />
* [[Алгоритм Манакера]]<tex>^\star</tex><br />
<br />
== [[Поиск подстроки в строке]] ==<br />
=== Точный поиск ===<br />
* [[Наивный алгоритм поиска подстроки в строке]]<br />
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
* [[Префикс-функция]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
* [[Автомат Кнута-Морриса-Пратта]]<br />
* [[Z-функция]]<br />
* [[Бор]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
* [[Суффиксный автомат]]<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Колусси]]<tex>^\star</tex><br />
* [[Алгоритм Райта]]<tex>^\star</tex><br />
* [[Алгоритм Shift-And]]<tex>^\star</tex><br />
* [[Двусторонний алгоритм]]<tex>^\star</tex><br />
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex><br />
<br />
=== Нечёткий поиск ===<br />
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex><br />
<br />
== Суффиксное дерево ==<br />
* [[Суффиксный бор]]<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Алгоритм МакКрейта]]<tex>^\star</tex><br />
* [[Алгоритм Фарача]]<tex>^\star</tex><br />
<br />
== Суффиксный массив ==<br />
* [[Суффиксный массив]]<br />
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]<br />
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]<br />
* [[Алгоритм Касаи и др.]]<br />
* [[Алгоритм Карккайнена-Сандерса]]<br />
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]<br />
* [[Количество подпалиндромов в строке]]<tex>^\star</tex><br />
<br />
== Задача о наименьшем общем предке ==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
* [[Метод двоичного подъема]]<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)<br />
* [[Алгоритм Хьюи]]<br />
* [[Heavy-light декомпозиция]]<br />
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex><br />
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex><br />
* [[Link-Cut Tree]]<tex>^\star</tex><br />
* [[Rake-Compress деревья]]<tex>^\star</tex><br />
<br />
== Матроиды ==<br />
=== Основные факты теории матроидов ===<br />
* [[Определение матроида]]<br />
* [[Примеры матроидов]]<br />
* [[Прямая сумма матроидов]]<br />
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]<br />
* [[Теорема о базах]]<br />
* [[Аксиоматизация матроида базами]]<br />
* [[Теорема о циклах]]<br />
* [[Аксиоматизация матроида циклами]]<br />
* [[Ранговая функция, полумодулярность]]<br />
* [[Аксиоматизация матроида рангами]]<br />
* [[Двойственный матроид]]<br />
* [[Оператор замыкания для матроидов]]<br />
* [[Покрытия, закрытые множества]]<br />
* [[Матроид Вамоса]]<tex>^\star</tex><br />
<br />
=== Пересечение матроидов ===<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Граф замен]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
=== Объединение матроидов ===<br />
* [[Объединение матроидов, проверка множества на независимость]]<br />
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]<br />
* [[Алгоритм построения базы в объединении матроидов]]<br />
<br />
== Теория расписаний ==<br />
=== Общая теория ===<br />
* [[Классификация задач]]<br />
* [[Методы решения задач теории расписаний]]<br />
* [[Правило Лаулера]]<br />
<br />
=== Задачи с одним станком ===<br />
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]<br />
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]<br />
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]<br />
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]<br />
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]<br />
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]<br />
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]<br />
<br />
=== Специальные случаи задач для двух станков ===<br />
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]<br />
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]<br />
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]<br />
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]<br />
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]<br />
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]<br />
<br />
=== Задачи для произвольного числа станков ===<br />
* [[Flow shop]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]<br />
* [[Ptreepi1Lmax|<tex>P \mid Intree, p_{i} = 1 \mid L_{max}</tex>]]<br />
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]<br />
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]<br />
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]<br />
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]<br />
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]<br />
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]<br />
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]<br />
<!--* [[Opij1sumwu|<tex> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>]]--></div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=53798
Дискретная математика, алгоритмы и структуры данных
2016-05-11T12:32:23Z
<p>95.161.239.161: /* Задачи для произвольного числа станков */</p>
<hr />
<div>[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы и структуры данных]]<br />
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].<br />
<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
<br />
= Первый семестр =<br />
<br />
== Отношения ==<br />
*[[Определение отношения]]<br />
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]<br />
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br />
*[[Симметричное отношение]]<br />
*[[Антисимметричное отношение]]<br />
*[[Транзитивное отношение]]<br />
*[[Отношение порядка]]<br />
*[[Отношение эквивалентности]]<br />
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]<br />
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br />
*[[Транзитивный остов]]<br />
<br />
== Булевы функции ==<br />
*[[Определение булевой функции]]<br />
*[[Побитовые операции]]<tex>^\star</tex><br />
*[[Суперпозиции]]<br />
*[[ДНФ]]<br />
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br />
*[[КНФ]]<br />
*[[2-SAT]]<br />
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br />
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br />
*[[Полные системы функций. Теорема Поста о полной системе функций]]<br />
*[[Представление функции класса DM с помощью медианы]]<br />
*[[Пороговая функция]]<br />
*[[Троичная логика]]<tex>^\star</tex><br />
<br />
== Схемы из функциональных элементов ==<br />
*[[Реализация булевой функции схемой из функциональных элементов]]<br />
*[[Простейшие методы синтеза схем из функциональных элементов]]<br />
*[[Метод Лупанова синтеза схем]]<br />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Троичный сумматор]]<tex>^\star</tex><br />
*[[Реализация вычитания сумматором]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<br />
*[[Контактная схема]]<br />
*[[Триггеры]]<tex>^\star</tex><br />
*[[Квантовые гейты]]<tex>^\star</tex><br />
<br />
== Представление информации ==<br />
*[[Кодирование информации]]<br />
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br />
*[[Представление вещественных чисел]]<br />
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex><br />
<br />
== Алгоритмы сжатия ==<br />
* [[Алгоритм Хаффмана]]<br />
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]<br />
* [[Алгоритм Хаффмана за O(n)]]<br />
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex><br />
* [[Неравенство Крафта]]<br />
* [[Неравенство Макмиллана]]<br />
* [[Код Шеннона]]<br />
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex><br />
* [[Алгоритмы LZ77 и LZ78]]<br />
* [[Алгоритм LZW]]<br />
* [[Алгоритм LZSS]]<tex>^\star</tex><br />
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br />
* [[Преобразование MTF]]<br />
* [[Расстояние Хэмминга]]<br />
* [[Избыточное кодирование, код Хэмминга]]<br />
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex><br />
<br />
== Комбинаторика ==<br />
=== Комбинаторные объекты ===<br />
* [[Комбинаторные объекты]]<br />
* [[Лексикографический порядок]]<br />
* [[Коды Грея]]<br />
* [[Коды Грея для перестановок]]<br />
* [[Коды антигрея]]<br />
* [[Цепные коды]]<br />
* [[Правильные скобочные последовательности]]<br />
<br />
=== Генерация комбинаторных объектов ===<br />
* [[Генерация комбинаторных объектов в лексикографическом порядке]]<br />
* [[Получение номера по объекту]]<br />
* [[Получение объекта по номеру]]<br />
* [[Получение следующего объекта]]<br />
* [[Получение предыдущего объекта]]<tex>^\star</tex> <br />
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br />
* [[Методы генерации случайного сочетания]]<tex>^\star</tex><br />
<br />
=== Подсчёт числа объектов ===<br />
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]<br />
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br />
* [[Производящая функция]]<br />
* [[Лемма Бёрнсайда и Теорема Пойа]]<br />
* [[Задача об ожерельях]]<br />
* [[Числа Стирлинга первого рода]]<br />
* [[Числа Стирлинга второго рода]]<br />
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex><br />
* [[Числа Каталана]]<br />
<br />
=== Свойства комбинаторных объектов ===<br />
* [[Умножение перестановок, обратная перестановка, группа перестановок]]<br />
* [[Действие перестановки на набор из элементов, представление в виде циклов]]<br />
* [[Таблица инверсий]]<br />
* [[Теорема Кэли]]<br />
* [[Матричное представление перестановок]]<br />
* [[Задача о минимуме/максимуме скалярного произведения]]<br />
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br />
<br />
== [[Динамическое программирование]] ==<br />
=== Классические задачи динамического программирования ===<br />
*[[Кратчайший путь в ациклическом графе]]<br />
*[[Задача о числе путей в ациклическом графе]]<br />
*[[Задача о расстановке знаков в выражении]]<br />
*[[Задача о порядке перемножения матриц]]<br />
*[[Задача о наибольшей общей подпоследовательности]]<br />
*[[Задача о наибольшей возрастающей подпоследовательности]]<br />
*[[Задача коммивояжера, ДП по подмножествам]]<br />
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br />
*[[Задача о рюкзаке]]<br />
<br />
=== Способы оптимизации методов динамического программирования ===<br />
*[[Метод четырех русских для умножения матриц]]<br />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex><br />
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br />
*[[Meet-in-the-middle]]<tex>^\star</tex><br />
<br />
=== Другие задачи ===<br />
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex><br />
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br />
*[[Задача о наибольшей подпоследовательности-палиндроме]]<br />
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex><br />
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex><br />
*[[Динамическое программирование по профилю]]<tex>^\star</tex><br />
*[[Динамика по поддеревьям]]<br />
<br />
== Теория вероятностей ==<br />
*[[Вероятностное пространство, элементарный исход, событие]]<br />
*[[Независимые события]]<br />
*[[Условная вероятность]]<br />
*[[Формула полной вероятности]]<br />
*[[Формула Байеса]]<br />
*[[Дискретная случайная величина]]<br />
*[[Независимые случайные величины]]<br />
*[[Математическое ожидание случайной величины]]<br />
*[[Дисперсия случайной величины]]<br />
*[[Ковариация случайных величин]]<br />
*[[Корреляция случайных величин]]<br />
*[[Неравенство Маркова]]<br />
*[[Энтропия случайного источника]]<br />
*[[Симуляция одним распределением другого]]<br />
*[[Арифметическое кодирование]]<br />
*[[Парадоксы теории вероятностей]]<tex>^\star</tex><br />
*[[Схема Бернулли]]<tex>^\star</tex><br />
<br />
== Марковские цепи ==<br />
<br />
* [[Марковская цепь]]<br />
* [[Теорема о поглощении]]<br />
* [[Фундаментальная матрица]]<br />
* [[Математическое ожидание времени поглощения]]<br />
* [[Расчет вероятности поглощения в состоянии]]<br />
* [[Эргодическая марковская цепь]]<br />
* [[Регулярная марковская цепь]]<br />
* [[Примеры использования Марковских цепей]]<br />
* [[Скрытые Марковские модели]]<tex>^\star</tex><br />
* [[Алгоритм Витерби]]<tex>^\star</tex><br />
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex><br />
* [[Алгоритм Баума-Велша]]<tex>^\star</tex><br />
<br />
= Второй семестр =<br />
<br />
== Амортизационный анализ ==<br />
* [[Амортизационный анализ]]<br />
* [[Динамический массив]]<br />
* [[Hashed Array Tree]]<tex>^\star</tex><br />
* [[Список]]<br />
* [[Стек]]<br />
* [[Очередь]]<br />
* [[Дек]]<br />
* [[Мажорирующий элемент]]<br />
* [[Счетчик Кнута]]<br />
* [[Мастер-теорема]]<tex>^\star</tex><br />
* [[List order maintenance]]<tex>^\star</tex><br />
<br />
== Персистентные структуры данных ==<br />
* [[Персистентные структуры данных]]<br />
* [[Персистентный стек]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентный дек]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== [[Приоритетные очереди]] ==<br />
* [[Двоичная куча]]<br />
* [[Биномиальная куча]]<br />
* [[Фибоначчиева куча]]<br />
* [[Левосторонняя куча]]<br />
* [[Тонкая куча]]<br />
* [[Толстая куча на избыточном счетчике]]<br />
* [[Куча Бродала-Окасаки]]<tex>^\star</tex><br />
<br />
== Система непересекающихся множеств ==<br />
* [[СНМ (наивные реализации) | Наивные реализации]]<br />
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]<br />
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]<br />
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex><br />
<br />
== [[Поисковые структуры данных]] ==<br />
* [[Упорядоченное множество]]<br />
* [[Дерево поиска, наивная реализация]]<br />
* [[АВЛ-дерево]]<br />
* [[2-3 дерево]]<br />
* [[B-дерево]]<br />
* [[Красно-черное дерево]]<br />
* [[Декартово дерево]]<br />
* [[Декартово дерево по неявному ключу]]<br />
* [[Splay-дерево]]<br />
* [[Tango-дерево]]<tex>^\star</tex><br />
* [[Рандомизированное бинарное дерево поиска]]<br />
* [[Дерево ван Эмде Боаса]]<br />
* [[Список с пропусками]]<br />
* [[Fusion tree]]<tex>^\star</tex><br />
* [[Сверхбыстрый цифровой бор]]<br />
* [[Rope]]<tex>^\star</tex><br />
<br />
== Дерево отрезков ==<br />
<br />
* [[Статистики на отрезках. Корневая эвристика]]<br />
* [[Дерево отрезков. Построение]]<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
* [[Несогласованные поддеревья. Реализация массового обновления]]<br />
* [[Многомерное дерево отрезков]]<br />
* [[Сжатое многомерное дерево отрезков]]<br />
<br />
== Дерево Фенвика ==<br />
* [[Дерево Фенвика]]<br />
* [[Встречное дерево Фенвика]]<br />
* [[Дерево Фенвика для некоммутативных операций]]<br />
* [[Многомерное дерево Фенвика]]<br />
<br />
== Хеширование ==<br />
* [[Хеш-таблица]]<br />
* [[Разрешение коллизий]]<br />
* [[Хеширование кукушки]]<br />
* [[Идеальное хеширование]]<br />
* [[Перехеширование]]<br />
* [[Фильтр Блума]]<br />
* [[Quotient filter]]<tex>^\star</tex><br />
* [[Универсальное семейство хеш-функций]]<br />
* [[Расширяемое хеширование]]<tex>^\star</tex><br />
<br />
== [[Сортировки]] ==<br />
=== Квадратичные сортировки ===<br />
* [[Сортировка выбором]]<br />
* [[Сортировка пузырьком]]<br />
* [[Сортировка вставками]]<br />
=== Сортировки на сравнениях ===<br />
* [[Сортировка Шелла]]<tex>^\star</tex><br />
* [[Сортировка кучей]]<br />
* [[Быстрая сортировка]]<br />
* [[Сортировка слиянием]]<br />
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]<br />
* [[Терпеливая сортировка]]<tex>^\star</tex><br />
* [[Timsort]]<tex>^\star</tex><br />
* [[Smoothsort]]<tex>^\star</tex><br />
* [[Теорема о нижней оценке для сортировки сравнениями]]<br />
<br />
=== Многопоточные сортировки ===<br />
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex><br />
* [[PSRS-сортировка]]<tex>^\star</tex><br />
=== Другие сортировки ===<br />
* [[Поиск k-ой порядковой статистики]]<br />
* [[Поиск k-ой порядковой статистики за линейное время]]<br />
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex><br />
* [[Сортировка подсчетом]]<br />
* [[Цифровая сортировка]]<br />
* [[Карманная сортировка]]<br />
* [[Сортировка Хана]]<tex>^\star</tex><br />
* [[Задача флага Нидерландов]]<tex>^\star</tex><br />
* [[Блинная сортировка]]<tex>^\star</tex><br />
<br />
== Сортирующие сети ==<br />
* [[Сортирующие сети]]<br />
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]<br />
* [[Сортирующие сети для квадратичных сортировок]]<br />
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex><br />
* [[Сеть Бетчера]]<br />
<br />
== Алгоритмы поиска ==<br />
* [[Целочисленный двоичный поиск]]<br />
* [[Поиск в матрице]]<tex>^\star</tex><br />
* [[Вещественный двоичный поиск]]<br />
* [[Троичный поиск]]<br />
* [[Поиск с помощью золотого сечения]]<br />
* [[Интерполяционный поиск]]<br />
* [[Метод Фибоначчи]]<tex>^\star</tex><br />
<br />
== Связь между структурами данных ==<br />
* [[Связь между структурами данных]]<br />
<br />
= Третий семестр =<br />
<br />
== Основные определения теории графов ==<br />
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]<br />
* [[Лемма о рукопожатиях]]<br />
* [[Теорема о существовании простого пути в случае существования пути]]<br />
* [[Теорема о существовании простого цикла в случае существования цикла]]<br />
* [[Матрица смежности графа]]<br />
* [[Матрица инцидентности графа]]<br />
* [[Циклическое пространство графа]]<tex>^\star</tex><br />
* [[Фундаментальные циклы графа]]<tex>^\star</tex><br />
* [[Дерево, эквивалентные определения]]<br />
* [[Алгоритмы на деревьях]]<tex>^\star</tex><br />
* [[Дополнительный, самодополнительный граф]]<br />
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex><br />
* [[Рёберное ядро]]<br />
* [[Факторизация графов]]<tex>^\star</tex><br />
<br />
== Связность в графах ==<br />
* [[Отношение связности, компоненты связности]]<br />
* [[Отношение реберной двусвязности]]<br />
* [[Отношение вершинной двусвязности]]<br />
* [[Точка сочленения, эквивалентные определения]]<br />
* [[Мост, эквивалентные определения]]<br />
* [[Граф компонент реберной двусвязности]]<br />
* [[Граф блоков-точек сочленения]]<br />
* [[k-связность]]<br />
* [[Теорема Менгера]]<br />
* [[Теорема Менгера, альтернативное доказательство]]<br />
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]<br />
<br />
== Остовные деревья ==<br />
=== Построение остовных деревьев ===<br />
* [[Остовные деревья: определения, лемма о безопасном ребре]]<br />
* [[Алгоритм Прима]]<br />
* [[Алгоритм Краскала]]<br />
* [[Алгоритм Борувки]]<br />
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]<br />
* [[Алгоритм двух китайцев]]<br />
<br />
=== Свойства остовных деревьев ===<br />
* [[Матрица Кирхгофа]]<br />
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]<br />
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]<br />
* [[Количество помеченных деревьев]]<br />
* [[Коды Прюфера]]<br />
<br />
== Обходы графов ==<br />
=== Эйлеровы графы ===<br />
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]<br />
* [[Покрытие ребер графа путями]]<br />
* [[Алгоритм построения Эйлерова цикла]]<br />
* [[Произвольно вычерчиваемые из заданной вершины графы]]<br />
=== Гамильтоновы графы ===<br />
* [[Гамильтоновы графы]]<br />
* [[Теорема Хватала]]<br />
* [[Теорема Дирака]]<br />
* [[Теорема Оре]]<br />
* [[Теорема Поша]]<tex>^\star</tex><br />
* [[Теорема Гуйя-Ури]]<tex>^\star</tex><br />
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]<br />
* [[Теорема Гринберга]]<tex>^\star</tex><br />
* [[Турниры]]<br />
* [[Теорема Редеи-Камиона]]<br />
<br />
== Укладки графов ==<br />
* [[Укладка графа на плоскости]]<br />
* [[Формула Эйлера]]<br />
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]<br />
* [[Укладка дерева]]<br />
* [[Укладка графа с планарными компонентами реберной двусвязности]]<br />
* [[Укладка графа с планарными компонентами вершинной двусвязности]]<br />
* [[Теорема Понтрягина-Куратовского]]<br />
* [[Род, толщина, крупность, число скрещиваний]]<tex>^\star</tex><br />
* [[Двойственный граф планарного графа]]<br />
* [[Теорема Фари]]<tex>^\star</tex><br />
* [[Гамма-алгоритм]]<br />
<br />
== Раскраски графов ==<br />
* [[Раскраска графа]]<br />
* [[Двудольные графы и раскраска в 2 цвета]]<br />
* [[Хроматический многочлен]]<br />
* [[Формула Зыкова]]<br />
* [[Формула Уитни]]<br />
* [[Теорема Брукса]]<br />
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex><br />
* [[Хроматическое число планарного графа]]<br />
* [[Многочлен Татта]]<tex>^\star</tex><br />
* [[Теория Рамсея]]<tex>^\star</tex><br />
<br />
== Обход в глубину ==<br />
* [[Обход в глубину, цвета вершин]]<br />
* [[Лемма о белых путях]]<br />
* [[Использование обхода в глубину для проверки связности]]<br />
* [[Использование обхода в глубину для поиска цикла]]<br />
* [[Использование обхода в глубину для топологической сортировки]]<br />
* [[Использование обхода в глубину для поиска компонент сильной связности]]<br />
* [[Использование обхода в глубину для поиска точек сочленения]]<br />
* [[Построение компонент вершинной двусвязности]]<br />
* [[Использование обхода в глубину для поиска мостов]]<br />
* [[Построение компонент реберной двусвязности]]<br />
<br />
== Кратчайшие пути в графах ==<br />
* [[Обход в ширину]]<br />
* [[Алгоритм Форда-Беллмана]]<br />
* [[Алгоритм Дейкстры]]<br />
* [[Алгоритм Флойда]]<br />
* [[Алгоритм Джонсона]]<br />
* [[Алгоритм Левита]]<tex>^\star</tex><br />
* [[Алгоритм A*]] <tex>^\star</tex><br />
* [[Алгоритм D*]] <tex>^\star</tex><br />
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex><br />
<br />
== Задача о паросочетании ==<br />
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]<br />
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]<br />
* [[Алгоритм Куна для поиска максимального паросочетания]]<br />
* [[Теорема Холла]]<br />
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]<br />
* [[Связь вершинного покрытия и независимого множества]]<br />
* [[Рёберное ядро]]<tex>^\star</tex><br />
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]<br />
* [[Теорема Татта о существовании полного паросочетания]]<br />
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]<br />
* [[Декомпозиция Эдмондса-Галлаи]]<br />
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex><br />
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex><br />
<br />
== Задача о максимальном потоке ==<br />
* [[Определение сети, потока]]<br />
* [[Разрез, лемма о потоке через разрез]]<br />
* [[Дополняющая сеть, дополняющий путь]]<br />
* [[Сложение и разность потоков]]<br />
* [[Теорема Форда-Фалкерсона]]<br />
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]<br />
* [[Алоритм Эдмондса-Карпа]]<br />
* [[Алгоритм масштабирования потока]]<br />
* [[Блокирующий поток]]<br />
* [[Схема алгоритма Диница]]<br />
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]<br />
* [[Алгоритм Голдберга-Тарьяна]]<tex>^\star</tex><br />
* [[Алгоритм поиска блокирующего потока в ациклической сети]]<br />
* [[Метод проталкивания предпотока]]<br />
* [[Алгоритм "поднять-в-начало"]]<br />
* [[Теорема о декомпозиции]]<br />
* [[Теорема о декомпозиционном барьере]]<br />
* [[Циркуляция потока]]<br />
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex><br />
<br />
== Задача о потоке минимальной стоимости ==<br />
* [[Поток минимальной стоимости]]<br />
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]<br />
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]<br />
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]<br />
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]<br />
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]<br />
* [[Венгерский алгоритм решения задачи о назначениях]]<br />
<br />
= Четвертый семестр =<br />
<br />
== Основные определения. Простые комбинаторные свойства слов ==<br />
* [[Основные определения, связанные со строками]]<br />
* [[Период и бордер, их связь]]<br />
* [[Слово Фибоначчи]]<br />
* [[Слово Туэ-Морса]]<br />
* [[Декомпозиция Линдона]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex><br />
* [[Алгоритм Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex><br />
* [[Алгоритм Манакера]]<tex>^\star</tex><br />
<br />
== [[Поиск подстроки в строке]] ==<br />
=== Точный поиск ===<br />
* [[Наивный алгоритм поиска подстроки в строке]]<br />
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]<br />
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]<br />
* [[Префикс-функция]]<br />
* [[Алгоритм Кнута-Морриса-Пратта]]<br />
* [[Автомат Кнута-Морриса-Пратта]]<br />
* [[Z-функция]]<br />
* [[Бор]]<br />
* [[Алгоритм Ахо-Корасик]]<br />
* [[Суффиксный автомат]]<br />
* [[Алгоритм Бойера-Мура]]<br />
* [[Алгоритм Апостолико-Крочемора]]<tex>^\star</tex><br />
* [[Алгоритм Колусси]]<tex>^\star</tex><br />
* [[Алгоритм Райта]]<tex>^\star</tex><br />
* [[Алгоритм Shift-And]]<tex>^\star</tex><br />
* [[Двусторонний алгоритм]]<tex>^\star</tex><br />
* [[Турбо-алгоритм Бойера-Мура]]<tex>^\star</tex><br />
<br />
=== Нечёткий поиск ===<br />
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex><br />
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex><br />
<br />
== Суффиксное дерево ==<br />
* [[Суффиксный бор]]<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Алгоритм МакКрейта]]<tex>^\star</tex><br />
* [[Алгоритм Фарача]]<tex>^\star</tex><br />
<br />
== Суффиксный массив ==<br />
* [[Суффиксный массив]]<br />
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]<br />
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]<br />
* [[Алгоритм Касаи и др.]]<br />
* [[Алгоритм Карккайнена-Сандерса]]<br />
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]<br />
* [[Количество подпалиндромов в строке]]<tex>^\star</tex><br />
<br />
== Задача о наименьшем общем предке ==<br />
* [[Сведение задачи LCA к задаче RMQ]]<br />
* [[Сведение задачи RMQ к задаче LCA]]<br />
* [[Метод двоичного подъема]]<br />
* [[Решение RMQ с помощью разреженной таблицы]]<br />
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)<br />
* [[Алгоритм Хьюи]]<br />
* [[Heavy-light декомпозиция]]<br />
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex><br />
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex><br />
* [[Link-Cut Tree]]<tex>^\star</tex><br />
* [[Rake-Compress деревья]]<tex>^\star</tex><br />
<br />
== Матроиды ==<br />
=== Основные факты теории матроидов ===<br />
* [[Определение матроида]]<br />
* [[Примеры матроидов]]<br />
* [[Прямая сумма матроидов]]<br />
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]<br />
* [[Теорема о базах]]<br />
* [[Аксиоматизация матроида базами]]<br />
* [[Теорема о циклах]]<br />
* [[Аксиоматизация матроида циклами]]<br />
* [[Ранговая функция, полумодулярность]]<br />
* [[Аксиоматизация матроида рангами]]<br />
* [[Двойственный матроид]]<br />
* [[Оператор замыкания для матроидов]]<br />
* [[Покрытия, закрытые множества]]<br />
* [[Матроид Вамоса]]<tex>^\star</tex><br />
<br />
=== Пересечение матроидов ===<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Граф замен]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
=== Объединение матроидов ===<br />
* [[Объединение матроидов, проверка множества на независимость]]<br />
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]<br />
* [[Алгоритм построения базы в объединении матроидов]]<br />
<br />
== Теория расписаний ==<br />
=== Общая теория ===<br />
* [[Классификация задач]]<br />
* [[Методы решения задач теории расписаний]]<br />
* [[Правило Лаулера]]<br />
<br />
=== Задачи с одним станком ===<br />
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]<br />
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]<br />
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]<br />
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]<br />
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]<br />
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]<br />
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]<br />
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]<br />
<br />
=== Специальные случаи задач для двух станков ===<br />
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]<br />
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]<br />
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]<br />
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]<br />
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]<br />
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]<br />
<br />
=== Задачи для произвольного числа станков ===<br />
* [[Flow shop]]<br />
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]<br />
* [[Ptreepi1Lmax|<tex>P \mid Tree, p_{i} = 1 \mid L_{max}</tex>]]<br />
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]<br />
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]<br />
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]<br />
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]<br />
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]<br />
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]</div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B9%D1%82%D0%B0&diff=52756
Алгоритм Райта
2016-03-21T14:53:08Z
<p>95.161.239.161: /* Асимптотика */</p>
<hr />
<div>'''Алгоритм Райта''' {{---}} алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]] и улучшающий его асимптотику<br />
<br />
==Описание алгоритма==<br />
Алгоритм Райта ищет образец <tex>x</tex> в заданном тексте <tex>y</tex> сравнивания их символы. Сравнение происходит в следующем порядке (окном текста <tex>y</tex> будем называть последовательность символов <tex>i \dots m - i + 1</tex>, где <tex>m</tex> {{---}} длина образца <tex>x</tex>):<br />
<br />
# '''Последний''' символ образца сравнивается с самым '''правым''' символом окна.<br />
# Если они совпадают, то '''первый''' символ сравнивается с самым '''левым''' символом окна.<br />
# Если они опять совпали, то сравниваются символы, находящиеся по середине образца и окна.<br />
<br />
Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае, выполняем функцию сдвига плохого символа, которая обрабона в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]].<br />
<br />
==Псевдокод==<br />
<br />
'''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n) {<br />
'''int'''[] bmBc<br />
'''char''' c, firstCh, middleCh, lastCh;<br />
'''if''' (m == 0)<br />
'''return'''<br />
'''else if''' (m == 1) {<br />
<font color=green>//Проверка на случай поиска вхождения одного символа</font><br />
'''int''' match = 0<br />
'''while''' (match < n) {<br />
match = findFirst(y, match, n - 1, x[0])<br />
'''if''' (match != -1) {<br />
'''print'''(match)<br />
}<br />
'''else'''<br />
'''print'''(<font color=green>"No matches"</font>)<br />
'''return'''<br />
}<br />
}<br />
'''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol){<br />
'''for''' (i = fromIndex .. toIndex){<br />
'''if''' (y[i] == symbol){<br />
'''return''' i<br />
}<br />
}<br />
'''return''' -1<br />
}<br />
'''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex){<br />
'''for''' (i = fromIndex .. toIndex){<br />
'''if''' (y[i] != x[i - fromIndex + 1]){<br />
'''return''' false<br />
}<br />
}<br />
'''return''' true<br />
}<br />
<font color=green> //Стадия препроцессинга</font><br />
'''int'''[] preBmBc('''char'''[] x, '''int''' m) {<br />
'''int'''[] result = '''int'''[m]<br />
'''for''' (i = 0 .. m - 1){<br />
result[i] = m;<br />
}<br />
'''for''' (i = 0 .. m - 2){<br />
result[x[i]] = m - i - 1;<br />
}<br />
'''return''' result<br />
}<br />
bmBc = preBmBc (x, m)<br />
firstCh = x[0];<br />
middleCh = x[m/2];<br />
lastCh = x[m - 1];<br />
<font color=green>//Поиск</font><br />
'''int''' j = 0<br />
'''while''' (j <= n - m) {<br />
c = y[j + m - 1]<br />
'''if''' (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&<br />
restEquals(y, j + 1, x, j + m - 2)){<br />
'''print'''(j)<br />
'''return'''<br />
}<br />
j += bmBc[c];<br />
}<br />
'''print'''(<font color=green>"No matches"</font>)<br />
}<br />
<br />
==Асимптотика==<br />
* Фаза препроцессинга требует <tex>O(m)</tex> времени и памяти<br />
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.<br />
<br />
==Пример==<br />
<br />
==Источники информации==<br />
* RAITA T., 1992, Tuning the Boyer-Moore-Horspool string searching algorithm, Software - Practice & Experience, 22(10):879-884.<br />
* [http://www-igm.univ-mlv.fr/~lecroq/string/node22.html#SECTION00220 Raita algorithm]<br />
* [https://en.wikipedia.org/wiki/Raita_algorithm Raita algorithm на англ вики]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]] <br />
[[Категория: Поиск подстроки в строке]]<br />
[[Категория: Точный поиск]]</div>
95.161.239.161
http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B9%D1%82%D0%B0&diff=52703
Алгоритм Райта
2016-03-18T21:12:13Z
<p>95.161.239.161: </p>
<hr />
<div>'''Алгоритм Райта''' {{---}} алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]] и улучшающий его асимптотику<br />
<br />
==Описание алгоритма==<br />
Алгоритм Райта ищет образец <tex>x</tex> в заданном тексте <tex>y</tex> сравнивания их символы. Сравнение происходит в следующем порядке (окном текста <tex>y</tex> будем называть последовательность символов <tex>i \dots m - i + 1</tex>, где <tex>m</tex> {{---}} длина образца <tex>x</tex>):<br />
<br />
# '''Последний''' символ образца сравнивается с самым '''правым''' символом окна.<br />
# Если они совпадают, то '''первый''' символ сравнивается с самым '''левым''' символом окна.<br />
# Если они опять совпали, то сравниваются символы, находящиеся по середине образца и окна.<br />
<br />
Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае, выполняем функцию сдвига плохого символа, которая обрабона в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]].<br />
<br />
==Псевдокод==<br />
<br />
'''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n) {<br />
'''int'''[] bmBc<br />
'''char''' c, firstCh, middleCh, lastCh;<br />
'''if''' (m == 0)<br />
'''return'''<br />
'''else if''' (m == 1) {<br />
<font color=green>//Проверка на случай поиска вхождения одного символа</font><br />
'''int''' match = 0<br />
'''while''' (match < n) {<br />
match = findFirst(y, match, n - 1, x[0])<br />
'''if''' (match != -1) {<br />
'''print'''(match)<br />
}<br />
'''else'''<br />
'''print'''(<font color=green>"No matches"</font>)<br />
'''return'''<br />
}<br />
}<br />
'''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol){<br />
'''for''' (i = fromIndex .. toIndex){<br />
'''if''' (y[i] == symbol){<br />
'''return''' i<br />
}<br />
}<br />
'''return''' -1<br />
}<br />
'''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex){<br />
'''for''' (i = fromIndex .. toIndex){<br />
'''if''' (y[i] != x[i - fromIndex + 1]){<br />
'''return''' false<br />
}<br />
}<br />
'''return''' true<br />
}<br />
<font color=green> //Стадия препроцессинга</font><br />
'''int'''[] preBmBc('''char'''[] x, '''int''' m) {<br />
'''int'''[] result = '''int'''[m]<br />
'''for''' (i = 0 .. m - 1){<br />
result[i] = m;<br />
}<br />
'''for''' (i = 0 .. m - 2){<br />
result[x[i]] = m - i - 1;<br />
}<br />
'''return''' result<br />
}<br />
bmBc = preBmBc (x, m)<br />
firstCh = x[0];<br />
middleCh = x[m/2];<br />
lastCh = x[m - 1];<br />
<font color=green>//Поиск</font><br />
'''int''' j = 0<br />
'''while''' (j <= n - m) {<br />
c = y[j + m - 1]<br />
'''if''' (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&<br />
restEquals(y, j + 1, x, j + m - 2)){<br />
'''print'''(j)<br />
'''return'''<br />
}<br />
j += bmBc[c];<br />
}<br />
'''print'''(<font color=green>"No matches"</font>)<br />
}<br />
<br />
==Асимптотика==<br />
<br />
==Пример==<br />
<br />
==Источники информации==<br />
* RAITA T., 1992, Tuning the Boyer-Moore-Horspool string searching algorithm, Software - Practice & Experience, 22(10):879-884.<br />
* [http://www-igm.univ-mlv.fr/~lecroq/string/node22.html#SECTION00220 Raita algorithm]<br />
* [https://en.wikipedia.org/wiki/Raita_algorithm Raita algorithm на англ вики]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]] <br />
[[Категория: Поиск подстроки в строке]]<br />
[[Категория: Точный поиск]]</div>
95.161.239.161