с) Найдите менее строгое ограничение, чем предложенное в упр. 3 ограничение для поля 7:7, которое в никоторой степени позволило бы устранить трудности, описанные в упр. 4, (с), а также не требовало дорогостоящего аппаратного обеспечения.

6. [10] Определите, какая из приведенных ниже последовательностей действий может вызвать переполнение или недостаток с начальной конфигурацией памяти, показанной на рис. 4:

(a)Ii; (b)l2; (с) I3; (d) I4I4I4I4I4; (е) D2D2I2I2I2.

7. [12] На шаге G4 алгоритма G предусмотрена операция деления на INC. Может ли значение INC быть равным нулю когда-либо в этом месте данного алгоритма?

► 8. [26] Объясните, как можно было бы модифицировать.коды (9) и (10), а также алгоритмы переупаковки в случае, когда один или несколько списков имеют структуру очереди с циркулярным порядком обработки, аналогично правилам (6, а) и (7, а).

► 9. [М27] Используя математическую модель, описанную почти в самом конце раздела, докажите, что среднее количество перемещений определяется формулой (14). (Обратите внимание, что для выполнения последовательности действий 1, 1, 4, 2, 3, 1, 2, 4, 2, 1 потребуется 04-0-Ь0-Ы-Ы4-3--2-Ь0-ЬЗ-Ь6=16 перемещений.)

10. [Мй.?] Изменим математическую модель в упр. 9, предположив, что таблицы могут иметь разные размеры. Иначе говоря, предположим, что pk-это вероятность того, что Uj = к для 1 < J < тп, 1 < < п. Таким образом, pi + Р2 + + Рп = 1, а в предыдущем упражнении рассматривался частный случай, когда рк = 1/п для всех к. Определите среднее количество перемещений, т. е. укажите, какой будет формула (14) в этом более общем случае. Относительный порядок п списков можно изменить так, что более длинные списки будут располагаться правее (или левее). При каком относительном порядке п списков среднее количество перемещений будет минимальным для данного набора вероятностей Pi, Р2, . • •, Рп?

11. [МЗО] Расширим предложенную в упр. 9 задачу следующим условием: для выполнения первых t операций вставки в стек не требуется никаких перемещений, тогда как все последующие операции вставки осуществляются так же, как и прежде. Следовательно, если t = 2, для приведенной в упр. 9 последовательности потребуется выполнить 04-0-ЬО-f-0-l-0-f3-f0-f-0-l-3-l-6 = 12 перемещений. Каким будет среднее количество перемещений при таком дополнительном условии? [Это условие приблизительно моделирует поведение алгоритма при наличии в исходном состоянии t доступных свободных мест в каждом стеке.]

12. [M;8i?] Выгоду от использования в памяти двух таблиц, которые растут по направлению друг к другу, а не занимают отдельные независимые участки памяти, можно в определенной степени оценить количественно. Для этого сначала рассмотрим модель, использованную в упр. 9 с п = 2. Далее предположим, что в каждой из 2" равновероятных последовательностей ai,a2, . ,ат содержится к\ единиц и к2 двоек. (Здесь к\ и к2 соответствуют размерам двух таблиц после полного заполнения памяти. При смежном расположении таблиц данный алгоритм можно с тем же результатом применить к т = ki+k2 ячейкам вместо 2 max (fci, 2) ячеек при раздельном расположении таблиц.)

Каким будет среднее значение max (1,2)?

13. [НМ42] Величина max(fci, /гг) из упр. 12 будет даже больше, если более крупные флуктуации таблиц будут вызваны не только случайными операциями удаления, но и случайными операциями вставки. Предположим, что прежняя модель изменена таким o6pa30Mj что с вероятностью р значение последовательности Uj интерпретируется, как удаление, а не как вставка, а весь процесс продолжается до тех пор, пока к\ + к2 (общее количество используемых ячеек таблицы) не станет равным т. Причем операция удаления из пустого списка не дает никакого результата.

Например, если т - 4, можно показать, что будет получено следующее распределение

вероятностей по окончании всего процесса:

(кикг) (0,4) (1,3) (2,2) (3,1) (4,0)

1 1 6-6р+2р 1 1

с вероятностью -, -, jg j2p+4p2-

Таким образом, при увеличении р увеличивается и разница между ki и Лг. Нетрудно показать, что в пределе при стремлении р к единице распределение ki становится практически равномерным, а предельное значение max(fci, г) будет точно равно Im-l-j[для четныхт]. Такое поведение существенно отличается от рассмотренного в предыдущем примере (когда р = 0). Однако это не так уж и важно, поскольку при приближении р к единице время, необходимое для завершения процесса, будет быстро стремиться к бесконечности. Сформулированная в этом упражнении задача заключается в исследовании зависимости тах(к\,к2) от р и m и определении асимптотических формул для заданных значений р (например, р = ), если т стремится к бесконечности. Особый интерес представляет случай, когда р = .

