Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2), страница 2

есть число записей в блоке 1, принадлежащих блоку 1', Если и > Ь, то существует начальное расположение, для которого все впэ < 1, так что 1 = О. Следовательно, для переразмещения записей необходимо выполнить хотя бы 1(Ь)н/(Ь+ т) ж (Ьп 18Ь)1'гп операций чтения блока. (Если Ь велико, то множитель 1яЬ делает эту нижнюю оценку нетривиальной.) В упр. 17 выведена несколько более строгая нижняя оценка для общего случая, когда т существенно больше Ь.

УПРАЖНЕНИЯ 1. [Мйй[ В тексте раздела аналнзируетвя метод, с помощью которого среднее время ожидания, необходнмое для чтения доли х дорожки, уменыпается с —,' до -,'(1 — х~) оборотов. Это минимально возможное время, когда имеется один держатель головок, Каково соответствующее минимальное время ожидания. если имеется два держателя головок, разнесенных на 160' (в предположении, что в любой момент данные могут передаваться только через головки на одном нз держателей)2 2. [МУО) (Л. Г. Конхейм (А.

С. Ковйе1ш).) Назначение этого упражнения — - исследовать, на какое расстояние должен переместиться держатель головок во время слияния файлов, расположенных "ортогонально" к цилиндрам. Допустим, имеется Р файлов, в каждом нз которых содержится б блоков записей, и предположим, что первый блок каждого файла находится на цилиндре 1. второй — на цилиндре 2 н т. д. Движением держателя головок во время слияния управляет относительный порядок последних ключей каждого блока; ы!едовательно, можно изобразить ситуацию следующим способом, удобным для математической интерпретации. Рассмотрим ннов!астап из РХ упорядоченных пар (а!!, 1) (аз! 1) ° ° (ар! 1) (аць 2) (аю, 2) ...

