Первое доказательство. Предположим, что условие (20) выполнено. Известно, что любую перестановку записей можно привести к "рассортированному" состоянию, т. е. привести ее к виду R1R2.. .Rn с использованием только перестановок двух соседних элементов. Каждая из таких перестановок заменяет ... RjRi... на ...RiRj... для некоторых i < j, тем самым уменьшая время поиска на неотрицательную величину PiLj - PjLi. Следовательно, порядок расположения записей Ri R2.. .Rn должен иметь минимальное время поиска, т. е. быть оптимальным.

Второе доказательство. Заменим каждую вероятность pi на

Рг{е) =рг + е-{е+е + --- + е)/Л, (21)

где е - очень малое положительное число. При этом равенство xipi{e) -f • -Ь xnPnI) = yiPi(e) + • • • -1- yjvpjv(e) справедливо только в том случае, когда xi =2/1, ..., Xn = Vn- Отсюда, в частности, следует, что в (20) равенство никогда не будет выполняться. Рассмотрим TV! перестановок записей. Среди них есть, по меньшей мере, одна оптимальная, которая в соответствии с первой частью доказательства удовлетворяет условию (20). Однако поскольку теперь в условии (20) равенства невозможны, то и оптимальная перестановка может быть только одна. Следовательно, условие (20) однозначно определяет некоторую оптимальную перестановку для вероятностей Pi(e), причем е достаточно мало. Исходя из непрерывности тот же порядок должен быть оптимален и при е = 0. (Такой тип доказательств нередко используется в комбинаторной оптимизации.)

Теорема S была доказана В. И. Смитом (W. Е. Smith) [Naval Research Logistics Quarterly 3 (1956), 59-66]. В приведенных ниже упражнениях содержатся дополнительные результаты оптимальной организации файлов.

УПРАЖНЕНИЯ

1. [М20] Пусть все ключи поиска равновероятны. Определите стандартное среднеквадратичное отклонение числа сравнений при успешном последовательном поиске в таблице с записями.

2. [15] Измените алгоритм S для использования связанных записей вместо индексов. (Если Р указывает на запись в таблице, полагаем, что KEY(P) - ключ, INFO(P) - связанная с ключом информация и LINK(P) - указатель на следующую запись. Полагаем также, что FIRST указывает на первую запись, а последняя запись указывает на Л.)

3. [16] Напишите MIX-программу для алгоритма из упр. 2. Чему равно время выполнения программы (с использованием С и S из (1))?

► 4. [17] Можно ли использовать идею алгоритма Q для таблиц в виде связанных записей (см. упр. 2)?

5. [20] Программа Q выполняется существенно быстрее программы Q при больших значениях С. Существуют ли значения С и S, при которых программа Q будет выполняться дольше, чем программа Q?

► 6. [20] Добавьте три инструкции в программу Q, которые позволят ей выполняться за время около (З.ЗЗС -(-constant)и.

7. [М20] Определите среднее число сравнений (3) в случае "бинарного" распределения вероятности (5).

8. [НМ22] Найдите асимптотический ряд для Яп при п - оо; а; ,1 1.

► 9. [НМ28] В тексте отмечено, что распределения вероятностей, данные в (И), (13) и (16), приблизительно одинаковы при О < в < 1 и что среднее число сравнений с использованием (13) равно gN + OiN-").

a) Означает ли это, что число сравнений равно grN + 0{N~) при использовании распределения (11)?

b) Верно ли это утверяодение для распределения (16)?

c) Сравните (11) и (16) с (13) при в<0.

10. [М20] Наилучшее расположение записей в последовательной таблице определяется условием (4). А что собой представляет наихудшее расположение? Покажите, что имеется простое соотношение между средним количеством сравнений при наилучшем и наихудшем размещениях записей.

11. [МЗО] Цель этого упражнения заключается в анализе предельного поведения самоорганизующегося файла при использовании эвристического метода перемещения записи в начало файла. Сначала введем некоторые обозначения. Пусть fm{xi,X2,. ,Хт) равно бесконечной сумме всех различных упорядоченных произведений Xi ж,2 ... Жг,, таких, что 1 < ii,... ,ik < т, причем каждое xi,X2,--.,Xm входит во все произведения. Например,

f2{x,у) = {х+у(х + у) + у+х{х + yf) = - J- (- + .

j,k>o i-y/

Исходя из множества X из п переменных {хг,... ,Хп}, положим

Рпт = fm{xjj, . . . ,Xj„); Qnm = -~-

Например, Рз2 = /2(1,2:2) + /2(2:1, жз) + /2(2:2, Жз) и Q32 = 1/(1 - Xi - Х2) + 1/(1 - xi -Хз) + - Х2 - Хз). По определению полагаем Рпо = Qno = 1-

a) Предположим, что в самоорганизующийся файл запросы на поиск элемента Ri поступают с вероятностью pi. Покажите, что после достаточно длительной работы системы элемент Ri оказывается на т-м месте с предельной вероятностью PiP(n-i)(,m-i), где множество А представляет собой {pi,... ,pi~i,pi+i,.. .,pn}.

b) Суммируя результат (а) для m = 1, 2,..., получаем тождество

