5. Рассмотрим Ь = 2, m = 4 и следующее поведение алгоритма.

Этаж 7: - 47-;я;77-

5667 4566

Этаж 6: - 23-/23--

5667 2345

Этаж 5: - 14-14-\;45-у-

5667 1234 2345

Этаж 4: - 71-f 15-Vli-

5566

Этаж 3: - 63-f 23-

2556

Этаж 2: - 62-f 00-

0055

Этаж 1: - 55-foo-

0000

Теперь 2 (в лифте) меньще, чем 3 (на третьем этаже).

[После построения примера, подобного этому, читателю должно быть ясно, как установить справедливость более слабого свойства, используемого в доказательстве теоремы К.]

6. Найдем минимальные г, j, такие, что Ь; < Ь\ ж bj > bj. Введем нового человека, который хочет переехать с этажа i на этаж j. При любом к это не увеличит max{uk,dk+i, 1) или max(bk,bk). Продолжим процесс, пока не получим bj = bj при всех j. Теперь заметим, что алгоритм в тексте раздела, если изменить b на Ьк на щагах К1 и КЗ, по-прежнему работает.

8. Пусть их число будет Р„ и пусть Qn - число перестановок, для которых = 1 при 1 < А; < п. Тогда Р„ = QiPn-i + QiPn-i + + QnPo, Ро = 1- Можно показать, что Qn = 3"~ при п > 2 (см. ниже), поэтому, используя производящие функции, получим

Y Рп-г" = (1 - Зг)/(1 - 4z + 2z) = 1 + z + 2z + 6z + гОг" + 68z + • • •;

2P„ = (2-(-V)"-4(2-V)-\

Чтобы доказать, что Qn = 3"", рассмотрим тернарную последовательность xiX2 ...Хп, такую, что XI = 2, Хп = О и д < Хк < 2 при 1 < к < п. Следующее правило определяет взаимно однозначное соответствие между такими последовательностями и требуемыми перестановками aiai.. .an.

!max{j I (j < А; или Xj = 0) или j - если Xk = 0; A:, если Xk = 1;

min{j I (j > A; или Xj = 2) или j = n }, если Xk = 2.

(Это соответствие было получено автором совместно с Э. А. Бендером (Е. А. Bender).)

9. Число проходов щейкер-сортировки равно 2 max(ui,..., Ип)-(0 или 1), так как каждая пара проходов (слева направо, справа налево) уменьшает каждое ненулевое и на 1.

10. Начните с какого-нибудь метода распределения (быстрая или обменная поразрядная сортировка), пока не получатся однобобинные файлы. И наберитесь терпения.

РАЗДЕЛ 5.4.9

1. \ - (х mod ) оборотов.

2. Вероятность, что А; = а;, и А; 4- 1 = а/, для фиксированных к, q, г и i ф i равна f{q,r,k)L\L\{PL-2L)\l{PL)\, где

«-)=(::;)c:nrv-v)("-v-/)

/ k-1 \/q + r-2\/PL-k-l\(2L-q-r\ \q + r-2)\ q-1 )\2L-q-r)\ L-q )

l<k<PL l<<),r<L

l<,,r<L

Вероятность того, что к = aiq и A: + 1 = gi(,+i), для фиксированных к, q и i равна

,<м./(™), - .<м)ч::;)(г;--;).

