Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 99
Текст из файла (страница 99)
Пример задачи по планированию единичных заданий с конечным сроце| выполнения н штрафом на одном процессоре 3 4 5 6 7 1 2 3 1 4 6 40 30 20 10 4 70 2 60 4 50 Упражнения 16.5-1. Решите задачу планирования„параметры которой приведены в табл. 16.2, но каждый штраф иЧ в которой заменен величиной 80 — иь 16.5-2. Покажите, как с помощью второго свойства леммы 16.12 в течение времени О (!А~) определить, независимо ли заданное множество заданий А. Задачи 16-1. Размен монет Рассмотрим задачу по выдаче сдачи, сумма которой составляет и копеек, использовав как можно меньшее количество монет. Предполагается, что номинал каждой монеты выражается целым числом. а) Опишите жадный алгоритм, в котором сдача выдается монетами номиналом 25 копеек, 10 копеек, 5 копеек и 1 копейка. Докажите, что алгоритм позволяет получить оптимальное решение. б) Предположим, что номинал монет выражается степенями некоторого целого числа с > 1, т.е.
номиналы представляют собой числа со, сз,..., с", где й > 1. Покажите, что жадный алгоритм всегда дает оптимальное решение. в) Приведите пример множества номиналов монет, для которого жадный алгоритм не выдает оптимального решения. В зто множество должна входить монета номиналом 1 копейка, чтобы решение существовало для любого значения и. г) Разработайте алгоритм, позволяющий выдать сдачу с помощью любого набора монет, множество номиналов в котором состоит из 1| писание (аз, а4, ад, аз, ат, аз, ав), которому соответствует общая сумма штрафа, равная иъз+ шв = 50. Глава 16. Жадные алгоритмы различных номиналов. Предполагается, что один из номиналов обязательно равен 1 копейке.
Время работы алгоритма должно быть равно О (тй). 16-2. Расписание, минимизирующее среднее время выполнения Предположим, у нас имеется множество заданий Я = (ам аз,...,а„), в котором для выполнения задания сн требуется р; единиц времени. Имеется один компьютер, на котором будут выполняться эти задания, который способен одновременно выполнять не более одного задания.
Пусть с; — время завершения задания а;, т.е. момент времени, когда прекрашается его выполнение. Задача заключается в том, чтобы минимизировать среднее время завершения, т.е. величину 2 ", С(п. Например, предположим, что имеется два задания а~ и аз, которым соответствуют времена выполнения Рз — — 3 и рз = 5. Рассмотрим расписание, в котором сначала выполняется задание аз, а затем — задание ап Тогда сэ = 5, с~ = 8, и среднее время завершения равно 15+ 8)/2 = 6.5.
а) Сформулируйте алгоритм, который планирует задания таким образом, чтобы минимизировать среднее время завершения. Каждое задание должно выполняться без прерываний, т.е. будучи запущено, задание сч должно непрерывно выполняться в течение р; единиц времени. Докажите, что ваш алгоритм минимизирует среднее время завершения, и определите время его работы. б) Предположим, что не все задания доступны сразу. Другими словами, с каждым заданием связано время выпуска (ге!сазе 1ппе) го раньше которого оно недоступно для обработки.
Предположим также, что допускаются лрерыааиия, т.е. что задание может быть приостановлено и возобновлено позже. Например, задание а;, время обработки которого равно р; = 6, может быть запущено в момент времени ! и приостановлено в момент времени 4. Затем оно может быть возобновлено в момент времени 10, еше раз приостановлено в момент времени 11, снова возобновлено в момент времени 13, и наконец завершено в момент времени 15. Таким образом, задание а, в обшей сложности выполняется в течение шести единиц времени, но время его выполнения разделено на три фрагмента. Время завершения задания а; равно при таком расписании 15. Сформулируйте алгоритм, планирующий задания таким образом, чтобы минимизировать среднее время завершения в этом новом сценарии.
Докажите, что ваш алгоритм минимизирует среднее время завершения и найдите время его работы. 480 Часть 1Ч. Усовершенствованные методы разработки и анализа 16-3. Ациклические подграфы а) Пусть С = (К Е) — неориентированный граф. Покажите с помощью определения матроида, что (Е, 2) — матроид, где А е 2 тогда и только тогда, когда А — ациклическое подмножество Е. б) Для неориентированного графа С = (К Е) матрицей инциденвности (щсЫепсе таптх) называется матрица М размером )Ц х )Е), такая что М„, = 1, если ребро е инцидентно вершине о, и М„, = 0 в противном случае. Докажите, что множество столбцов матрицы М линейно независимо над полем целых чисел по модулю 2 тогда и только тогда, когда соответствующее множество ребер ациклично. Затем с помощью результата упражнения 16.4-2 приведите альтернативное доказательство того, что структура (Е, Т~ из части а задачи— матроид.
в) Предположим, с каждым ребром неориентированного графа С = = (1~, Е) связан неотрицательный вес ю(е). Разработайте эффективный алгоритм поиска ациклического подмножества множества Е с максимальным общим весом. г) Пусть С = (К Е) — произвольный ориентированный граф, и пусть (Е, Х) определено так, что А е Х тогда и только тогда, когда А не содержит ориентированных циклов. Приведите пример ориентированного графа С, такого что связанная с ним система (Е, Х) не является матроидом. Укажите, какое условие из определения матроила не соблюдается. д) Для ориентированного графа С = ($', Е) матрицей инцидентносгни (1псЫепсе та1пх) называется матрица М размером (Ц х (Е(, такая что М„, = -1, если ребро е исходит из вершины о, М„, = +1, если ребро е входит в вершину о, и М, = 0 в противном случае.
Докажите, что если множество столбцов матрицы М линейно независимо, то соответствующее множество ребер не содержит ориентированных циклов. е) В упражнении 16.4-2 утверждается, что семейство линейно независимых столбцов произвольной матрицы М образует матрона. Объясните, почему результаты частей г) и д) задачи не противоречат друг другу. В чем могут быть различия между понятием ациклического множества ребер и понятием множества связанных с ними линейно независимых столбцов матрицы инцидентности? 16-4. Вариации задачи планирования Рассмотрим сформулированный ниже алгоритм применительно к задаче из раздела 16.5, в которой предлагается составить расписание единичных Глава 18. Жадные алгоритмы 481 задач с конечными сроками выполнения и штрафами. Пусть все тт отрезков времени изначально являются пустыми, где 1-й интервал времени— это единичный промежуток времени„который заканчивается в момент 1. Задачи рассматриваются в порядке монотонного убывания штрафов.
Если при рассмотрении задания а существуют незаполненные отрезки времени, расположенные на шкале времени не позже конечного момента выполнения ф этого задания, то задание а. планируется для выполнения в течение последнего из этих отрезков, заполняя данный отрезок. Если же ни одного такого отрезка времени не осталось, задание а планируется для выполнения в течение последнего из незаполненных отрезков. а) Докажите, что этот алгоритм всегда позволяет получить оптимальный ответ. б) Реализуйте эффективный алгоритм с помощью леса непересекающихся множеств, описанного в разделе 21.3.
Предполагается, что множество входных заданий уже отсортировано в порядке монотонного убывания штрафов. Проанализируйте время работы алгоритма в вашей реализации. Заключительные замечания Намного большее количество материала по жадным алгоритмам и матроидам можно найти в книгах Лоулера (1.атг!ег) [196], а также Пападимитриу (Рарад(шЬпои) и Штейглица (Бте(811гх) [237].
Впервые жадный алгоритм был описан в литературе по комбинаторной оптимизации в статье Эдмондов (Ебшопдз) [85], опубликованной в 1971 году. Появление же теории матроидов датируется 1935 годом, когда вышла статья Уитни (%Ь(тнеу) [314]. Приведенное здесь доказательство корректности жадного алгоритма для решения задачи о выборе процессов основано на доказательстве, предложенном Гаврилом (бачп1) [112]. Задача о планировании заданий изучалась Лоулером [196], Горовицем (Ногочлтг) и Сахни (ЯаЬгн) [157], а также Брассардом (Вгаззап1) и Брейтли (Вга11еу) [47]. Коды Хаффмана были разработаны в 1952 году [162].
В работе Лелевера (1.е!евег) и Хиршберга (НпзсЬЬег8) [200] имеется обзор методов сжатия данных, известных к 1987 году. Развитие теории матроидов до теории гридоидов (8геедоЫ) впервые было предложено Кортом (Когте) и Ловасом (1.очазг) [189-192], которые значительно обобщили представленную здесь теорию. ГЛАВА 17 Амортизационный анализ При амортизационном анализе (ашоп(гед апа!уз(з) время, требуемое для выполнения последовательности операций над структурой данных, усредняется по всем выполняемым операциям. Этот анализ можно использовать, например, чтобы показать, что даже если одна из операций последовательности является дорогостоящей, то при усреднении по всей последовательности средняя стоимость операций будет небольшой.
Амортизационный анализ отличается от анализа средних величин тем, что в нем не учитывается вероятность. При амортизационном анализе гарантируется средняя производительность операций в наихудшем случае. В первых трех разделах этой главы описываются три наиболее распространенных метода, используемые при амортизационном анализе. Начало раздела 17.1 посвящено групповому анализу, в ходе которого определяется верхняя граница Т(п) полной стоимости последовательности и операций. Тогда средняя стоимость операции вычисляется как Т(п)/и. Мы принимаем среднюю стоимость равной амортизированной стоимости каждой операции, так что амортизированная стоимость всех операций одинакова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
