16. Ожидаемое время проверки Ti+piT2+piP2T3 + - +piP2 -pn-iTn минимально тогда и только тогда, когда Ti/{1 - pi) < < Tn/{1 - Pn)- [BIT 3 (1963), 255-256; некоторые интересные дополнения получены Джеймсом Р. Слейглом (James R. Slagle), JACM 11 (1964), 253-264.]

17. Выполняйте задания в порядке увеличения их крайних сроков выполнения - независимо от значений Г,! (Естественно, в реальной жизни одни задания важнее других и требуется минимизировать максимальное взвешенное запаздывание; возможно, придется минимизировать сумму ЕГ=1 ™*(-<i"""-"i "~ T>ai,0)- Похоже, однако, что простого решения для таких постановок задач не существует.)

18. Положим h = 1 при наличии s и Л = О в противном случае. Пусть А = {j \ qj < ri}, В = {j \ q, = Tj}, С = {Я qj > rj}, D = {j \ tj > 0}; тогда сумма T,i,j PiPjd\i-j\ Для расположения (q,r) минус соответствующая сумма для расположения {q,r) будет равна

2 {qi-ri){qj-rj){d,-ji-dh+i+2k-i-j) + 2 (qi - ri)tj{dh+2k-i+j - di-i+j).

Эта величина положительна, за исключением случаев, когда С = 0 или AUD = 0. Искомый результат следует из того, что расположения в виде "органных труб" - единственные расположения, которые не могут быть улучшены таким способом (и с помощью его зеркального двойника) при m = О, 1.

(Этот результат получен Г. Г. Харди (G. Н. Hardy), Дж. Э. Литлвудом (J. Е. Littlewood) и Д. Пойа (G. Polya) [Ргос. London Math. Soc. (2), 25 (1926), 265-282], которые показали, что минимум Et j PjH-jl достигается для всех независимых перестановок р я q только при "органном порядке" р и q. Более подробные разъяснения и обобщения можно найти в их книге Inequalities (Cambridge University Press, 1934), Chapter 10.)

19. Все расположения одинаково хороши. Считая, что d{j,j) = О, находим

YPiPjd{i,j) = i ZpiPjidii,j)+diJ,i)) = \с.

(Частный случай d{i,j) = 1 + [j - i) modiV для i ф j был рассмотрен К. Ю. Айверсоном (К. Е. Iverson) в работе А Programming Language (New York; Wiley, 1962), 138. P. Л. Бейбер (R. L. Baber) в работе JACJVf 10 (1963), 478-486, изучил некоторые задачи, связанные с поиском на ленте с возможностью чтения, перемотки или возврата на к блоков без чтения. В. Д. Фрейзер (W. D. Prazer) нашел, что возможно значительное ускорение поиска в случае репликации в файле некоторой информации. В работе Е. В. Eichelberger, W. С. Rodgers, and Е. W. Stacy, JBJVf J. Research & Development 12 (1968), 130-139, имеется эмпирическое решение схожей задачи.)

20. Переходя, как и в упр. 18, от {q,r) к {q, г), получим изменение

Y1 (Ч ~ - rj)idii-ji - min{dh+i+2k~i-j,di+j-.i)),

которое всегда положительно, кроме случаев, когда А пли С является пустым множеством. Вследствие циклической симметрии оптимальные перестановки представляют собой циклические сдвиги "органной" конфигурации. (О другом классе задач с тем же ответом можно прочесть в работе Т. S. Motzkin and Е. G. Straus, Proc. Amer. JVfatii. Soc. 7 (1956), 1014-1021.)

21. Эта задача впервые была решена Л. X. Харпером (L. Н. Harper) [SJAJVf J. Appl. Math. 12 (1964), 131-135]. Обобщения и ссылки на другие работы можно найти в J. Applied Probability 4 (1967), 397-401.

22. Приоритетная очередь размером 1 ООО элементов (представленная, например, в виде кучи; см. раздел 5.2.3). Вставьте в очередь первые 1000 записей, причем элементы с большими значениями d{Kj, К) вставляются в начало очереди. Затем каждым последующим Kj, для которого d{Kj,K) < (начало очереди, АГ), следует заменить первый элемент очереди и переупорядочить ее.

РАЗДЕЛ 6.2.1

1. Докажите по индукции, что при достижении щага В2 АГ( 1 < К < Ku+i и что I < i < и при достижении шага ВЗ.

2. (а, с) Нет; алгоритм зациклится при I = и - 1 и К > Ки- (Ь) Да. Однако при отсутствии в таблице К он будет зацикливаться при I = и и К < Ки -

3. Это алгоритм 6.IT при N = 3. При успешном завершении поиска алгоритм выполняет в среднем {N + 1)/2 сравнений; в противном случае среднее число сравнений составляет N/2 + l-l/{N + l).

4. Это должен быть неудачный поиск с N = 127; следовательно, согласно теореме В ответ равен 138и.

5. Среднее время работы программы 6.1Q составляет 1.75Л-1-8.5 - (Л mod2)/4iV; таким образом, она опережает программу В тогда и только тогда, когда < 44. (Программа С проигрывает при N < 11.)

7. (а) Определенно, нет. (Ь) Примечания в скобках в алгоритме U остаются справедливыми, а потому алгоритм будет работать, но только если при нечетном N ключи Ко = -оо и АГлг+1 = +00 будут присутствовать в таблице.

8. (а) N. Интересно доказать это по индукции, заметив, что при замене iV на iV -I- 1 увеличивается ровно одно из приращений S. (В АММ 77 (1970), 884, можно найти обобщение этого утверждения.) (Ь) Максимум = Ej - А; минимум = 2<5i - Ej = Nт.оА2.

9. Тогда и только тогда, когда = 2* - 1.

10. Используйте "макрорасширение" программы, содержащей таблицу DELTA. Так, для ЛГ = 10 получим следующее.

START

ENTl

СМРА

INCl CMPA JL JE

INCl

CMPA

INCl

CMPA

KEY.l C3A

SUCCESS 3

KEY.l C3B

SUCCESS 1

KEY.l СЗС

SUCCESS 1

KEY.l

SUCCESS

FAILURE

DECl

CMPA

DECl

CMPA

DECl

CMPA

♦

KEY.l C4B t 1

KEY.l C4C ♦ 1

KEY.l

SUCCESS

FAILURE

(B упр. 23 показано, что большинство команд JE можно исключить, получив в результате программу из примерно 6 Ig ЛГ строк, которая выполняется за около 4 Ig ЛГ единиц времени. Однако такая программа окажется быстрее только для N > 1000 (приблизительно).)

11. Рассмотрим соответствующее дерево (например, такое, как на рис. 6): при нечетном N левое поддерево корня представляет собой зеркальное отражение правого поддерева и К < Кг встречается так же часто, как и К > Ki. В среднем, С1 = {C+S) и С2 = (C-S), А = i(l - 5). При четном N дерево имеет тот же вид, что и при N + 1, с метками, уменьшенными на 1 (за исключением узла (о), который при этом становится излишним). В среднем, полагая к = [Ig iVJ, имеем:

Cl =

Cl =

ik + l)N 2(N+1)

C2 - + A (fc + l)(iV + 2)

A = 0

2{N+1)

2{N+1)

при 5=1; при 5 = 0.

(Среднее значение С указано в тексте.) 12.

12 13 14 15 16

Я-2. Я-i Я-i d-L

"12 "13 "14 "15 16

13. ЛГ= 1 2 3 4 5 6 7 8 9 10 11 Cn = 1 1 If 2i 2 2 2f 3 3 3 3

С;, = 1 If 2 2 2 3 3 3§ 3 3 3 4 4 4 4

14. Одна идея заключается в поиске наименьшего М > О, такого, что N + М имеет вид Fk+i - 1. Затем следует установить г <- P/t - М на шаге F1 и вставить в начало шага F2 "Если г < О, то перейти к шагу F4! Лучшим решением будет адаптация метода Шара к поиску Фибоначчи: если результат самого первого сравнения К > Кр,,, установить i <- i - М и перейти к шагу F4 (далее все продолжает работать, как обычно). Это позволяет избежать дополнительных затрат времени работы во внутреннем цикле.

15. Внешние узлы появляются на уровнях от [к/2\ до к - 1; разница между этими числами превышает единицу для всех к, кроме к = О,... ,4.

16. Дерево Фибоначчи порядка А;, отображенное зеркально (так что левое и правое поддеревья меняются местами), согласно "естественному соответствию" из раздела 2.3.2 представляет собой диаграмму размножения кроликов по к-й месяц включительно (надо только удалить верхний узел диаграммы).

17. Пусть длина пути равна к - А{п); тогда A{Fj) = j и A{Fj + т) = 1 + А{т) при О < m < Fj-i.

18. Успешный поиск: Ак = О, С* = {3kFk+i + (к - 4)Fk)/5{Fk+i - 1) - 1, CU = Ck-i(Fk -l)/(Ffc+i - 1). Неудачный поиск: Л = Fk/Fk+x, Ck = {SkFk+i + (к - 4)Fk)/bFk+i, Cl = Ck-iFk/Fk+i + Fk-i/Fk+i. C2 = С - Cl. (См. также упр. 1.2.8-12.)

20. (a) b = p"*"?". (b) В приведенном рассуждении, по меньшей мере, две ошибки. Первая состоит в том, что деление не является линейной функцией и его нельзя просто "усреднять" В самом деле, с вероятностью р получим pN элементов, с вероятностью q их будет qN, так что математическое ожидание составляет (р -- q)N; следовательно, искомый множитель равен 1/(р +9)- Теперь, когда мы выяснили, что после к итераций