Викиконспекты - Вклад участника [ru]

1ripipsumwu

2015-06-16T15:56:41Z

Pokrasko: /* Прочие задачи */

<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>

{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}

== Алгоритм ==

=== Предисловие ===

Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из <tex>n^2</tex> значений.

{{Лемма
|statement=
Существует оптимальное расписание, в котором время начала каждой работы <tex>t_j</tex> принадлежит множеству:
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>

|proof=
Рассмотрим оптимальное расписание <tex>S</tex>. Пусть <tex>j_1, \dots, j_n</tex> — работы в <tex>S</tex> в порядке неубывания дедлайна. Выполнимое расписание может быть получено из <tex>S</tex> следующим образом. Первая работа <tex>j_1</tex> может быть сдвинута влево до времени своего появления. Тогда работа <tex>j_2</tex> сдвигается влево до времени своего появления или времени завершения работы <tex>j_1</tex>. В общем, <tex>j_i</tex> сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы <tex>j_{i - 1}</tex>.
}}

Для любого <tex>k \leqslant n</tex> и <tex>s, e \in T</tex> таких, что <tex>s \leqslant e</tex>, пусть <tex>U_k (s, e)</tex> — множество работ <tex>j \leqslant k</tex> таких, что <tex>s \leqslant r_i \leqslant e</tex>. Кроме того, пусть <tex>W^*_k (s, e)</tex> — максимальный суммарный вес подмножества <tex>U_k (s, e)</tex> такого, что существует выполнимое расписание <tex>S</tex> для работ из этого подмножества такое, что:
* <tex>S</tex> свободно до времени <tex>s + p</tex> и после времени <tex>e</tex>,
* время начала работ в <tex>S</tex> принадлежат <tex>T</tex>.
<tex>W^*_k (s, e) = 0</tex>, если ни для какого подмножества работ не существует выполнимого расписания.

