Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 106
Текст из файла (страница 106)
д. В упр. !64.2 утверждается, что множество линейно независимых множеств произвольной матрицы М образует матроид. Обьясните, почему результаты пп, (в) и (д) задачи не противоречат одно другому. В чем могут быть различия между понятием ациклического множества ребер и понятием множества связанных с ними линейно независимых столбцов матрицы инцидентности? 1б.4. Вариации задачи планирования Рассмотрим следующий алгоритм для решения задачи из раздела 16.5, в которой предлагается составить расписание единичных задач с конечными сроками выполнения и штрафами.
Пусть все и отрезков времени изначально являются пустыми, где з-й интервал времени — это единичный промежуток времени, который заканчивается в момент з. Задачи рассматриваются в порядке монотонного убывания штрафов. Если при рассмотрении задания а существуют незаполненные отрезки времени, расположенные на шкале времени не позже конечного момента выполнения б этого задания, то задание а планируется для выполнения в течение последнего из этих отрезков, заполняя данный отрезок. Если же ни одного такого отрезка времени ие осталось, задание а планируется для выполнения в течение последнего из незаполненных отрезков.
ж Докажите, что этот алгоритм всегда дает оптимальный ответ. б. Эффективно реализуйте этот алгоритм с помощью леса непересекающихся множеств, описанного в разделе 21.3. Предполагается, что множество входных заданий уже отсортировано в порядке монотонного убывания штрафов. Проанализируйте время работы алгоритма в вашей реализации.
16.5. Кетирование Современные компьютеры используют кеш для хранения в быстрой памяти данных небольших размеров. Несмотря на то что программа может работать Глава!К Жадные алгоритмы с большим количеством данных, хранение небольшого подмножества основной памяти в капле — маленькой, но быстрой памяти — может существенно снизить общее время обращения к данным. При работе компьютерной программы она выполняет последовательность (гы гз,..., т„) из и обращений к памяти, где каждое обращение запрашивает неюторый конкретный элемент данных. Например, программа, обращающаяся к четырем различным элементам (а, Ь, с, д) может выполнять последовательность запросов (д, Ь, Н, Ь, д, а, с, й, Ь, а, с, Ь).
Обозначим размер кеша как Ь. Когда кеш содержит Ь элементов и программа обрашается к (/с + 1)-му элементу, система должна решить (для данного и каждого из последующих запросов), какие й элементов должны храниться в кеше. Точнее говоря, лля каждого запроса г, алгоритм управления кешированием проверяет, находится лн элемент г; в кеше. Если да, то мы сталкиваемся с попаданием (сасйе )з(!); в противном случае мы имеем арамах (сасйе ппзз). При промахе система запрашивает г; из основной памяти, и алгоритм управления кешированнем должен решить, следует ли хранить г; в кеше. Если он принимает решение о хранении го а кеш уже хранит /с элементов, то из кеша следует убрать один элемент, чтобы освободить память для гь Алгоритм управления кешированием убирает данные нз кеша таким образом, чтобы минимизировать количество промахов во всей последовательности запросов.
Обычно кеширование представляет собой оперативную (оп-йпе) задачу, когда мы должны принимать решения о том, какие данные должны храниться в кеше, ничего не зная о будущих запросах. В данной же задаче мы рассматриваем автономную (оффлайн, о(Т-!(пе) версию этой задачи, в которой нам заранее известна вся последовательность лз запросов и размер кеша Й, и хотим минимизировать обшее количество промахов кеша. Эту задачу можно решить с применением жадной стратегии, которая выбирает для удаления элементы кеша, очередные обрашения к которым в последовательности запросов будут выполняться позже всего. к Напишите псевдокод программы управления кешированием, использующей указанную стратегию.
Входными данными должны быть последовательность запросов (гы гз, ..., г„) н размер кеша й, а на выходе должна получаться последовательность решений об удалениях из кеша (еслн таковые требуются) после каждого запроса. Чему равно время работы вашего алгоритма? б. Покажите, что поставленная задача демонстрирует оптимальную подструктуру. к Докажите, что описанная выше стратегия обеспечивает минимально возможное количество промахов. 48б Часть ЧИ "зсзтертенстеоеанные методы разработки и анализа Заключительные замечания Намного больше материапа по жадным алгоритмам и матроидам можно найти в книгах Лоулера (Ьаьу!ег) [223], а также Пападимнтриу (Рараг)(пйпоп) и Штейглица (Бге)8111х) [269]. Впервые жадный алгоритм был описан в литературе по комбинаторной оптимизации в статье Эдмондов (ЕсЬпопь)з) [100], опубликованной в 1971 году.
Появление же теории матроидов датируется 1935 годом, когда вышла статья Уитни (%Ь)шеу) [353]. Приведенное здесь доказательство корректности жадного алгоритма для решения задачи о выборе процессов основано на доказательстве, предложенном Гаврилом (бауп1) [130]. Задача о планировании заданий изучалась Лоулером [223], Горовитцем (Ногози(гг), Сахни (БаЬп1) и Раясекараном (Ка]азе1сагап) [180], а также Брассардом (Вгаааагб) и Брейтли (Вгаз1еу) [53]. Коды Хаффмана были разработаны в 1952 году [184].
В работе Лелевера (1.е!си ег) и Хиршберга (НпзсЬЬег8) [230] имеется обзор методов сжатия данных, известных к 1987 году. Развитие теории матроидов до теории гридоидов (8геебо10) впервые было предложено Кортом (КогГе) и Ловасом (Ьоуазх) [215-218], которые значительно обобщили представленную здесь теорию. Глава 17. Амортизационный анализ В ходе амортизационного анализа (ашоп(лед апа!угйз) время, необходимое для выполнения последователъности операций над структурой данных, усредляется по всем выполняемым операциям.
Этот анализ можно использовать, например, чтобы показать, что, даже если одна из операций последовательности явпяется дорогостоящей, при усреднении по всей последовательности средняя стоимость операций будет небольшой. Амортизационный анализ отличается от анализа средних величин тем, что в нем не учитывается вероятность. При выполнении амортизационного анализа гарантируется средняя производительность операций в наихудшем случае. В первых трех разделах этой главы описываются три наиболее распространенных метода, которые используются при амортизационном анализе.
Начало раздела 17.1 посвящено групповому анализу, в ходе которого определяется верхняя граница Т(п) полной стоимости последовательности и операций. Тогда средняя стониость операции вычисляется как Т(п)(п. Мы принимаем среднюю стоимость равной амортизированной стоимости каждой операции, так что амортизированная стоимость всех операций одинакова. В разделе 17.2 описывается метод бухгалтерского учета, в котором определяется амортнзированная стоимость каждой операции. Если имеется несколько вядов операций, то каждый нз них может характеризоваться своей амортизированной стоимостью. В этом методе стоимость некоторых операций, находящихся в начальной части последовательности, может переоцениваться.
Эта переоценка рассматривается как своего рода "предварительный кредит" для определенных объектов структуры данных. Впоследствии такой кредит используется для "оплаты*' тех операций последовательности, которые оцениваются ниже, чем стоят на самом деле. В разделе 17.3 описан метод потенциалов, похожий на метод бухгалтерского учета в том отношении, что в нем определяется амортнзированная стоимость каждой операции, причем стоимость ранних операций последовательности может переоцениваться, чтобы впоследствии компенсировать заниженную стоимость более поздних операций. В методе потенциалов кредит поддерживается как "'потенциальная энергия" структуры данных в целом, а не связывается с отдельными объектами этой структуры данных.
Все три перечисленных метода будут опробованы на двух примерах. В одном яз них рассматривается стек с дополнительной операцией Мгп.тгРОР, в ходе ко- Часть ГК усовершенствованные методы разработки и анавиза дво торой со стека одновременно снимается несколько объектов. Во втором примере реализуется бинарный счетчик, ведущий счет от нуля с помощью единственной операции — 1нсккмкнт.
Изучая эту главу, следует иметь в виду, что при выполнении амортизационного анализа расходы начисляются только для анализа алгоритма и что в коде в ннх нет никакой необходимости. Например, если при использовании метода бухгалтерского учета объекту х приписывается какой-нибудь кредит, то в коде не нужно присваивать соответствующую величину некоторому атрибуту наподобие х. стеНИ. Глубокое понимание той или иной структуры данных, возникающей в ходе амортизационного анализа, может помочь оптимизировать ее устройство. Например, в разделе 17.4 с помощью метода потенциалов проводится анализ динамически увеличивающейся и уменьшающейся таблицы. 17.1.
Групповой анализ В ходе груллоаого анализа (аййгейаге апа1уз(з) исследователь показывает, что в наихудшем случае суммарное время выполнения последовательности всех п операций равно Т(п). Поэтому в наихудшем случае средняя, или амортазлроааллая, стоимость (апюгбгей соз1), приходящаяся на одну операцию, определяется соотношением Т(п),1п. Заметим, что такая амортизированная стоимость применима ко всем операциям, даже если в последовательности имеется несколько разных их типов, В других двух методах, которые изучаются в этой главе (методе бухгалтерского учета и методе потенциалов), операциям различного вида могут присваиваться разные амортизированные стоимости. Стековые операции В качестве первого примера группового анализа рассматриваются стеки, в которых реализована дополнительная операция.
В разделе 10.1 представлены две основные стековые операции, для выполнения каждой из которых требуется время 0(1). Рази(5, х) добавляет объект х в стек 5. Рог(Я) снимает объект с вершины стека Я и возвращает его. Вызов Рор с пустым стеком генерирует ошибку. Поскольку каждая из этих операций выполняется в течение времени О(1), примем их длительность за единицу. Тогда полная стоимость последовательности, состоящей из и операций Рцзн и РОр, равна п, а фактическое время выполнения и таких операций — й(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