е .(м,е(г.)=(-"("-7)

l<fc<Fi l<,<i

l<q<L

[SICOMP 1 (1972), 161-166.]

3. Найдите минимум в соотношении (5) на интервале 2 < m < min(9, п).

4. (а) (0.000725(-/P + 1) + 0.014)L. (b) Замените "amn + l3n" в формуле (5) выражением "(0.000725(у+1) + 0,014)п" ["Натурные" эксперименты на компьютере показывают, что оптимальные деревья, определяемые этими соотношениями, весьма напоминают деревья, которые определяются теоремой К при а = 0.00145, /9 = 0.01545. Фактически существуют деревья, оптимальные для обоих рекуррентных соотношений, если 30 < п < 100. Предложенное выше изменение позволяет экономить около 10% времени слияния при условии, что п = 64 или 100, как в примере, который рассматривался в основном тексте раздела. Такой способ распределения памяти для буферов рассматривался еще в 1954 году X. Сьювордом, который показал, что 4-путевое слияние позволяет минимизировать время поиска.]

5. Пусть Ат{п) и Вт(п) - СТОИМОСТИ оптимальных наборов т деревьев, п листьев которых находятся соответственно на четных и нечетных уровнях. Тогда Ai{l) - О, 13i(l) = Q-f-/9; Ат{п) и Вт{п) определены, как в (4), при m > 2; Ai{n) = mmi<m<n{amn + j3n + Вт{п)), Bi(n) = mini<m<n(amn + (Зп + Ат{п)). Последние уравнения корректны несмотря на то, что Ai{n) и Bi{n) определяются друг через друга!

Ai{23) = i?i(23) = 268. [Интересно отметить, что п = 23 есть единственное значение, меньшее или равное 50, при котором никакое дерево с п листьями равной четности не является оптимальным в случае, когда нет ограничений на четность. Возможно, это единственное такое значение, когда а = /3.]

7. Для некоторого дерева рассмотрим величины adi + (3ei, ad„ + ficn, где dj - сумма степеней пути и ej - есть длина пути для j-ro листа. Для оптимального дерева с весами u;i < • < и;„ будет выполняться неравенство adi + /9ei > > Qd„ 4- /Зе„. Всегда можно переупорядочить индексы так, что adi +Ре\ - = adk Л-(Зек, где первые к листьев сливаются вместе.

9. Пусть d минимизирует (am + Р)/1пт. Рассуждение по индукции с использованием при этом выпуклости показывает, что Ai{n) > (Qd+/9)nbfr, n, причем равенство наступает при п = d*. Соответствующая верхняя оценка получается из полного d-арного дерева, поскольку в этом случае £)(г) = dE{T), Е{т) = tn + dr при п = d + (d - 1)г, О < г < d.

10. См. STOC 6 (1974), 216-229.

11. Из результата упр. 1.2.4-38 следует /т(п) = 3gn+2(n-3m), когда 2-3" < п/т < 3; /т(п) = 3qn + 4(п - Зт), когда З"* < п/т < 2 • 3. При этом /2(71) + 2п > /(п), причем равенство выполняется тогда и только тогда, когда 4 • 3" < " < 2 3; /з(п) 4- Зп = /("); /4(") + 4п > /(п), равенство выполняется тогда и только тогда, когда п = 4 3; и /т{п) + тп > f{n) для всех m > 5.

12. Используйте спецификации -, 1:1, 1:1:1, 1:1:1:1 ог 2:2, 2:3, 2:2:2, [n/SJ: [(" + l)/3j: [(n + 2)/3j, ...; при этом получаются деревья со всеми листьями на уровне g + 2, где 4 3« < п < 4 Зч+. (Если п = 4 3, формируется два таких дерева.)

14. Следующие спецификации деревьев были построены для случаев п = 1, 2, 3, ... посредством исчерпывающего просмотра всех разбиений п: -, 1:1, 1:1:1, 1:1:1:1, 1:1:1:1:1, 1:1:1:1:1:1, 1:1:1:1:3, 1:1:3:3, 3:3:3, 1:3:3:3, 3:4:4, 3:3:3:3, 3:3:3:4, 3:3:4:4, 3:4:4:4, 4:4:4:4, 5:6:6:6:12, 6:6:6:6:12, 6:6:6:6:13, .... (По-видимому, степени всегда < 6, но доказать это утверждение довольно сложно.)

15. Если первоначально в лифте находятся о человек, то при первой остановке оценка совместности возрастет не более чем на о -- 6. При следующей остановке оценка возрастет не более чем на Ы- m - о. Значит, после к остановок оценка возрастет не более чем на кЬ + (к-1)т.

16. И остановок: 123456 на этаже 2, 334466 на этаже 3, 444666 на этаже 4, 256666 на этаже 5, 466666 на этаже 6, 123445 на этаже 4, 11233S на этаже 5, 222333 на этаже 3, 122225 на этаже 2, 111555 на этаже 5, 111U1 на этаже 1. [Это минимум. Результат для 10 остановок при произвольной вместимости лифта может иметь следующий вид. Остановки на этажах: 2, 3, 4, 5, 6, рг, Рз, Р4, Рб, 1, где р2РзРлРв есть перестановка множества {2,3,4,5}. Такой график движения возможен только при 6 > 8. См. Martin Gardner, Knotted Doughnuts (New York: Freeman, 1986), Chapter 10.]

17. Существует no меньшей мере (Ьпу./Ы" конфигураций; число, которое может быть получено из некоторой заданной конфигурации после s остановок, не будет превышать ((и - 1)(""))что меньше, чем (п((Ь -I- m)e/bf), полученное в упр. 1.2.6-67. Следовательно," некоторая конфигурация требует

s(lnn -I- 6(1 -I- 1п(1 -I- т/6))) > 1п(Ьп)! - п1п6! > 6п1пЬп - 6п - п((6 -I-1) 1п6 - 6 --1),

как следует из упр. 1.2.5-24.

Замечание. Учитывая то, что 1/(х -I- у) > 5 min(l/x, l/y), когда х и у положительны, можно выразить эту нижнюю оценку в более приемлемой форме:

V V log(l-l-m/6)/y

Такой результат получен в работе А. Aggarwal, J. S. Vitter, CACJVf 31 (1988), 1116-1127, в которой также приводится соответствующая верхняя оценка:

log(l -I- m/6).

Расширение этого решения для нескольких дисков описано в работе М. Н. Nodine, J. S. Vitter, ACJVf Symposium on Parallel Algorithms and Architectures 5 (1993), 120-129.