=== Псевдокод ===

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
<tex>W_0 (s, e) \leftarrow 0</tex>
'''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
'''if''' <tex>r_k \not\in [s, e)</tex>
<tex>W_k (s, e) \leftarrow W_{k - 1} (s, e)</tex>
'''else'''
<tex>W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;</tex>
<tex>\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}</tex>
<tex>W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}</tex>
'''return''' <tex>W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)</tex>

Заметим, что <tex>W'_k (s, e)</tex> соответствует выполнимому расписанию, в котором работа <tex>k</tex> начинается в момент времени <tex>s'</tex>.

=== Время работы ===

По лемме <tex>T</tex> содержит <tex>O(n^2)</tex> элементов. В каждой итерации алгоритма мы выбираем времена <tex>s</tex> и <tex>e</tex> из <tex>T</tex>, а для каждой такой пары ищем необходимое время <tex>s'</tex>. Из того, что итераций <tex>n</tex>, получаем, что алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени.

=== Корректность алгоритма ===

Покажем, что вычисленное алгоритмом <tex>W_k (s, e)</tex> равно <tex>W^*_k (s, e)</tex>, то есть возвращаемое им значение является оптимальным решением.

{{Теорема
|statement=
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняется:
<tex>W_k (s, e) = W^*_k (s, e)</tex>

|proof=
Докажем индукцией по <tex>k</tex>. Очевидно, что утверждение выполняется при <tex>k = 0</tex>. Допустим, что оно выполняется при <tex>k - 1</tex>.

Если <tex>r_k \not\in [s, e)</tex>, то <tex>U_k (s, e) = U_{k - 1} (s, e)</tex>, из чего следует, что <tex>W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)</tex>. Осталось показать, что:
<tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)</tex>, если <tex>r_k \in [s, e)</tex>.
Рассмотрим два неравенства:

# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, e)</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
#:* работы <tex>k</tex>, выполняющейся в <tex>[s', s' + p]</tex>,
#:* подмножества работ <tex>U_{k - 1} (s, s')</tex>, выполняющихся в <tex>[s + p, s']</tex>,
#:* подмножества работ <tex>U_{k - 1} (s', e)</tex>, выполняющихся в <tex>[s' + p, e]</tex>.
#:
# <tex>W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}</tex>
#: Пусть <tex>Z</tex> - подмножество <tex>U_k (s, e)</tex>, соответствующее <tex>W^*_k (s, e)</tex>. Если <tex>k \not\in Z</tex>, то <tex>W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)</tex> и неравенство доказано. Иначе, пусть <tex>S^*</tex> - расписание, соответствующее <tex>W^*_k (s, e)</tex>, и <tex>s'</tex> - время начала работы <tex>k</tex>. Нужно, чтобы выполнялось неравенство: <tex>\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>.
#:
#: Обозначим за <tex>Z^b</tex> и <tex>Z^a</tex> подмножества работ <tex>Z</tex>, которые в <tex>S^*</tex> выполняются до и после работы <tex>k</tex> соответственно. Можем предположить, что времена появления всех работ в <tex>Z^a</tex> больше, чем время <tex>s'</tex> начала работы <tex>k</tex>. Иначе, пусть <tex>i</tex> - работа в <tex>Z^a</tex> такая, что <tex>r_i \le s'</tex>. Так как работы отсортированы в порядке неубывания дедлайна, то <tex>d_i \le d_k</tex>. Таким образом, при перестановке работ <tex>i</tex> и <tex>k</tex> в <tex>S^*</tex> суммарный вес не изменится. Продолжим этот процесс, пока новое расписание <tex>S^*</tex> удовлетворяет нужному свойству. Получим:
#: <tex>W^*_k (s, e) = \sum \limits_{j \in Z} w_j = \sum \limits_{j \in Z^b} w_j + w_k + \sum \limits_{j \in Z^a} \leqslant W^*_{k - 1} (s, s') + w_k + W^*_{k - 1} (s', e) = W_{k - 1} (s, s') + w_k + W_{k - 1} (s', e) \leqslant W'_k (s, e)</tex>
#:, так как очевидно, что <tex>Z^b \subseteq U_{k - 1} (s, s')</tex>, и, по предположению, выполняется <tex>Z^a \subseteq U_{k - 1} (s', e)</tex>.
}}

== Прочие задачи ==

Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист (''Philippe Baptiste''), его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.

== См. также ==

* [[P1sumu]]
* [[1pi1sumwu]]

== Источники информации ==

* Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Дискретная математика, алгоритмы и структуры данных

2015-06-16T15:49:00Z

Pokrasko:

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

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

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

== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Квантовые гейты]]<tex>^\star</tex>

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>

== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]

=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]

=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]

== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]

=== Способы оптимизации методов динамического программирования ===
*[[Метод четырех русских для умножения матриц]]<tex>^\star</tex>
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>

=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Дисперсия случайной величины]]
*[[Ковариация случайных величин]]
*[[Корреляция случайных величин]]
*[[Неравенство Маркова]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Парадоксы теории вероятностей]]<tex>^\star</tex>
*[[Схема Бернулли]]<tex>^\star</tex>

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

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
* [[Примеры использования Марковских цепей]]
* [[Скрытые Марковские модели]]<tex>^\star</tex>
* [[Алгоритм Витерби]]<tex>^\star</tex>
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>

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

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Динамический массив]]
* [[Hashed Array Tree]]<tex>^\star</tex>
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Мажорирующий элемент]]
* [[Счетчик Кнута]]
* [[Мастер-теорема]]<tex>^\star</tex>

== Персистентные структуры данных ==
* [[Персистентные структуры данных]]
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[Персистентная приоритетная очередь]]

== [[Приоритетные очереди]] ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
* [[Тонкая куча]]
* [[Толстая куча на избыточном счетчике]]
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>

== [[Поисковые структуры данных]] ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Tango-дерево]]<tex>^\star</tex>
* [[Рандомизированное бинарное дерево поиска]]
* [[Дерево ван Эмде Боаса]]
* [[Список с пропусками]]
* [[Fusion tree]]<tex>^\star</tex>
* [[Сверхбыстрый цифровой бор]]
* [[Rope]]<tex>^\star</tex>

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

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеш-таблица]]
* [[Разрешение коллизий]]
* [[Хеширование кукушки]]
* [[Идеальное хеширование]]
* [[Перехеширование]]
* [[Фильтр Блума]]
* [[Quotient filter]]<tex>^\star</tex>
* [[Универсальное семейство хеш-функций]]
* [[Расширяемое хеширование]]<tex>^\star</tex>

== [[Сортировки]] ==
=== Квадратичные сортировки ===
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
=== Сортировки на сравнениях ===
* [[Сортировка Шелла]]<tex>^\star</tex>
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Терпеливая сортировка]]<tex>^\star</tex>
* [[Timsort]]<tex>^\star</tex>
* [[Smoothsort]]<tex>^\star</tex>
* [[Теорема о нижней оценке для сортировки сравнениями]]

=== Многопоточные сортировки ===
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
* [[PSRS-сортировка]]<tex>^\star</tex>
=== Другие сортировки ===
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-ой порядковой статистики за линейное время]]
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
* [[Сортировка подсчетом]]
* [[Цифровая сортировка]]
* [[Карманная сортировка]]
* [[Сортировка Хана]]<tex>^\star</tex>
* [[Задача флага Нидерландов]]<tex>^\star</tex>

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Целочисленный двоичный поиск]]
* [[Вещественный двоичный поиск]]
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]

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

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

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Левита]]<tex>^\star</tex>
* [[Алгоритм Флойда]]
* [[Алгоритм A*]] <tex>^\star</tex>
* [[Алгоритм Джонсона]]
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
* [[Алгоритм D*]] <tex>^\star</tex>

== Задача о паросочетании ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

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

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
* [[Декомпозиция Линдона]]<tex>^\star</tex>
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
* [[Алгоритм Крочемора]]<tex>^\star</tex>
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>

== [[Поиск подстроки в строке]] ==
=== Точный поиск ===
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Автомат Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]
* [[Алгоритм Бойера-Мура]]
* [[Алгоритм Колусси]]<tex>^\star</tex>
* [[Алгоритм Shift-And]]<tex>^\star</tex>
* [[Двусторонний алгоритм]]<tex>^\star</tex>

=== Нечёткий поиск ===
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex>
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex>

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
* [[Алгоритм Фарача]]<tex>^\star</tex>

== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== Задача о наименьшем общем предке ==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Сведение задачи RMQ к задаче LCA]]
* [[Метод двоичного подъема]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Heavy-light декомпозиция]]
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
* [[Link-Cut Tree]]<tex>^\star</tex>

== Матроиды ==
=== Основные факты теории матроидов ===
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Аксиоматизация матроида рангами]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Покрытия, закрытые множества]]
* [[Матроид Вамоса]]<tex>^\star</tex>

=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]

=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]

== Теория расписаний ==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[Flow shop]]
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]

Дискретная математика, алгоритмы и структуры данных

2015-06-16T15:48:22Z

Pokrasko: /* Теория расписаний */

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

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

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

== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Квантовые гейты]]<tex>^\star</tex>

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>

== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]

=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]

=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]

== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]

=== Способы оптимизации методов динамического программирования ===
*[[Метод четырех русских для умножения матриц]]<tex>^\star</tex>
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>

=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Дисперсия случайной величины]]
*[[Ковариация случайных величин]]
*[[Корреляция случайных величин]]
*[[Неравенство Маркова]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Парадоксы теории вероятностей]]<tex>^\star</tex>
*[[Схема Бернулли]]<tex>^\star</tex>

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

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
* [[Примеры использования Марковских цепей]]
* [[Скрытые Марковские модели]]<tex>^\star</tex>
* [[Алгоритм Витерби]]<tex>^\star</tex>
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>

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

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Динамический массив]]
* [[Hashed Array Tree]]<tex>^\star</tex>
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Мажорирующий элемент]]
* [[Счетчик Кнута]]
* [[Мастер-теорема]]<tex>^\star</tex>

== Персистентные структуры данных ==
* [[Персистентные структуры данных]]
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[Персистентная приоритетная очередь]]

== [[Приоритетные очереди]] ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
* [[Тонкая куча]]
* [[Толстая куча на избыточном счетчике]]
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>

== [[Поисковые структуры данных]] ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Tango-дерево]]<tex>^\star</tex>
* [[Рандомизированное бинарное дерево поиска]]
* [[Дерево ван Эмде Боаса]]
* [[Список с пропусками]]
* [[Fusion tree]]<tex>^\star</tex>
* [[Сверхбыстрый цифровой бор]]
* [[Rope]]<tex>^\star</tex>

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

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеш-таблица]]
* [[Разрешение коллизий]]
* [[Хеширование кукушки]]
* [[Идеальное хеширование]]
* [[Перехеширование]]
* [[Фильтр Блума]]
* [[Quotient filter]]<tex>^\star</tex>
* [[Универсальное семейство хеш-функций]]
* [[Расширяемое хеширование]]<tex>^\star</tex>

== [[Сортировки]] ==
=== Квадратичные сортировки ===
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
=== Сортировки на сравнениях ===
* [[Сортировка Шелла]]<tex>^\star</tex>
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Терпеливая сортировка]]<tex>^\star</tex>
* [[Timsort]]<tex>^\star</tex>
* [[Smoothsort]]<tex>^\star</tex>
* [[Теорема о нижней оценке для сортировки сравнениями]]

=== Многопоточные сортировки ===
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
* [[PSRS-сортировка]]<tex>^\star</tex>
=== Другие сортировки ===
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-ой порядковой статистики за линейное время]]
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
* [[Сортировка подсчетом]]
* [[Цифровая сортировка]]
* [[Карманная сортировка]]
* [[Сортировка Хана]]<tex>^\star</tex>
* [[Задача флага Нидерландов]]<tex>^\star</tex>

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Целочисленный двоичный поиск]]
* [[Вещественный двоичный поиск]]
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]

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

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

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Левита]]<tex>^\star</tex>
* [[Алгоритм Флойда]]
* [[Алгоритм A*]] <tex>^\star</tex>
* [[Алгоритм Джонсона]]
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
* [[Алгоритм D*]] <tex>^\star</tex>

== Задача о паросочетании ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

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

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
* [[Декомпозиция Линдона]]<tex>^\star</tex>
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
* [[Алгоритм Крочемора]]<tex>^\star</tex>
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>

== [[Поиск подстроки в строке]] ==
=== Точный поиск ===
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Автомат Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]
* [[Алгоритм Бойера-Мура]]
* [[Алгоритм Колусси]]<tex>^\star</tex>
* [[Алгоритм Shift-And]]<tex>^\star</tex>
* [[Двусторонний алгоритм]]<tex>^\star</tex>

=== Нечёткий поиск ===
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex>
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex>

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
* [[Алгоритм Фарача]]<tex>^\star</tex>

== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== Задача о наименьшем общем предке ==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Сведение задачи RMQ к задаче LCA]]
* [[Метод двоичного подъема]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Heavy-light декомпозиция]]
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
* [[Link-Cut Tree]]<tex>^\star</tex>

== Матроиды ==
=== Основные факты теории матроидов ===
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Аксиоматизация матроида рангами]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Покрытия, закрытые множества]]
* [[Матроид Вамоса]]<tex>^\star</tex>

=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]

=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]

== Теория расписаний ==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[Flow shop]]
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[1ripipsumwu|<tex> 1 \mid r_i; p_i = p \mid \sum w_i U_i</tex>]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]

Дискретная математика, алгоритмы и структуры данных

2015-06-16T15:47:59Z

Pokrasko:

[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

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

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

== Отношения ==
*[[Определение отношения]]
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
*[[КНФ]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]
*[[Троичная логика]]<tex>^\star</tex>

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Метод Лупанова синтеза схем]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Троичный сумматор]]<tex>^\star</tex>
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]
*[[Контактная схема]]
*[[Квантовые гейты]]<tex>^\star</tex>

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>

== Алгоритмы сжатия ==
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
* [[Алгоритм Хаффмана за O(n)]]
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
* [[Неравенство Крафта]]
* [[Неравенство Макмиллана]]
* [[Код Шеннона]]
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
* [[Алгоритмы LZ77 и LZ78]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]<tex>^\star</tex>
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
* [[Преобразование MTF]]
* [[Расстояние Хэмминга]]
* [[Избыточное кодирование, код Хэмминга]]
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>

== Комбинаторика ==
=== Комбинаторные объекты ===
* [[Комбинаторные объекты]]
* [[Лексикографический порядок]]
* [[Коды Грея]]
* [[Коды Грея для перестановок]]
* [[Коды антигрея]]
* [[Цепные коды]]
* [[Правильные скобочные последовательности]]

=== Генерация комбинаторных объектов ===
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение номера по объекту]]
* [[Получение объекта по номеру]]
* [[Получение следующего объекта]]
* [[Получение предыдущего объекта]]<tex>^\star</tex>
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>

=== Подсчёт числа объектов ===
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* [[Производящая функция]]
* [[Лемма Бёрнсайда и Теорема Пойа]]
* [[Задача об ожерельях]]
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
* [[Числа Каталана]]

=== Свойства комбинаторных объектов ===
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]

== [[Динамическое программирование]] ==
=== Классические задачи динамического программирования ===
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о числе путей в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о рюкзаке]]

=== Способы оптимизации методов динамического программирования ===
*[[Метод четырех русских для умножения матриц]]<tex>^\star</tex>
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Meet-in-the-middle]]<tex>^\star</tex>

=== Другие задачи ===
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Наибольшая общая возрастающая подпоследовательность]]<tex>^\star</tex>
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
*[[Динамика по поддеревьям]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Дисперсия случайной величины]]
*[[Ковариация случайных величин]]
*[[Корреляция случайных величин]]
*[[Неравенство Маркова]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Парадоксы теории вероятностей]]<tex>^\star</tex>
*[[Схема Бернулли]]<tex>^\star</tex>

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

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
* [[Примеры использования Марковских цепей]]
* [[Скрытые Марковские модели]]<tex>^\star</tex>
* [[Алгоритм Витерби]]<tex>^\star</tex>
* [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
* [[Алгоритм Баума-Велша]]<tex>^\star</tex>

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

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Динамический массив]]
* [[Hashed Array Tree]]<tex>^\star</tex>
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Мажорирующий элемент]]
* [[Счетчик Кнута]]
* [[Мастер-теорема]]<tex>^\star</tex>

== Персистентные структуры данных ==
* [[Персистентные структуры данных]]
* [[Персистентный стек]]
* [[Персистентная очередь]]
* [[Персистентный дек]]
* [[Персистентная приоритетная очередь]]

== [[Приоритетные очереди]] ==
* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]
* [[Тонкая куча]]
* [[Толстая куча на избыточном счетчике]]
* [[Куча Бродала-Окасаки]]<tex>^\star</tex>

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]
* [[СНМ с операцией удаления за О(1)]]<tex>^\star</tex>

== [[Поисковые структуры данных]] ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Tango-дерево]]<tex>^\star</tex>
* [[Рандомизированное бинарное дерево поиска]]
* [[Дерево ван Эмде Боаса]]
* [[Список с пропусками]]
* [[Fusion tree]]<tex>^\star</tex>
* [[Сверхбыстрый цифровой бор]]
* [[Rope]]<tex>^\star</tex>

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

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеш-таблица]]
* [[Разрешение коллизий]]
* [[Хеширование кукушки]]
* [[Идеальное хеширование]]
* [[Перехеширование]]
* [[Фильтр Блума]]
* [[Quotient filter]]<tex>^\star</tex>
* [[Универсальное семейство хеш-функций]]
* [[Расширяемое хеширование]]<tex>^\star</tex>

== [[Сортировки]] ==
=== Квадратичные сортировки ===
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
=== Сортировки на сравнениях ===
* [[Сортировка Шелла]]<tex>^\star</tex>
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Терпеливая сортировка]]<tex>^\star</tex>
* [[Timsort]]<tex>^\star</tex>
* [[Smoothsort]]<tex>^\star</tex>
* [[Теорема о нижней оценке для сортировки сравнениями]]

=== Многопоточные сортировки ===
* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>
* [[PSRS-сортировка]]<tex>^\star</tex>
=== Другие сортировки ===
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-ой порядковой статистики за линейное время]]
* [[Поиск k-ой порядковой статистики в двух массивах]]<tex>^\star</tex>
* [[Сортировка подсчетом]]
* [[Цифровая сортировка]]
* [[Карманная сортировка]]
* [[Сортировка Хана]]<tex>^\star</tex>
* [[Задача флага Нидерландов]]<tex>^\star</tex>

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Целочисленный двоичный поиск]]
* [[Вещественный двоичный поиск]]
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]

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

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

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]<tex>^\star</tex>
* [[Фундаментальные циклы графа]]<tex>^\star</tex>
* [[Дерево, эквивалентные определения]]
* [[Алгоритмы на деревьях]]<tex>^\star</tex>
* [[Дополнительный, самодополнительный граф]]
* [[Теоретико-множественные операции над графами]]<tex>^\star</tex>

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Теорема Менгера, альтернативное доказательство]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
=== Построение остовных деревьев ===
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

=== Свойства остовных деревьев ===
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
=== Гамильтоновы графы ===
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Поша]]<tex>^\star</tex>
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
* [[Теорема Гринберга]]<tex>^\star</tex>
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]
* [[Теорема Фари]]<tex>^\star</tex>

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex>
* [[Хроматическое число планарного графа]]
* [[Многочлен Татта]]<tex>^\star</tex>
* [[Теория Рамсея]]<tex>^\star</tex>

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Левита]]<tex>^\star</tex>
* [[Алгоритм Флойда]]
* [[Алгоритм A*]] <tex>^\star</tex>
* [[Алгоритм Джонсона]]
* [[Эвристики для поиска кратчайших путей]]<tex>^\star</tex>
* [[Алгоритм D*]] <tex>^\star</tex>

== Задача о паросочетании ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Теорема Татта о существовании полного паросочетания]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]
* [[Декомпозиция Эдмондса-Галлаи]]
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex>

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]
* [[Алгоритм Каргера для нахождения минимального разреза]]<tex>^\star</tex>

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

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

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]
* [[Декомпозиция Линдона]]<tex>^\star</tex>
* [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
* [[Алгоритм Крочемора]]<tex>^\star</tex>
* [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>

== [[Поиск подстроки в строке]] ==
=== Точный поиск ===
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Автомат Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]
* [[Алгоритм Бойера-Мура]]
* [[Алгоритм Колусси]]<tex>^\star</tex>
* [[Алгоритм Shift-And]]<tex>^\star</tex>
* [[Двусторонний алгоритм]]<tex>^\star</tex>

=== Нечёткий поиск ===
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex>
* [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex>

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]
* [[Алгоритм МакКрейта]]<tex>^\star</tex>
* [[Алгоритм Фарача]]<tex>^\star</tex>

== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== Задача о наименьшем общем предке ==
* [[Сведение задачи LCA к задаче RMQ]]
* [[Сведение задачи RMQ к задаче LCA]]
* [[Метод двоичного подъема]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Heavy-light декомпозиция]]
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
* [[Link-Cut Tree]]<tex>^\star</tex>

== Матроиды ==
=== Основные факты теории матроидов ===
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Аксиоматизация матроида рангами]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
* [[Покрытия, закрытые множества]]
* [[Матроид Вамоса]]<tex>^\star</tex>

=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]

=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]

== Теория расписаний ==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[Flow shop]]
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[1ripipsumwu|<tex> 1 \mid r_i; p_i = p; \mid \sum w_i U_i</tex>]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[1precripi1Lmax|<tex>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \le 2 \mid C_{max}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]

1ripipsumwu

2015-06-15T07:07:57Z

Pokrasko: /* Предисловие */

<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>

{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}

== Алгоритм ==

=== Предисловие ===

Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из <tex>n^2</tex> значений.

{{Лемма
|statement=
Существует оптимальное расписание, в котором время начала каждой работы <tex>t_j</tex> принадлежит множеству:
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>

|proof=
Рассмотрим оптимальное расписание <tex>S</tex>. Пусть <tex>j_1, \dots, j_n</tex> — работы в <tex>S</tex> в порядке неубывания дедлайна. Выполнимое расписание может быть получено из <tex>S</tex> следующим образом. Первая работа <tex>j_1</tex> может быть сдвинута влево до времени своего появления. Тогда работа <tex>j_2</tex> сдвигается влево до времени своего появления или времени завершения работы <tex>j_1</tex>. В общем, <tex>j_i</tex> сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы <tex>j_{i - 1}</tex>.
}}

Для любого <tex>k \leqslant n</tex> и <tex>s, e \in T</tex> таких, что <tex>s \leqslant e</tex>, пусть <tex>U_k (s, e)</tex> — множество работ <tex>j \leqslant k</tex> таких, что <tex>s \leqslant r_i \leqslant e</tex>. Кроме того, пусть <tex>W^*_k (s, e)</tex> — максимальный суммарный вес подмножества <tex>U_k (s, e)</tex> такого, что существует выполнимое расписание <tex>S</tex> для работ из этого подмножества такое, что:
* <tex>S</tex> свободно до времени <tex>s + p</tex> и после времени <tex>e</tex>,
* время начала работ в <tex>S</tex> принадлежат <tex>T</tex>.
<tex>W^*_k (s, e) = 0</tex>, если ни для какого подмножества работ не существует выполнимого расписания.

=== Псевдокод ===

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
<tex>W_0 (s, e) \leftarrow 0</tex>
'''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
'''if''' <tex>r_k \not\in [s, e)</tex>
<tex>W_k (s, e) \leftarrow W_{k - 1} (s, e)</tex>
'''else'''
<tex>W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;</tex>
<tex>\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}</tex>
<tex>W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}</tex>
'''return''' <tex>W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)</tex>

