AOP_Tom3 (1021738), страница 94
Текст из файла (страница 94)
Идея проверки иь э на шаге К4 является, как мы увидим, решающим моментом для правильной работы алгоритма. Э 9 899 458 — — -~~- Э вЂ” — ~9 899 245 778 577 Этаж 7; — 19 ~.18 — +58 — — тсбб — +77 889 124 677 556 Этаж б: — 24 — +24 — — ЭГ44 — -+44 — +56 — угбб 889 122 677 445 456 455 э: — — ~о — — ~»-~ — — ~-'х-~- 778 122 266 244 Э: — — ~Ю вЂ” — — ~-'О 667 122 Этаж 3: — 13 — +13 23-7гзз 667 112 123 122 Этаж 2: — 67 — 7-03 01-+22 036 011 Этаж 1. — Зб — 7-00 11 000 000 l Начало Конец Рнс.
88. Оптимальный способ перераспределения людей прн помонш небольшого медленного лифзв. (Квждь9й человек представлен номером этажа, нв который он направляется.) п1 = 8ьс1 и1 = с?ы1 — ти при Й < 1 < и; при1<1</с; если и1 — — О и lс <1 < и. (6) (7) (8) и141 = О, Чтобы проверить правильность этого алгоритма, заметим, что на шагах К1 и КЗ всегда поддерживается соответствие данных в массивах и и 4 н (4) текущему состоянию, если считать людей в лифте находящимися на текущем этаже?с. Теперь можно доказать по индукции, что в начале каждого шага справедливы следующие соотношения между параметрами: Кроме того, в начале шага К1 и лифте или на этаже и находится ппп (иь, т) человек, стремяшихся на самые высокие этажи, среди всех людей на этажах < Й, которые хотят попасть на этажи > и.
В начале шага КЗ в лифте илн на этаже )с находится пцп (ню гп) человек, стремящихся попасть на самые низкие этажи, среди всех людей на этажах > 1с, направляющихся на этажи < к. Эти условия также можно проверить по индукции, если проследить, как мы попадаем на шаг К1 нли КЗ (см. упр. 5). Из сказанного выше следует, что замечания в скобках на шагах К1 и КЗ справедливы. Послг каждого выполнения шага К1, следовательно, [иь/т) уменыцается на 1 и [4,е~ /пг) остается без изменений.
После каждого выполнения шага КЗ [4/т) уменыпается на 1 и [нь ~(гп~ остается неизменным. Значит, алгоритм должен завершиться за конечное число шагов, и после этого в силу (6) и (8) каждый человек должен оказаться на своем этаже. 3 16сли иа = О, а иь ~ > О, мы имеем "несвязную" ситуацию; лифт должен подняться до этажа й + 1.
чтобы переместить людей вверх, хотя никому не нужно переезжать с этажей < )с на этажи > к+ 1. Не поступаясь общностькц можно считать ив ~ > О, Тогда лк>бой правильный график должен включать по крайней мере 2 ~~~ шах(1, [иь/пг)) (9) 1<а<о движений, так как мы требуем, чтобы лифт вернулся на первый этаж.
График, для которого достигается эта нижняя граница, несложно построить (см. упр, 4). УПРАЖНЕНИЯ 1. [20) В методе пузырька Р-го порядка, когорый проанализирован в тексте раздела, используются только прямое чтение и перемотка. Можно ли модифицировать алгоритм так, чтобы получать преимущества от обратного чтенияу 2. [Мйб! Найдите явные выражения в замкнутом виде для чисел Л к и Ун, опрелеленвых в (3). [Указание, Проанализируйте решение уравнения 5.2.2-(19) ) 3.
[УВ) Существует ли метод сортировки с двумя лептами, основанный на сравнении ключей (а не на свойствах, представляющих зти ключи цифр), для которого в наихудшем случае при сортировке Ж записей перемещение лент составляет 0(Х 1об Ж)? [При быстрой сортировке зто аначение достигается в среднем, но не в наихудшем случае; в методе КенниСтирнза (см. рис. 86) оно равняегся 0(йг(1ой У)е).[ 4. [МОЯ) В задаче о лифте предположим, что имеются индексы р и д, причем о > р+ 2, пр > О.
и, > О и пре~ — — — — ие ~ = О. Обьясните, как составить график, требующий ве более (9) единиц времени. б. [Мйу] Верно ли следующее утверждение? После шага К1 алгоритма теоремы К никто в лифте не стремится попасть на более низкий этаж, кроме тех, кто остался на этажах < Ь. 6. [МУ0[ (Р.
М. Карп.) Обобщите задачу о лифте (см. рис. 87) для случая, когда на этаже У первоначально находится Ьз пассажиров и на этаж 1' стремится попасть Ь', пассажиров при 1 < 1 < и. Покажите, что сушествует график работы, рассчитанный на 2~„",' шах(1, [ие/гп), [0ь ъ [ш) ) единиц времени, причем на этаже 1' никогда не оказывается одновременно более шах шах(Ь, Ь',) пассажиров.
(Указание. Введите, если необходимо, фиктивньж людей, чтобы равенство Ь, = Ь,' соблюгаачось при всех 11) 7. [М40) (Р М. Карп.) Обобщите задачу из упр б, заменив линейный путь, который проходит лифт, сетью дорог, по которым можно ездить на автобусе, пря условии, что сеть образует любое свободное дерево. Автобус имеет конечную емкость, и желательно перевезти пассажиров к их местам назначения твк, чтобы автобус прошел минимальное расстояние.
В. )ЛИ2] Пусть в задаче о лифте, рассмотренной в тексте раздела, Ь = 1. Сколько перестановок из и человек по и этажам далут в (4) вь < 1 при 1 < Ь < п? )Например, перестановка 3 1 4 5 9 2 б 8 7.) 9. ~М25) Найдите важную связь между шейкер-сортировкой, описанной в разделе 5.2.2 (см. рис.
15), и числами нм им, и„в (4) для Ь = 1. 10. [ЯО! Как бы вы сортировали файлы на нескольких бобинах, имея только два лентопротяжных устройстввэ *5.4.9. Диски и барабаны До сих пор ленты рассматривались как единственное средство для внешней сортировки, однако нередко в нашем распоряжении оказываются и другие типы более функционально гибких устройств внешней памяти. Хотя существует множество конструкций таких запоминакш1их устройств большого объема нли запоминающих устройств с прямым доступом, можно выделить следуюгцие общие для них свойства. ~) Получить доступ к любой заданной части хранимой информации можно довольно быстро.
й) Блоки данных, содержащие последовательные слова, могут быстро передаваться между внутренней (оперативной) и внешней памятью. Накопители на магнитной ленте обладают свойством 1й), но не (1), поскольку перемотка ленты от одного конца к другому отнимает много времени. Каждое внешнее запоминающее устройство имеет свои особенное.ти, которые следует тщательно изучить, прежде чем разрабатывать лля него большие программы.
Однако технология меняется так быстро, что здесь не удастся сколько-нибудь подробно обсудить все существующие разновидности оборудования. Поэтому мы рассмотрим лишь некоторые типичные внешние запоминающие устройства и на них праиллюстрируем продуктивные подходы к задаче сортировки. Одним из наиболее распространенных типов внешних запоминающих устройств, удовлетворяющих (1) и (й), является накопитель на магнитном диске (НМД), схематически показанный на рис. 89. Данные хранятся на нескольких быстро вращающихся круглых дисках, покрытых магнитным материалом.
Для записи или выборки информации используется держатель головок в виде гребешка, включающий одну или несколько головок чтения/записи для каждой поверхности дигка. Каждая поверхность делится на концентрические кольца, называемые дорожками или треками, так что за время одного оборота диска под головкой чтения/записи проходит целая дорожка. Держатель головок может перемещаться в двух направлениях — внутрь и наружу, передвигая головки чтения/записи от одной дорожки к другой, но зто движение требует времени. Множество дорожек, которые могут быть прочитаны или записаны без перемещения держателя головок, называется цилиндром.
Например, на рис. 89 показан НМД, который имеет по одной головке чтения/записи на каждую поворхностьл пунктирными линиями обозначен один из цилиндров, состоящий из всех дорожек, просматриваемых в настоящий момент головками. Держатель головок Рис. 8В. Накопитель на магнитных лисках. Чтобы конкретизировап эти рассуждении, рассмотрим гипотетический НМД И1ХТЕС, для которого 1 дорожка = 5000 символов, 1 цилиндр = 20 дорожек, 1 дисковый накопитель = 200 цилиндров. На таком устройстве хранится 20 млн символов, т. е, чуть меньше того объема данных, который можно записать на одну магнитную ленту в НМЛ М1ХТ. В некоторых устройствах на дорожках вблизи центра содержится меньше символов, чем на дорожках, расположенных ближе к краю.
Это значительно у(шожняет программирование, но М1ХТЕС, к счастью, не создает подобных проблем, (См. раздел 5,4.6, в котором обсуждаются характеристики НМЛ М1ХТ. Здесь будут рассматриваться классические технологии, пригодные для работы с типичными для 70-х годов устройствами; более современные диски имеют ббльшпй объем хранимой информации и ббльшую скорость обращения к ней.) Время, необходимое для чтения или записи на диск, представляет, по существу, сумму трех величин. ° Время поиска (время, затрачиваемое на перемещение держателя головок к нужному цилиндру). в Время ожидания (задержка, связанная с вращением диска, пока головка чтения/записи не достигнет нужного места). ° Время передачи (задержка, связанная с вращением диска, пока данные проходят под головками). В НМД М1ХТЕС время поиска для перехода от цилиндра т к цилиндру у равно 25 + -'~т — Я мс.
Если т и / — случайно выбранные целые числа между 1 и 200, то среднее значение )т' — у( равно 2( е')/200 — 66.7, т. е, среднее время поиска составляет приблизительно 60 мс. Диски МТХТЕС совершают один оборот за 25 мс, так что время ожидания равно в среднем 12.5мс. Время передачи и символов равняется (а/5000) х 25 мс = 5п мкс. (Это приблизительно в 3-' раза больше, чем скорость передачи для НМЛ И1ХТ, использованного в примерах из раздела 5.4.6.) Таким образом, основные различия между НМД М1ХТЕС и НМЛ М1ХТ, касающиеся сортировки, следующие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