(ар!, 2) (а!с, Х) (асс, Х) ... (а! г,, Х) где множество (а;; [ 1 < ! < Р, 1 < у < Ц состоит из чисел (1, 2,..., РЦ в некотором порядке н ам < ац +ц при 1 < 7 < Х (строки представляют цилиндры, столбцы— исходные Файлы). Рассортируем пары по кх первым компонентам и будем считать, что получилась последовательность (1,2!) (2, у!)...

(РХ,,урс). Покажите, что если все (РЙ)![ХЗ! возможных наборов о;, равновероятны, то среднее значение )у! я![+ [уз 72[ + ' '+ [Эр!. урс ![ равно (Х вЂ” 1) (1+(Р— 1)2~~ ~/( )) . [Указинце. См. упр. 5.2.1-14.] Заметим, что при Х -+ оо зто значение асимптотическн стремится к -',(Р— 1)Х,~йХ+ 0(РЦ. 3. [М15[ Предположим, что ограниченный размер внутренней памяти делает нежелательным 15-путевое слияние.

Как можно изменить рекуррентные соотнощения (3)-(5), чтобы А!(и) имело минимальное значение оР(Т) +,9Е(Т) среди всех деревьев Т с и листьями, не имеющих узлов степени, большей, чем 92 4. [Мйу) Рассмотрим модифицированный вариант квадратичной схемы выделения буферов, при которой все Р входных буферов име!от равные объемы, а объем выходного буфера нужно выбрать из соображения минимизации времени поиска. а) Выведите формулу, аналогичную (2), для времени выполнения Р-путевого глияния 5 символов.

Ь) Покажите, что построение в теореме К можно изменить так, что получится схема слияния, которая будет оптимальной в смысле вашей формулы из п. (а). 5. [Мйд) Если используются два диска, причем чтение с одного совмещается с записью на другой, то нельзя применять схему слияния, подобную представленной на рис. 93, так как одни листья находятся на четных уровнях, а другие — на нечетных.

Покажите, как изменить построение в теореме К, чтобы получались оптимальные деревья с учетом ограничения, что все листья находятся на четных уровнях или все на нечетных. 6. [29) Найдите дерево, оптимальное в смысле упр. 5, егли и = 23 н а = !3 = 1. (Возможно, у вас появится желание прибегнуть к помощи компьютера.) 7. [М94[ Если длины начальных серий не равны, та наилучшая схема слияния (в смысле теоремы Н) минимизирует оХ1(Т) + 9Е(Т), где Х1(Т) и Е(7") теперь представляют собой езесшгжвмс длины путей: каждому листу дерева приписываются веса ю!,..., ю„(гоответствуквцие длинам начальных серий), а суммы степеней и длины путей умножаются на соответствующие веса.

Например, если 7 — дерево, представленное на рис. 92, то получим Х1(Т) = бы! + б!л! + 7юз +9ю! + 9юз + 7юз + 4кт+ 4юэ, Е(7) ы 2ю! + 2в!! + 2юз + Зги! + Зю! + 2ые + в!! + ав Докажите, что при некотором к всегда существует оптимальная схема, в которой первыми слиыцотся й самых коротких серий. 8. [49] Существует ли алгоритм, который при заданных а„9 н весах шп..., ю находит оптимальные в смысле упр.

7 деревья, затрачивая только О(и') шагов при некотором с? 9. [НМур] (Л. Хьяфял (1.. Нуа|1), Ф. Прускер (Г. Ргпайег) и Ж. Вуйлемен (1. Ъп!0еш!и).) Доюьжите, что для фиксированных а и !У получается А~(и) = (ш!и /! и!обо+О(и) от+8 г и>2 !Обт при и -г оо, где член О(и) > О. 10. [11ЛЩ) (Л. Хьяфил, Ф. Прускер и Ж. Вуйлемеи.) Докажите, что при фиксиргеанных и и /! Аг(и) = ото+ би+ А (и) для всех достаточно больших и, если т минимизирует козффициент в упр. 9.

11. [М39] В обозначениях (6) и (11) докажите, что / (и) + ти > /(и) при всех т > 2 и и > 2, и определите все т и и, при которых имеет место равенство. 12. [85] Докажите, что при всех и > 0 существует дерево с и листьями н минимальной длиной степенного пути соответственна (6), все листья которого расположены иа одном уровне. 13. [М84] Покажите, что при 2 < и < г((а,б), гдето(а,8) определено в соотношении (12), единственной наилучшей схемой слияния в смысле теоремы Н является и-путевое слияние.

14. [40) При использовании квадратичного метода распределения буферое время поиска для схемы слияния, предстшленной на рис. 92, будет пропорционально (з/2 + з/4+ з/1 + з/1+ ~/8) + (з/1+ Л+ ~/2) + (з/1+ ~/2+ з/1+ ъ14) +(Л+ з/1+ з/2) . Это значение Р бма 1 ЬК-:- + -кхт':т Г ю~ узлам, где полдеревья данных узлов имеют (и,,...,и„,) листьев.

Напишите программу, которая порождает деревья с минимальным временем поиска, имеющие 1, 2, 3,, листьев, используя для оценки времени поиска эту формулу. 15. [Мйй] Покажите, что можно несколько "усилитьв теорему Р, если лифт первоначально пуст и если Е(6)и ф й В эгон случае необходимо не менее [(Г(Ь)и+ ги — !)/(Ь+ т)] остановок. 16. [98] (Р.

У. Флойд.) Найдите график работы лифта, перевозящего всех людей из (28) к их местам назначения через 12 или менее остановок. (В (29) показано положение после одной, а ие после двух остановок,) и 17. [НМ85] (Р. Флойд, 1980.) Покажите, что нижняя оценка в теореме Р может быть улучшена до и(6 1п и — !п Ь вЂ” 1) !п и+ Ь(1 + !п(1 + т/6)) в там смысле, что некоторая исходная конфигурация должна потребовать, по крайней мере, столько остановок. [Убиение. Пересчитайте конфигурации, которые могут образоваться после з остановок.] 18.

[ЖХ8б] Пусть 1 — нижняя оценка из упр. 17. Покажите, что среднее число остановок лифта, необходимое для того, чтобы доставить всех пассажиров по назначению, будет не менее 1 — 1, когда равновероятны все (6и)! возможных перестановок Ьи пассажиров. ь 19. [95] (Б. Т. Беннет (В.

Т. Веппеы) и А. Ч. Ыак-Келлар (А. С. У!сКе)!аг), 1971.) Рассмотрим следующий подход к сортировке ключей, продемонстрированный на примере файла с 10 ключами. !) Исходный файл: (50,1о)(08,1~)(51,1з)(06,1з)(90,1з)(17,1е)(89,1е)(27,1г)(65,1е)(42,1е) й) Файл ключей; (50, 0)(08, 1)(51, 2)(06, 3) (90, 4)(17, 5) (89, 6)(27, 7)(65, 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,о)(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) Исходный файл, распределенный по ящикам с использованием рассортированных номеров ящиков (г): Ящик 1: (50, 1о)(51, 1з)(90, А)(89, 1в) Ящик 2: (08, 1г)(06, 1з)(17, 1з)(27, 1г)(65, 1з)(42,1з) гй) Результат выбора с замещением (сиачала читается ящик 2, затем — ящик 1): (06, 1з) (08, 1~ )(Г7, 1з) (27, 1тИ42, 1з) (50, 1в)(51, 1з)(65, 1а)(89, 1е) (90, 1з) Номера ящиков иа шаге (Ь) присваиваются путем применения к (гй) выбора с замещеяигм справа ивлеве в порядке убывания по второй компонеите, Номер ящика -- это номер серии.

В приведенном примере используется выбор с замещением только с двумя элементами в дереве. Для выбора с замещеиием в (и) я (тй) должен использоваться один и тот же размер дерева выбора, Заметим, что содержимое ящиков необязательно упорядочено. Докажите, что этот метод позволит выполнять сортировку, т. е. что выбор с замещением в (гй) образует лишь одну сернкь (Этот метод уменьшает число ящиков, необходимых дяя обьщной сортировки ключей посредством распределения, особенно если исходные данные уже в значительной степени упорядочены.) ь 20.

[33[ Некоторые системы предоставляют в распоряжение программиста воршрольиую помюпсч можно писать программы, исходя из предположения, что имеется очень большой обьем оперативной памяти, способиой вместить все данные. Эта память разделена иа страницы, и лишь немногие из иих действительно в произвольный момент времени находятся в оперативной памяти; остальные же хранятся на дисках или барабанах. Программисту ие иужно вникать во все эти подробности, так как система сама або всем заботится: новые страницы автоматически вызываются в память, когда в иих возникает необходимость.