Заметим, что <tex>W'_k (s, e)</tex> соответствует выполнимому расписанию, в котором работа <tex>k</tex> начинается в момент времени <tex>s'</tex>.

=== Время работы ===

По лемме <tex>T</tex> содержит <tex>O(n^2)</tex> элементов. В каждой итерации алгоритма мы выбираем времена <tex>s</tex> и <tex>e</tex> из <tex>T</tex>, а для каждой такой пары ищем необходимое время <tex>s'</tex>. Из того, что итераций <tex>n</tex>, получаем, что алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени.

=== Корректность алгоритма ===

Покажем, что вычисленное алгоритмом <tex>W_k (s, e)</tex> равно <tex>W^*_k (s, e)</tex>, то есть возвращаемое им значение является оптимальным решением.

{{Теорема
|statement=
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняется:
<tex>W_k (s, e) = W^*_k (s, e)</tex>

|proof=
Докажем индукцией по <tex>k</tex>. Очевидно, что утверждение выполняется при <tex>k = 0</tex>. Допустим, что оно выполняется при <tex>k - 1</tex>.

Если <tex>r_k \not\in [s, e)</tex>, то <tex>U_k (s, e) = U_{k - 1} (s, e)</tex>, из чего следует, что <tex>W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)</tex>. Осталось показать, что:
<tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)</tex>, если <tex>r_k \in [s, e)</tex>.
Рассмотрим два неравенства:

# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, e)</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
#:* работы <tex>k</tex>, выполняющейся в <tex>[s', s' + p]</tex>,
#:* подмножества работ <tex>U_{k - 1} (s, s')</tex>, выполняющихся в <tex>[s + p, s']</tex>,
#:* подмножества работ <tex>U_{k - 1} (s', e)</tex>, выполняющихся в <tex>[s' + p, e]</tex>.
#:
# <tex>W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}</tex>
#: Пусть <tex>Z</tex> - подмножество <tex>U_k (s, e)</tex>, соответствующее <tex>W^*_k (s, e)</tex>. Если <tex>k \not\in Z</tex>, то <tex>W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)</tex> и неравенство доказано. Иначе, пусть <tex>S^*</tex> - расписание, соответствующее <tex>W^*_k (s, e)</tex>, и <tex>s'</tex> - время начала работы <tex>k</tex>. Нужно, чтобы выполнялось неравенство: <tex>\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>.
#:
#: Обозначим за <tex>Z^b</tex> и <tex>Z^a</tex> подмножества работ <tex>Z</tex>, которые в <tex>S^*</tex> выполняются до и после работы <tex>k</tex> соответственно. Можем предположить, что времена появления всех работ в <tex>Z^a</tex> больше, чем время <tex>s'</tex> начала работы <tex>k</tex>. Иначе, пусть <tex>i</tex> - работа в <tex>Z^a</tex> такая, что <tex>r_i \le s'</tex>. Так как работы отсортированы в порядке неубывания дедлайна, то <tex>d_i \le d_k</tex>. Таким образом, при перестановке работ <tex>i</tex> и <tex>k</tex> в <tex>S^*</tex> суммарный вес не изменится. Продолжим этот процесс, пока новое расписание <tex>S^*</tex> удовлетворяет нужному свойству. Получим:
#: <tex>W^*_k (s, e) = \sum \limits_{j \in Z} w_j = \sum \limits_{j \in Z^b} w_j + w_k + \sum \limits_{j \in Z^a} \leqslant W^*_{k - 1} (s, s') + w_k + W^*_{k - 1} (s', e) = W_{k - 1} (s, s') + w_k + W_{k - 1} (s', e) \leqslant W'_k (s, e)</tex>
#:, так как очевидно, что <tex>Z^b \subseteq U_{k - 1} (s, s')</tex>, и, по предположению, выполняется <tex>Z^a \subseteq U_{k - 1} (s', e)</tex>.
}}

