Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 105

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 105)

Заметим, что Хо(А) = О для любого множества А. Лемма 16.12 Для любого множества заданий А сформулированные ниже утверждения эквива- лентны. 1. Множество А независимое. 2. Неравенство Юс (А) < 1 справедливо для всех г = О, 1, 2,..., и. 3. Если в расписании задания из множества А расположены в порядке неубывания конечных сроков выполнения, то ни одно из них не является просроченным. Доказательство. Чтобы показать, что нз (1) следует (2), докажем обращенное утверждение: если Хс(А) ) 1 для некоторого 1, то невозможно составить расписание таким образом, чтобы в множестве А не оказалось просроченных заданий, поскольку до наступления момента с остается более с незавершенных заданий. Таким образом, утверждение (1) предполагает выполнение утверждения (2).

Если выполняется утверждение (2), то г-й по порядку срок завершения задания не превышает з, так что при расстановке заданий в этом порядке все сроки будут соблюдены. Наконец из утверждения (3) тривиальным образом следует справедливость утверждения (1). С помощью свойства 2 леммы 16.12 легко определить, является ли независимым заданное множество заданий (см. упр. 16.5.2). Задача минимизации суммы штрафов за просроченные задания — это то же самое, что задача по максимизации суммы штрафов, которых удалось избежать бла- 4В1 Глава 1й Жадные алгоритмы годара своевременному выполнению заданий. Таким образом, приведенная ниже теорема гарантирует, что с помощью жадного алгоритма можно найти независимое множество заданий А с максимальной суммой штрафов. Теорема 1б.13 Если 5 — множество единичных заданий с конечным сроком выполнения, а Х— семейство всех независимых множеств заданий, то соответствующая система (5, 1) является матроидом.

Доказателастоо. Каждое подмножество независимого множества заданий также независимо. Чтобы доказать, что выполняется свойство обмена, предположим, что В н А — независимые множества заданий, и что )В) ) (А~. Пусть и — наибольшее 1, такое, что Хт(В) < 1ч;(А) (такое значение 1 существует, поскольку Уо(А) = Ио(В) = О). Поскольку №(В) = /В/ и №(А) = /А/, но )В! ) (А), получается, что и < п, и для всех з в диапазоне Й + 1 < з < и должно выполняться соотношение 1ч' (В) > Гч',(А). Следовательно, в множестве В содержится больше заданий с конечным сроком выполнения 1с+ 1, чем в множестве А. Пусть а; — задание из множества  — А с конечным сроком выполнения 1с + 1 и пусть А'= А1л(а,).

Теперь с помощью второго свойства леммы 16.12 покажем, что множество А' должно быть независимым. Поскольку множество А независимое, для любого 0 < 1 < lс выполняется соотношение Хе(А') = гт'т(А) < 1. Для 1с < 1 < и, посюльку  — независимое множество, имеем Хт(А') < Ле(В) < 1. Следовательно, множество А' независимое, что и завершает доказательство того, что (Я, Т)— мвтроид. Согласно теореме 16.11 для поиска независимого множества заданий А с максимальным весом можно использовать жадный алгоритм. После этого можно будет создать оптимальное расписание, в ютором элементы множества А будут играть роль своевременных заданий.

Этот метод дает эффективный алгоритм планирования единичных заданий с конечным сроюм выполнения и штрафом для одного процессора. Время работы этого алгоритма, в котором используется процедура 1лкбепу, равно 0(п~), поскольку каждая из 0(п) проверок независимости, выполняющихся в этом алгоритме, требует времени 0(п) (см. упр. 16.5.2). Более быструю реализацию этого алгоритма предлагается разработать в задаче 16А. На рис. 16.7 приведен пример задачи по планированию единичных заданий с конечным сроком выполнения и штрафом для одного процессора. В этом при- Задание Рис. ПК7.