Рпп -Ь Pn(n-l) -(-•• -Ь РпО = Qnn.

Получите отсюда следующие соотношения:

/п-т+1\ /п-т + т\

гпт -\- у Jn(m-l) + + у jrnO-Qnm,

Qnm - у JVn(m-l)H-----г(-1) ( jQnO = rnrn.

c) Вычислите предельное среднее расстояние di = J2m>i mpiPN-i.m-i записи Ri от начала таблицы; затем вычислите См = iLiPtdi.

12. [М23] Используйте (17) для вычисления среднего количества сравнений, необходимого для поиска в самоорганизующемся файле при бинарном распределении вероятностей ключей поиска (5).

13. [М27] Используя (17), вычислите Cn для распределения вероятностей (6).

14. [М21] Даны две последовательности действительных чисел- {xi,X2,... ,Хп) и {у1,у2, ...,у„). Какая перестановка индексов aia2...a„ делает сумму Х, ЖгУа; максимальной, минимальной?

► 15. [М22] В тексте было показано, как оптимально расположить программы на ленте системной библиотеки для поиска только одной программы. Однако при работе с библиотекой подпрограмм, когда для работы программы пользователя необходимо загрузить различные подпрограммы, следует принять другой набор предположений.

В этом случае предположим, что запрос на подпрограмму j поступает с вероятностью Pj, причем вызовы различных подпрограмм независимы. Тогда, например, вероятность того, что не Потребуется ни одна подпрограмма, равна (1 - Pi)(l - Р2).•.(! - Pn), а вероятность того, что поиск прекратится после загрузки j-й подпрограммы, равна Pj (1 - Pj+i)... (1 - Pn)- Если Lj - длина j-й подпрограммы, то среднее время поиска будет пропорционально

LiPi{l - р2) - - .{I - Pn) + [Lx + l2)p2{1 - Рз) - - {I - Pn) + + [Lx + - + Ln)Pn-

Каким в этом случае должно быть оптимальное расположение подпрограмм на ленте?

16. [М22] (Г. Ризель (Н. Riesel).) Зачастую необходимо проверить, выполняются ли одновременно п заданных условий. (Например, может понадобиться проверить, что а; > О и у < , и при этом не ясно, какое условие должно проверяться первым.) Предположим, что проверка j-ro условия занимает Т, единиц времени и что условие выполняется с вероятностью Pj (причем эта вероятность не зависит от результатов выполнения других условий). В каком порядке должны выполняться проверки?

17. [М23] (В. И. Смит (W. Е. Smith).) Предположим, имеется п заданий; j-e задание занимает Т, единиц времени; крайний срок его выполнения - Dj. Другими словами, j-e задание должно быть выполнено не позже момента Dj. Какое расписание работ 0102 - - - а„ минимизирует максимальное запаздывание, т е.

тах(Га1 -Da, , Та, +Та, -Da, , - - ,Та, +Та, + -(-Та„ -Z?a„ ) ?

18. [МЗО] {Сцепленный поиск.) Предположим, что Л записей расположены в памяти в виде линейного массива Ri ... Rn и вероятность поиска записи Rj равна pj. Поиск называется "сцепленным", если каждый последующий поиск начинается с того места, где завершился предыдущий. Если последовательные поиски независимы, то среднее время поиска составляет Y1 PiPjd{i,j), где d{i,j) - время, которое необходимо для поиска,

l<i,j<iV

начинающегося в позиции г и заканчивающегося в позиции j. Эта модель может быть применима, например, ко времени поиска дискового файла (при этом d{i,j) представляет собой время перемещения между г- и j-м цилиндрами диска).

Цель данного упражнения - описать оптимальное размещение записей для сцепленного поиска в случае, когда rf/г, j) представляет собой монотонно возрастающую функцию от г - j\, т.е. d{i,j) = d,-j и di < 2 < • • • < лг-1 (величина do не существенна). Докажите, что размещение будет оптимально тогда и только тогда, когда будет выполняться

условие либо Pl < PN < Р2 < PN-l < ••• < PIN/2J+1, либо PN < pi < PN-1 < P2 <

• < P\N/2j. (Другими словами, наилучшее расположение - в виде "органных труб", показанных на рис. 2.) Указание. Рассмотрите расположение, которому соответствуют вероятности qi q2 .. qk s гк ... Г2 ri ti . .. tm для некоторых т>ОиА;>0; Л = 2А;--т-Ь1. Покажите, что расположение ql q2 ... qk s rl... г2 rl ti ... tm лучше, если gj = min {qi,ri) и ri = max {qi,ri), за исключением случая, когда = g; и = г; для всех г, и случая = г;, ri = g, и fj = О для всех г и j. То же самое справедливо при отсутствии s vi N =2к + т.

19. [М20] Продолжая выполнять упр. 18, найдите оптимальное расположение для сцепленного поиска, если функция d{i,j) обладает следующим свойством: d{i,j) + d{j,i) = с для всех i ф j. (Такая ситуация возможна, например, при поиске на ленте без возможности обратной перемотки и с неизвестным нам направлением поиска; для г < j имеем d{i,j) =