== Прочие задачи ==

Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист, его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.

== См. также ==

* [[P1sumu]]
* [[1pi1sumwu]]

== Источники информации ==

* Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

1ripipsumwu

2015-06-15T07:07:30Z

Pokrasko: /* Предисловие */

<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>

{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}

== Алгоритм ==

=== Предисловие ===

Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из <tex>n^2</tex> значений.

{{Лемма
|statement=
Существует оптимальное расписание, в котором время начала каждой работы t_j принадлежит множеству:
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>

|proof=
Рассмотрим оптимальное расписание <tex>S</tex>. Пусть <tex>j_1, \dots, j_n</tex> — работы в <tex>S</tex> в порядке неубывания дедлайна. Выполнимое расписание может быть получено из <tex>S</tex> следующим образом. Первая работа <tex>j_1</tex> может быть сдвинута влево до времени своего появления. Тогда работа <tex>j_2</tex> сдвигается влево до времени своего появления или времени завершения работы <tex>j_1</tex>. В общем, <tex>j_i</tex> сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы <tex>j_{i - 1}</tex>.
}}

Для любого <tex>k \leqslant n</tex> и <tex>s, e \in T</tex> таких, что <tex>s \leqslant e</tex>, пусть <tex>U_k (s, e)</tex> — множество работ <tex>j \leqslant k</tex> таких, что <tex>s \leqslant r_i \leqslant e</tex>. Кроме того, пусть <tex>W^*_k (s, e)</tex> — максимальный суммарный вес подмножества <tex>U_k (s, e)</tex> такого, что существует выполнимое расписание <tex>S</tex> для работ из этого подмножества такое, что:
* <tex>S</tex> свободно до времени <tex>s + p</tex> и после времени <tex>e</tex>,
* время начала работ в <tex>S</tex> принадлежат <tex>T</tex>.
<tex>W^*_k (s, e) = 0</tex>, если ни для какого подмножества работ не существует выполнимого расписания.