Пример задачи по планированию единичных заданий с конечным сроком выполнения и штрафом на одном процессоре. ~в звх зтгв 4Вг Часть!и усовертенствованные методы разработки и аназиза мере жадный алгоритм поочередно выбирает задания ам аз, аз и а4, затем отвеРгает заданил оа (посколькУ зи4((аз,аз,аз,а4,аь1) = 5) и ае (посколькУ Ж4((аз,аз,аз,а4, ае)) = 5) и наконец выбирает задание аз. В результате получается оптимальное расписание (пз п4, п11аз пз, пб, оа) котоРомУ соответствУет общаЯ сУмма штРафа, РавнаЯ вз + зсб = 50.

Упражяеиия 16.5.1 Решите задачу планирования, параметры которой приведены на рис. 16.7, но каждый штраф ид в которой заменен величиной 80 — а ь 16.5.2 Покажите, как с помощью второго свойства леммы 16.12 в течение времени 0(~А~) определить, независимо ли заданное множество заданий А. Задачи 16.1. Размен монезн Рассмотрим задачу по выдаче сдачи, сумма которой составляет п копеек, использовав как можно меньше монет. Предполагается, что номинал каждой монеты выражается целым числом. зь Опишите жадный алгоритм, в котором сдача выдастся монетами номиналом 25 копеек, 1О копеек, 5 копеек и 1 копейка.

Докажите, что алгоритм позволяет получить оптимальное решение. 6. Предположим, что номинал монет выражается степенями некоторого целого числа с > 1, т.е. номиналы представляют собой числа со, с,..., ск, где Й > 1. Покажите, что жадный алгоритм всегда дает оптимальное решение. в. Приведите пример множества номиналов монет, для которого жадный алгоритм не выдает оптимального решения. В зто множество должна входить монета номиналом 1 копейка, чтобы решение существовало для любого значения п.

* Разработайте алгоритм, позволяющий вьщать сдачу с помощью любого набора монет, множество номиналов в котором состоит из зс различных номиналов. Предполагается, что один из номиналов обязательно равен 1 копейке. Время работы алгоритма должно быть равно 0(п)с). Глава !д Жадные алгоритмы 483 ла2. Рвснисвние, минимизируюибее среднее время выналнения Предположим, имеется множество заданий Я = (аыаз,...,а„), в котором для выполнения задания а; требуется рг единиц времени. Имеется один компьютер, на котором будут выполняться эти задания и который способен одновременно выполнять не более одного задания.

Пусть с, — время зввертения задания а,, т.е. момент времени, когда прекращается его выполнение. Задача заключается в том, чтобы минимизировать среднее время завершения, т.е. величину (1/и) 2'," г с;. Например, предположим, что имеется два задания, аг и аз, которым соответствуют два значения времени выполнения: рг = 3 и рз = 5.

Рассмотрим расписание, в котором сначала выполняется задание аз, а затем — задание аг. Тогда сз = 5, сг = 8 и среднее время завершения равно (5+ 8)/2 = 6.5. Если же первым выполняется задание аы то сг = 3, сз = 8, а среднее время завершения равно (3 + 8)/2 = 5.5. а Сформулируйте алгоритм, который планирует задания таким образом, чтобы минимизировать среднее время завершения.

Каждое задание должно выполняться без прерываний, т.е., будучи запушенным, задание а, должно непрерывно выполняться в течение р, единиц времени. Докажите, что ваш алгоритм минимизирует среднее время завершения, и определите время его работы. 6. Предположим, что не все задания доступны сразу. Другими словами, с квкдым заданием связано время выпуски (ге!еазе гппе) г,, раньше которого оно недоступно для обработки. Предположим также, что допускаются нрерыввння, т.е. что задание может быть приостановлено и возобновлено позже. Например, задание ао время обработки которого равно р, = 6, может быть запущено в момент времени 1 и приостановлено в момент времени 4.

Затем оно может быть возобновлено в момент времени 10, еще раз приостановлено в момент времени 11, снова возобновлено в момент времени 13 и наконец завершено в момент времени 15. Таким образом, задание а; в общей сложности выполняется в течение шести единиц времени, но время его выполнения разделено на три фрагмента. Время завершения задания а; равно при таком расписании 15. Сформулируйте алгоритм, планирующий задания таким образом, чтобы минимизировать среднее время завершения в этом новом сценарии. Докажите, что ваш алгоритм минимизирует среднее время завершения, и найдите время его работы.

1аЗ. Ациклические иодграфы а Для неориентированного графа С = (1г,Е) метрицей инцидентнвсти (шсЫепсе шап(х) называется матрица М размером ))Г! х (Е), такая, что Мае = 1, если ребро е инцидентно вершине е, и Мае = 0 в противном случае. Докажите, что множество столбцов матрицы М линейно независимо над полем целых чисел по модулю 2 тогда и только тогда, когда соответствующее множество ребер ациклично. 484 Часть гц усовершенствованные методы разработки и анализа б. Предположим, что с каждым ребром неориентированного графа С = (у; Е) связан неотрицательный вес зо(е). Разработайте эффективный алгоритм поиска ациклического подмножества множества Е с максимальным общим весом.

в. Пусть С = ($л, Е) — произвольный ориентированный граф и пусть (Е,Х) определено так, что А Е Х тогда и только тогда, когда А не содержит ориентированных циклов. Приведите пример ориентированного графа С, таиэго, что связанная с ним система (Е,1) не является матроидом. Укажите, какое условие из определения матроида не соблюдается. и Для ориентированного графа С = ( н; Е) матрицей инцидентности ((псЫепсе шацтх) называется матрица М размером ~Ъ'! х (Е), такая, что Мв, = — 1, если ребро е исходит из вершины о, Мсв = +1, если ребро е входит в вершину о, иначе Мов = О. Докажите, что если множество столбцов матрицы М линейно независимо, то соответствующее множество ребер не содержит ориентированных циклов.

Характеристики

Список файлов книги