14. [НМ43] Обобщите результат упр. 12 для произвольного п > 2, показав, что для фиксированного п и стремящегося к бесконечности т величина

т\ max(fci, 2,..., fc„)

, Г". kik2\...knl

имеет асимптотический вид т/п + с„у/гп + 0(1). Определите константы сг, Сз, С4 и cs.

15. [40] Используя метод Монте-Карло, промоделируйте работу алгоритма G для разных распределений вставок и удалений. Какой вывод об эффективности алгоритма G можно сделать на основании этих опытов? Сравните его производительность с производительностью другого алгоритма, в котором узлы сдвигаются вверх или вниз по одному.

16. [20] В этом разделе описан способ более эффективного использования общей области памяти благодаря такому расположению двух стеков в памяти, при котором они могут расти навстречу друг другу. Можно ли так расположить две очереди или стек и очередь, чтобы добиться такой же эффективности при использовании общей области памяти?

17. [30] Если а - это произвольная последовательность вставок и удалений типа (12), пусть so(ct) - количество переполнений стека, которые возникают после применения простого способа, показанного на рис. 4, к этой последовательности а с начальными условиями наподобие (11), а Si(cr)-соответствующее количество переполнений по отношению к другим начальным условиям наподобие (13). Докажите, что so(a) < Si(a) 4- Loo - Lo.

► 18. [M50] Покажите, что общее время выполнения любой последовательности m вставок и/или удалений согласно алгоритмам G и R имеет порядок 0{т + njj а*/(1 - а*)), где ак -доля памяти, занятая во время последней переупаковки памяти до к-к операции. ак =0 до первой переупаковки памяти. (Следовательно, если память никогда не заполняется более чем на 90%, для выполнения каждой операции потребуется не больше 0{п) тактов независимо от общего размера памяти.) Предполагается, что Loo - Lo > n.

► 19. [16] (Нуль-индексирование.) Опытным программистам известно, что в общем случае для индексирования элементов линейного списка лучше использовать форму X [0], X [1], ..., X [п - 1] вместо традиционной формы X [1], X [2] , ..., X [п]. Тогда, например, базовый адрес Lo в (1) будет указывать на наименьшую ячейку массива.

Измените методы вставки и удаления (2, а), (3, а), (6, а) и (7, а) для стеков и очередей так, чтобы они соответствовали этому соглашению. Иначе говоря, измените их так, чтобы все элементы списка находились в массиве Х[0], Х[1], ..., Х[М - 1], а не в массиве Х[1], Х[2], Х[М].

2.2.3. Связанное распределение

Вместо того чтобы хранить линейный список в последовательных ячейках памяти, можно использовать бояее гибкую схему, в соответствии с которой каждый узел содержит связь со следующим узлом списка.

Последовательное распределение

Связанное распределение

Здесь А, В, С, D и Е - это произвольные ячейки памяти, а А - пустая связь (см. раздел 2.1). В программе с такой таблицей с последовательным распределением элементов для обозначения ее длины (5 элементов) потребуется либо дополнительная переменная или константа, либо Специальный код в последнем, 5тМ, элементе или в следующей за ним ячейке памяти. В программе со связанным распределением необходимо использовать переменную или константу связи, которая будет указывать на адрес А, причем все другие элементы списка могут быть найдены с помощью этого адреса.

Как упоминалось выше, в разделе 2.1, связи часто схематически изображают в виде стрелок, так как их действительное расположение в памяти обычно не имеет никакого значения. В таком случае описанная выше таблица при связанном распределении памяти будет выглядеть следующим образом.

FIRST

Элемент 1

Элемент 2

> Элемент 3 *- Элемент 4 ->

Элемент 5

Здесь FIRST - это переменная связи, которая указывает на первый узел списка.

Сравнив два основных типа хранилищ, можно сделать несколько очевидных выводов.

1) При организации связанного распределения в памяти потребуется выделить дополнительное пространство для размещения связей. В некоторых ситуациях этот фактор может оказаться доминирующим. Но часто бывает так, что хранимая в узле информация все равно не занимает все слово целиком, поэтому место для связи всегда найдется. Кроме того, во многих случаях несколько элементов комбинируются в одном узле, а потому связь может использоваться сразу для нескольких элементов данных (см. упр. 2.5-2). Однако важнее то, что с помощью связанного распределения памяти выигрыш можно получить неявно за счет частичного перекрытия таблиц, совместно использующих некоторые области памяти. Часто последовательное распределение не так рационально, как связанное, поскольку для его эффективной, работы необходимо очень большое количество дополнительных вакантных ячеек памяти. Так, в конце предыдущего раздела уже объяснялось, почему подобные системы становятся крайне неэффективными при плотном заполнении памяти.