=== Псевдокод ===

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
<tex>W_0 (s, e) \leftarrow 0</tex>
'''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
'''if''' <tex>r_k \not\in [s, e)</tex>
<tex>W_k (s, e) \leftarrow W_{k - 1} (s, e)</tex>
'''else'''
<tex>W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;</tex>
<tex>\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}</tex>
<tex>W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}</tex>
'''return''' <tex>W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)</tex>

Заметим, что <tex>W'_k (s, e)</tex> соответствует выполнимому расписанию, в котором работа <tex>k</tex> начинается в момент времени <tex>s'</tex>.

=== Время работы ===

По лемме <tex>T</tex> содержит <tex>O(n^2)</tex> элементов. В каждой итерации алгоритма мы выбираем времена <tex>s</tex> и <tex>e</tex> из <tex>T</tex>, а для каждой такой пары ищем необходимое время <tex>s'</tex>. Из того, что итераций <tex>n</tex>, получаем, что алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени.

=== Корректность алгоритма ===

Покажем, что вычисленное алгоритмом <tex>W_k (s, e)</tex> равно <tex>W^*_k (s, e)</tex>, то есть возвращаемое им значение является оптимальным решением.

{{Теорема
|statement=
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняется:
<tex>W_k (s, e) = W^*_k (s, e)</tex>

|proof=
Докажем индукцией по <tex>k</tex>. Очевидно, что утверждение выполняется при <tex>k = 0</tex>. Допустим, что оно выполняется при <tex>k - 1</tex>.

Если <tex>r_k \not\in [s, e)</tex>, то <tex>U_k (s, e) = U_{k - 1} (s, e)</tex>, из чего следует, что <tex>W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)</tex>. Осталось показать, что:
<tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)</tex>, если <tex>r_k \in [s, e)</tex>.
Рассмотрим два неравенства:

# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, e)</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
#:* работы <tex>k</tex>, выполняющейся в <tex>[s', s' + p]</tex>,
#:* подмножества работ <tex>U_{k - 1} (s, s')</tex>, выполняющихся в <tex>[s + p, s']</tex>,
#:* подмножества работ <tex>U_{k - 1} (s', e)</tex>, выполняющихся в <tex>[s' + p, e]</tex>.
#:
# <tex>W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}</tex>
#: Пусть <tex>Z</tex> - подмножество <tex>U_k (s, e)</tex>, соответствующее <tex>W^*_k (s, e)</tex>. Если <tex>k \not\in Z</tex>, то <tex>W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)</tex> и неравенство доказано. Иначе, пусть <tex>S^*</tex> - расписание, соответствующее <tex>W^*_k (s, e)</tex>, и <tex>s'</tex> - время начала работы <tex>k</tex>. Нужно, чтобы выполнялось неравенство: <tex>\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>.
#:
#: Обозначим за <tex>Z^b</tex> и <tex>Z^a</tex> подмножества работ <tex>Z</tex>, которые в <tex>S^*</tex> выполняются до и после работы <tex>k</tex> соответственно. Можем предположить, что времена появления всех работ в <tex>Z^a</tex> больше, чем время <tex>s'</tex> начала работы <tex>k</tex>. Иначе, пусть <tex>i</tex> - работа в <tex>Z^a</tex> такая, что <tex>r_i \le s'</tex>. Так как работы отсортированы в порядке неубывания дедлайна, то <tex>d_i \le d_k</tex>. Таким образом, при перестановке работ <tex>i</tex> и <tex>k</tex> в <tex>S^*</tex> суммарный вес не изменится. Продолжим этот процесс, пока новое расписание <tex>S^*</tex> удовлетворяет нужному свойству. Получим:
#: <tex>W^*_k (s, e) = \sum \limits_{j \in Z} w_j = \sum \limits_{j \in Z^b} w_j + w_k + \sum \limits_{j \in Z^a} \leqslant W^*_{k - 1} (s, s') + w_k + W^*_{k - 1} (s', e) = W_{k - 1} (s, s') + w_k + W_{k - 1} (s', e) \leqslant W'_k (s, e)</tex>
#:, так как очевидно, что <tex>Z^b \subseteq U_{k - 1} (s, s')</tex>, и, по предположению, выполняется <tex>Z^a \subseteq U_{k - 1} (s', e)</tex>.
}}

== Прочие задачи ==

Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист, его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.

== См. также ==

* [[P1sumu]]
* [[1pi1sumwu]]

== Источники информации ==

* Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

1ripipsumwu

2015-06-14T09:38:27Z

Pokrasko: /* Корректность алгоритма */

<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>

{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}

== Алгоритм ==

=== Предисловие ===

Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из <tex>n^2</tex> значений.

{{Лемма
|statement=
Существует оптимальное расписание, в котором время начала каждой работы принадлежит множеству:
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>

|proof=
Рассмотрим оптимальное расписание <tex>S</tex>. Пусть <tex>j_1, \dots, j_n</tex> — работы в <tex>S</tex> в порядке неубывания дедлайна. Выполнимое расписание может быть получено из <tex>S</tex> следующим образом. Первая работа <tex>j_1</tex> может быть сдвинута влево до времени своего появления. Тогда работа <tex>j_2</tex> сдвигается влево до времени своего появления или времени завершения работы <tex>j_1</tex>. В общем, <tex>j_i</tex> сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы <tex>j_{i - 1}</tex>.
}}

Для любого <tex>k \leqslant n</tex> и <tex>s, e \in T</tex> таких, что <tex>s \leqslant e</tex>, пусть <tex>U_k (s, e)</tex> — множество работ <tex>j \leqslant k</tex> таких, что <tex>s \leqslant r_i \leqslant e</tex>. Кроме того, пусть <tex>W^*_k (s, e)</tex> — максимальный суммарный вес подмножества <tex>U_k (s, e)</tex> такого, что существует выполнимое расписание <tex>S</tex> для работ из этого подмножества такое, что:
* <tex>S</tex> свободно до времени <tex>s + p</tex> и после времени <tex>e</tex>,
* время начала работ в <tex>S</tex> принадлежат <tex>T</tex>.
<tex>W^*_k (s, e) = 0</tex>, если ни для какого подмножества работ не существует выполнимого расписания.

=== Псевдокод ===

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
<tex>W_0 (s, e) \leftarrow 0</tex>
'''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
'''if''' <tex>r_k \not\in [s, e)</tex>
<tex>W_k (s, e) \leftarrow W_{k - 1} (s, e)</tex>
'''else'''
<tex>W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;</tex>
<tex>\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}</tex>
<tex>W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}</tex>
'''return''' <tex>W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)</tex>

