AOP_Tom3 (1021738), страница 101
Текст из файла (страница 101)
92, будет пропорционально (з/2+;/4+ ь/1+ пг1+з/8) + (ь/1+ з/1+ з/2) + (ь/1+ з/2+ з/1+ з/4) +(Л+ ь/1+ з/2) . Это значение б»ь%+ + +/ Г т ) узлам, где полдеревья данных узлов имеют (пм, .., и ) листьев. Напишите программу, которая порождает деревья с минимальным вреиенем поиска, имеющие 1, 2, 3, ... листьев, используя для опенки времени поиска эту формулу. 15.
[М28] Покажите, что можно несколько "усилить" теорему Г, если лифт первоначально пуст и если Е(6)п Зе !. В этом случае необходимо не менее [(Г(6)п+ т — !)/(Ь+ гп)] остановок. 10. [33] (Р. У. Флойд.) Найдите график работы лифта, перевозящего всех людей из (28) к их местам назначения через 12 или менее остановок. (В (29) показано положение после одной, вне после двух остановок.) ь 17.
[Л?М35] (Р. Флойд, 1980.) Покажите, что нижняя оценка в теореме Р может быть улучшена до п(Ып и — !пЬ вЂ” 1) !пи+ 6(1 + !п(1+ т/6)) в том смысле, что некоторая исходная конфигурация должна потребовать, по крайней мере, столько остановок. [Указание.
Пересчитайте конфигурации, которые могут образоваться после д остановок.] 18. [НМ86] Пусть 1 — нижняя оценка из упр 17. Покажите, что греднее число остановок лифта, необходимое для того, чтобы доставить всех паггажиров по назначению, будет не менее Š— 1, когда равновероятны все (6п)! возможных перестановок 6п пассажиров ь 19. [35] (Б. Т. Беннет (Б. Т. Веппем) и А. Ч. Мак-Келлар (А. С, МсКе!1эг), 1971.) Рассмотрим следующий подход к сортировке ключей, продемонстрированный на примере файла с 10 ключами. !) Исходный файл: (50Дд)(08Д1)(51Дд)(ООДзН90,П)(1?Дз)(89Дд)(2?оН)(55Дд)(42Дд) й) Файл ключей: (50, О)(08, 1)(51., 2)(05, 3)(90, 4)(17, 5)(89, б) (27, 7)(05, 8)(42, 9) ш) Рассортированный файл клвэчей (й): (06, 3)(08, 1)(17, 5)(27, 7)(42.
9)(50, 0)(51, 2)(65. 8) (89, 6) (90, 4) !г) Присвоение номеров ящиков (см. ниже): (2, 1)(2, 3)(2, 5)(2, 7)(2, 8)(2,9)(1., 0)(1, 2)(1. 4) (1, 6) у) Рассортированные номера ящиков (!и); (1, О) (2, 1)(1, 2)(2, 3)(1, 4) (2, 5)(1, 6) (2, 7) (2, 8) (2, 9) к!) (!) Исходный файл, распределенный цо ящикам с использованием рассортировшгных номеров ящиков (у); Ящик 1: (50, Уа)(51,?г)(90, Г4)(89, 1е) Ящик 2: (08, Д)(06, ?а)(17, Га)(27, 1гН65, Уе)(42, Хэ) зби) Результат выбора г замещением (сначала читается ящик 2, затем — ящик 1): (06, 1з)(08, 7~) (17, ?э) (27, ?г)(42, ?э)(50.?о)(51, ?э)(65, уа)(89, ?е)(90, 1э) Номера ящиков на шаге (!я) присваиваются путем применения к (й!) амбара с замещением справа налево е поулдке убывания по второй компоненте.
Номер ящика — это номер серии. В приведенном примере используется выбор с замещением только с двумя элементами в дереве. Для выбора с замещением в (!х) и (тй) должен использоваться один и тот же размер дерева выбора Заметим, что содержимое ящиков необязательно упорядочено. Докажите, что этот метод позволит выполнять сортировку, т. е. что выбор с замещением в (чй) образует лишь одну серию. (Этот метод уменьшает число ящиков, необходимых для обычной сортировки ключей посредством распределения, особенно если исходные данные уже в значительной степени упорядочены.) ь 20.
[95) Некоторые системы предоставляют в распоряжение программиста еирг йальную памяшь: можно писать программы, исходя из предположения, что имеется очень болыной объем оперативной памяти, способной вместить все данные. Эта память разделена на страницы, и лишь немногие из них действительно в произвольный момент времени находятся в оперативной памяти; остальные же хранятся на дисках или барабанах. Программисту не нужно вникать во все этн подробности, так как система гама обо всем заботится: новые страницы автоматически вызываются в память, когда в них возникает необходимость.
Может показаться, что появление виртуальной памяти приводит к отмиранию методов внешней сортировки, так как эта работа может быть выполнена с помощью методов, предназначенных для внутренней сортировки. Проанализируйте такую ситуацию. Почему специально разработанный метод внешней сортировки может оказаться лучше применения обычной технологии подкачки страниц к методу внутренней сортировки? ь 21. [М15) Сколько блоков переходит на диск у'из Е-блочного файла при разделении на ?у дисков? 22.
[32[ Пусть сливаются два файла по принципу Гилбрета и желательно сохранить ключи аэ с а блоками и ключи 17, с Ь блоками. В какой блок необходимо поместить а, дли того, чтобы получить при необходимости нужную информацию? ь 23. [80) Какой объем памяти необходим для входных буферов, в которых предполагается довольно продолжительно хранить исходные данные, если выполняется 2-путевое слияние посредством (а) разделения суперблоков; (Ь) принципа Гилбрета? 24. [МУ6[ Предположим, что Р серий разделены между?7 дисками так, что блок у' серии?с находится на диске (хь + 7) шос1 В.
При выполнении Р-путевого слияния эти блоки будут считываться в некотором хронологическом порядке, гюдобном (19). Если группы из Р блоков должны вводится продолжительное время, то в момент времени 4 мы будем считывать с каждого диска!-й в хронологическом порядке блок, как в (21). Каков минимальный обьем буфера в памяти (в количестве записей), необходимый длн хранения исходных данных, которые еще не были вовлечены в процесс слияния, если не учитывать хронологический порядок? Объясните, как выбрать смещения х„хг, ..., хр с тем, чтобы в худшем случае требовалось как можно меньше буферов. 26. [23] Повторите пример из текста раздела, рассмотренный в связи с раыдомизированным разделением, изменив условия: пусть лс = 2 вместо !'„! = 4.
Что окажется в буферах в отличие от (24)? 26. ]26] Сколько выходных буферов необходимо, чтобы выполнение Р-путевого слияния с рандомизироваиным разделениел» никогда не было приостановлено из-за отсутствии места в памяти для размещения только что полученных в результате слияния данных? Считайте, что время записи блока равно врел»ени считывании.
27. (НМ27] (Проблема циклической заив»пос»ли.) Предположим, что и пустых урн расставлены по кругу и им присвоены номера О, 1,, и — 1. При?с = 1. 2,..., р мы бросаем тл в»аров в урны (Хл + 1) гпо»1 и, 1 = О, 1, ..., тл — 1, где целые числа Хл выбираются случайно. Пусть Е„(»п»,..., глр) — число шаров в урне О, а Е„[»пы, тр) — ожидаемое число шаров в самой заполненной урне.
а) Докажите, что Ев(т», ..,, тр) < 2„»'" » ш!п(1, и Рг(Я„(т»,..., тр) > !)), где т = т, + + гпр. Ь) Используя неравенство и соотношении 1.2,10 — (25), докажите, что Е„(т»,..., глр) ( ~ппп(1, I п(1 + а»/п)»Р '» »=» (1+ а» ' для любых неотрицательных действительных чисел а», аг, ..., а . Какие значения а»,, а, дадут наилучшую верхнюю оценку? 20.
(НМ47] Продолжая упр. 27, ответьте, справедливо ли неравенство Е„(»оы..., тр) > Е„(т» + тг, тг,... тр) . р 29. (М30] Назначение етого упражнения —. вывести верхнюю оценку среднего времени, необходимого для ввода любой последовательности блоков в хронологическом порядке при выполнении процедууры рандомизированного разделения, когда блоки представляют Р серий и Р дисков. Мы говорим, что блок, ожидаемый на некотором временном цикле в то время, когда выполняется алгоритм (см. (24)), является "маркированным"; таким образом, суммарное время ввода пропорционально числу маркированных блоков.
Маркирование зависит только от хронологической последовательности доступа к блокам (сл».(20)). а) Докажите, что если»с+ 1 последовательных блоков в хронологическом порядке имекгт »У» блоков нв диске /, то не более шах(№, !»'»,...,Мп») из них являются л»аркироввиными. Ь) Усильте результат (а), показав, что он имеет место также для Я+ 2 пош»едовательных блоков. с) Теперь используйте результаты анализа проблемы пикличсской занятости из упр. 27 и получите верхнюю оценку среднего времени выполнения в терминах функции г(Р, Я+ 2), как в табд.
2, задан любой хронологический порядок. ЗО. (НМ30] Докажите, что для функции г(»?,т) из упр 29 при л. -л оо выполняется условие г(»4, р»4!об»4) = 1 + 0(1/л»гр ) для фиксированного ф 31. (НМ48] Проанализируйте рандомизированиое разделение и определите поведение этого алгоритма в среднем, а не только по отнов»ению к верхней опенке, как функцию от Р, Я и Р. (Интересен даже случай для»С = О, когда требуется в среднем б»(Е/л/Р) циклов чтения,) 5.5. РЕЗЮМЕ. ИСТОРИЯ И БИБЛИОГРАФИЯ ТкпьРь, кОГдА мы почти достигли конца этой очень длинной главы, "рассортируем" наиболее важные из рассмотренных выше сведений.
Алгоритм сортировки — это процедура, которая реорганизует файл записей таким образом, что ключи оказываются расположенными и порядке возрастания. Вследствие такого упорядочения группируются записи с равными ключами, становится возможной эффективная обработка множества файлов, рассортированных по одному ключу, создается информационная основа для эффективных алгоритмов выборки и более убедительно выглядят документы, подготовленные г помощью компьютера.
Внутренняя сортировка используется в тех случаях, когда все записи помещаются в быстродействуюп1ей внутренней памяти компьютера. Мы изучили с разной степенью детализации более двух десятков елгоритмон внутренней сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