Заметим, что <tex>W'_k (s, e)</tex> соответствует выполнимому расписанию, в котором работа <tex>k</tex> начинается в момент времени <tex>s'</tex>.

=== Время работы ===

По лемме <tex>T</tex> содержит <tex>O(n^2)</tex> элементов. В каждой итерации алгоритма мы выбираем времена <tex>s</tex> и <tex>e</tex> из <tex>T</tex>, а для каждой такой пары ищем необходимое время <tex>s'</tex>. Из того, что итераций <tex>n</tex>, получаем, что алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени.

=== Корректность алгоритма ===

Покажем, что вычисленное алгоритмом <tex>W_k (s, e)</tex> равно <tex>W^*_k (s, e)</tex>, то есть возвращаемое им значение является оптимальным решением.

{{Теорема
|statement=
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняется:
<tex>W_k (s, e) = W^*_k (s, e)</tex>

|proof=
Докажем индукцией по <tex>k</tex>. Очевидно, что утверждение выполняется при <tex>k = 0</tex>. Допустим, что оно выполняется при <tex>k - 1</tex>.

Если <tex>r_k \not\in [s, e)</tex>, то <tex>U_k (s, e) = U_{k - 1} (s, e)</tex>, из чего следует, что <tex>W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)</tex>. Осталось показать, что:
<tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)</tex>, если <tex>r_k \in [s, e)</tex>.
Рассмотрим два неравенства:

# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, e)</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
#:* работы <tex>k</tex>, выполняющейся в <tex>[s', s' + p]</tex>,
#:* подмножества работ <tex>U_{k - 1} (s, s')</tex>, выполняющихся в <tex>[s + p, s']</tex>,
#:* подмножества работ <tex>U_{k - 1} (s', e)</tex>, выполняющихся в <tex>[s' + p, e]</tex>.
#:
# <tex>W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}</tex>
#: Пусть <tex>Z</tex> - подмножество <tex>U_k (s, e)</tex>, соответствующее <tex>W^*_k (s, e)</tex>. Если <tex>k \not\in Z</tex>, то <tex>W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)</tex> и неравенство доказано. Иначе, пусть <tex>S^*</tex> - расписание, соответствующее <tex>W^*_k (s, e)</tex>, и <tex>s'</tex> - время начала работы <tex>k</tex>. Нужно, чтобы выполнялось неравенство: <tex>\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>.
#:
#: Обозначим за <tex>Z^b</tex> и <tex>Z^a</tex> подмножества работ <tex>Z</tex>, которые в <tex>S^*</tex> выполняются до и после работы <tex>k</tex> соответственно. Можем предположить, что времена появления всех работ в <tex>Z^a</tex> больше, чем время <tex>s'</tex> начала работы <tex>k</tex>. Иначе, пусть <tex>i</tex> - работа в <tex>Z^a</tex> такая, что <tex>r_i \le s'</tex>. Так как работы отсортированы в порядке неубывания дедлайна, то <tex>d_i \le d_k</tex>. Таким образом, при перестановке работ <tex>i</tex> и <tex>k</tex> в <tex>S^*</tex> суммарный вес не изменится. Продолжим этот процесс, пока новое расписание <tex>S^*</tex> удовлетворяет нужному свойству. Получим:
#: <tex>W^*_k (s, e) = \sum \limits_{j \in Z} w_j = \sum \limits_{j \in Z^b} w_j + w_k + \sum \limits_{j \in Z^a} \leqslant W^*_{k - 1} (s, s') + w_k + W^*_{k - 1} (s', e) = W_{k - 1} (s, s') + w_k + W_{k - 1} (s', e) \leqslant W'_k (s, e)</tex>
#:, так как очевидно, что <tex>Z^b \subseteq U_{k - 1} (s, s')</tex>, и, по предположению, выполняется <tex>Z^a \subseteq U_{k - 1} (s', e)</tex>.
}}

== Прочие задачи ==

Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист, его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.

== См. также ==

* [[P1sumu]]
* [[1pi1sumwu]]

== Источники информации ==

* Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

1ripipsumwu

2015-06-13T21:47:22Z

Pokrasko:

<tex dpi=200> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>

{{Задача
|definition=
Дано <tex>n</tex> работ и 1 станок. Для каждой работы известны её время появления <tex>r_i</tex> и вес <tex>w_i</tex>, а также дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>p</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_i U_i</tex> (суммарный вес просроченных работ) было минимальным.
}}

== Алгоритм ==

=== Предисловие ===

Необходимо найти выполнимое множество работ <tex>X</tex> такое, что его суммарный вес <tex>\sum \limits_{i \in X} w_i</tex> максимален. Эта проблема решается с помощью [[Динамическое программирование | динамического программирования]].
Предполагается, что работы отсортированы в порядке неубывания дедлайна. Следующая лемма показывает, что времена начала всех работ могут быть ограничены до множества, состоящего не более, чем из <tex>n^2</tex> значений.

{{Лемма
|statement=
Существует оптимальное расписание, в котором время начала каждой работы принадлежит множеству:
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>

|proof=
Рассмотрим оптимальное расписание <tex>S</tex>. Пусть <tex>j_1, \dots, j_n</tex> — работы в <tex>S</tex> в порядке неубывания дедлайна. Выполнимое расписание может быть получено из <tex>S</tex> следующим образом. Первая работа <tex>j_1</tex> может быть сдвинута влево до времени своего появления. Тогда работа <tex>j_2</tex> сдвигается влево до времени своего появления или времени завершения работы <tex>j_1</tex>. В общем, <tex>j_i</tex> сдвигается влево, пока время её начала не равно максимуму из времени её появления и времени завершения уже сдвинутой работы <tex>j_{i - 1}</tex>.
}}

Для любого <tex>k \leqslant n</tex> и <tex>s, e \in T</tex> таких, что <tex>s \leqslant e</tex>, пусть <tex>U_k (s, e)</tex> — множество работ <tex>j \leqslant k</tex> таких, что <tex>s \leqslant r_i \leqslant e</tex>. Кроме того, пусть <tex>W^*_k (s, e)</tex> — максимальный суммарный вес подмножества <tex>U_k (s, e)</tex> такого, что существует выполнимое расписание <tex>S</tex> для работ из этого подмножества такое, что:
* <tex>S</tex> свободно до времени <tex>s + p</tex> и после времени <tex>e</tex>,
* время начала работ в <tex>S</tex> принадлежат <tex>T</tex>.
<tex>W^*_k (s, e) = 0</tex>, если ни для какого подмножества работ не существует выполнимого расписания.

=== Псевдокод ===

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
<tex>W_0 (s, e) \leftarrow 0</tex>
'''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>s, e \in T \mid s \leqslant e</tex>
'''if''' <tex>r_k \not\in [s, e)</tex>
<tex>W_k (s, e) \leftarrow W_{k - 1} (s, e)</tex>
'''else'''
<tex>W'_k (s, e) \leftarrow \max\{w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) \mid s' \in T;</tex>
<tex>\max\{r_k, s + p\} \leqslant s' \leqslant \min\{d_k, e\} - p\}</tex>
<tex>W_k (s, e) \leftarrow \max\{W_{k - 1} (s, e), W'_k(s, e)\}</tex>
'''return''' <tex>W_n(\min\limits_{t \in T} t - p, \max\limits_{t \in T} t)</tex>

Заметим, что <tex>W'_k (s, e)</tex> соответствует выполнимому расписанию, в котором работа <tex>k</tex> начинается в момент времени <tex>s'</tex>.

=== Время работы ===

По лемме <tex>T</tex> содержит <tex>O(n^2)</tex> элементов. В каждой итерации алгоритма мы выбираем времена <tex>s</tex> и <tex>e</tex> из <tex>T</tex>, а для каждой такой пары ищем необходимое время <tex>s'</tex>. Из того, что итераций <tex>n</tex>, получаем, что алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени.

=== Корректность алгоритма ===

Покажем, что вычисленное алгоритмом <tex>W_k (s, e)</tex> равно <tex>W^*_k (s, e)</tex>, то есть возвращаемое им значение является оптимальным решением.

{{Теорема
|statement=
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняется:
<tex>W_k (s, e) = W^*_k (s, e)</tex>

|proof=
Докажем индукцией по <tex>k</tex>. Очевидно, что утверждение выполняется при <tex>k = 0</tex>. Допустим, что оно выполняется при <tex>k - 1</tex>.

Если <tex>r_k \not\in [s, e)</tex>, то <tex>U_k (s, e) = U_{k - 1} (s, e)</tex>, из чего следует, что <tex>W_k (s, e) = W_{k - 1} (s, e) = W^*_{k - 1} (s, e) = W^*_k (s, e)</tex>. Осталось показать, что:
<tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} = W^*_k (s, e)</tex>, если <tex>r_k \in [s, e)</tex>.
Рассмотрим два неравенства:

# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, s')</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
#:* работы <tex>k</tex>, выполняющейся в <tex>[s', s' + p]</tex>,
#:* подмножества работ <tex>U_{k - 1} (s, s')</tex>, выполняющихся в <tex>[s + p, s']</tex>,
#:* подмножества работ <tex>U_{k - 1} (s', e)</tex>, выполняющихся в <tex>[s' + p, e]</tex>.
#:
# <tex>W^*_k (s, e) \leqslant \max \{W_{k - 1} (s, e), W'_k (s, e)\}</tex>
#: Пусть <tex>Z</tex> - подмножество <tex>U_k (s, e)</tex>, соответствующее <tex>W^*_k (s, e)</tex>. Если <tex>k \not\in Z</tex>, то <tex>W^*_k (s, e) = W^*_{k - 1} (s, e) = W_{k - 1} (s, e)</tex> и неравенство доказано. Иначе, пусть <tex>S^*</tex> - расписание, соответствующее <tex>W^*_k (s, e)</tex>, и <tex>s'</tex> - время начала работы <tex>k</tex>. Нужно, чтобы выполнялось неравенство: <tex>\max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>.
#:
#: Обозначим за <tex>Z^b</tex> и <tex>Z^a</tex> подмножества работ <tex>Z</tex>, которые в <tex>S^*</tex> выполняются до и после работы <tex>k</tex> соответственно. Можем предположить, что времена появления всех работ в <tex>Z^a</tex> больше, чем время <tex>s'</tex> начала работы <tex>k</tex>. Иначе, пусть <tex>i</tex> - работа в <tex>Z^a</tex> такая, что <tex>r_i \le s'</tex>. Так как работы отсортированы в порядке неубывания дедлайна, то <tex>d_i \le d_k</tex>. Таким образом, при перестановке работ <tex>i</tex> и <tex>k</tex> в <tex>S^*</tex> суммарный вес не изменится. Продолжим этот процесс, пока новое расписание <tex>S^*</tex> удовлетворяет нужному свойству. Получим:
#: <tex>W^*_k (s, e) = \sum \limits_{j \in Z} w_j = \sum \limits_{j \in Z^b} w_j + w_k + \sum \limits_{j \in Z^a} \leqslant W^*_{k - 1} (s, s') + w_k + W^*_{k - 1} (s', e) = W_{k - 1} (s, s') + w_k + W_{k - 1} (s', e) \leqslant W'_k (s, e)</tex>
#:, так как очевидно, что <tex>Z^b \subseteq U_{k - 1} (s, s')</tex>, и, по предположению, выполняется <tex>Z^a \subseteq U_{k - 1} (s', e)</tex>.
}}

== Прочие задачи ==

Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист, его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.

== См. также ==

* [[P1sumu]]
* [[1pi1sumwu]]

== Источники информации ==

* Peter Brucker — Scheduling Algorithms — Springer, 2007 — p. 98-101 — ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

1ripipsumwu

2015-06-13T21:39:47Z

Pokrasko: переименовал 1ripipsumwu в 1ridipipsumwu: Точнее отражает условия алгоритма.

#перенаправление [[1ridipipsumwu]]