► 7. [23] Предложите алгоритм "обращения" связанного линейного списка наподобие (1), т. е. такого изменения связей, чтобы его элементы расположились в обратном порядке. [Если, например, обратит!» список (1), то в нем указатель FIRST будет связан с узлом, содержащим элемент 5, а этОт узел будет связан с узлом, содержащим элемент 4, и т. д.] Допустим, что узлы имеют вид (3).

8. [24] Напишите программу для компьютера MIX, чтобы выполнить упр. 7, оптимизируя скорость ее выполнения.

9. [20] Какое из приведенных ниже отношений является частичным упорядочением некоторого множества 5? [Замечание. Если ниже определено отношение х -< у, то задача заключается в определении отношения х < у = {х -< у или х = у) -а выяснении, является ли -< частичным упорядочением.] (а) S = множество всех рахиональных чисел; х -< у означает, что х > у. (Ь) 5 = множество всех людей; х -< у означает, что х является предком у. (с) S = множество всех целых чисел; х :< у означает, что х кратно у (т. е. ж mod 2/ = 0). (d) S = множество всех доказанных в этой книге математических результатов; X -< у означает, что доказательство у зависит от истинности х. (е) S - множество всех положительных целых чисел; х < у означает, что х + у четно, (f) S = множество подпрограмм; х у означает, что х вызывает у, т. е. подпрограмма у может быть вызвана во время работы подпрограммы х, но рекурсия при этом не допускается.

10. [М21] При условии, что С является отношением, которое удовлетворяет свойствам (i) и (ii) частичного упорядочения, докажите, что отношение определенное правилом x < у тогда И ТОЛЬКО тогда, когда X = у или X с у", обладает всеми тремя свойствами частичного упорядочения.

► 11. [24] Результат топологической сортировки не всегда полностью определен, поскольку может существовать несколько способов упорядочения узлов и удовлетворения условий топологического порядка. Найдите все возможные способы топологического упорядочения узлов, показанных на рис. 6.

12. [М20] Существует 2" подмножеств множества п элементов, и эти подмножества частично упорядочены с помощью отношения включения множества. Предложите два способа упорядочения данных подмножеств в топологическом порядке.

13. [М48] Сколько существует способов упорядочения в топологическом порядке 2" подмножеств, описанных в упр. 12? (Дайте ответ в виде функции от п.)

14. [М21] Линейным упорядочением {linear ordering) или полным упорядочением {total ordering) множества S называется частичное упорядочение, которое удовлетворяет дополнительному условию "сравнимости".

(iv) Для любых двух элементов х, у множества S верно либо х < у, либо у < х.

Докажите непосредственно на основе этого определения, что топологическая сортировка может быть получена в единственном варианте тогда и только тогда, когда отношение < является линейным упорядочением. (Предположим, что множество S конечно.)

15. [М25] Покажите, что для любого частичного упорядочения конечного множества S существует единственное множество неприводимых отношений, которое характеризует это упорядочение, например таких, как отношения (18) и отношения, показанные на рис. 6. Верно ли это утверждение, если S является бесконечным множеством?

16. [М22] Для любого заданного частичного упорядочения множества S = {xi,... ,Хп} можно построить его матрицу инцидентности {incidence matrix) (oij), где Oij = 1, если Xi <Xj,w Uij = 0 в противном случае. Покажите, что существует такая перестановка строк и столбцов этой матрицы, при которой все ее элементы, расположенные ниже диагонали, будут равны нулю.

► 17. [21] Каким будет результат выполнения алгоритма Т для исходного набора отношений (18)?

18. [20] Какой смысл имеютачения QLINK [0] , QLINK [1] , ..., QLINK[n] после завершения алгоритма Т (если они вообще его имеют)?

19. [18] В алгоритме Т на шаге Т5 проверяется начальный элемент очереди, но этот элемент не удаляется из очереди до шага Т7. Что произойдет, если установить F ч- QLINK [F] в конце шага Т5, а не на шаге Т7?

* 20. [24] F, R и таблица QLINK используются в алгоритме Т для организации очереди с узлами, в которых поле COUNT уже стало равным нулю, но их отношения с наследниками еще не были удалены. Можно ли для этого вместо очереди использовать стек? Если можно, то сравните полученный алгоритм с алгоритмом Т.

21. [21] Сможет ли алгоритм Т правильно выполнять топологическую сортировку при многократном повторении отношения j -< к во входном потоке? Что произойдет, если входной поток будет содержать некоторое отношение в виде j -< j?

22. [23] В программе Т предполагается, что на входной магнитной ленте содержится корректная информгщия, но в программе общего назначения всегда следует предусматривать тщательную проверку входного потока для обнаружения описок и попыток "самоуничтожения" программы. Например, если одно из входных отношений является отрицательным для некоторого к, программа Т может ошибочно изменить одну из своих команд во время записи в X[fe]. Предложите такой способ изменения программы Т, который позволил бы избежать подобных сбоев.

* 23. [27] Если алгоритм топологической сортировки не может продолжить работу из-за обнаружения замкнутой петли во входном потоке (см. шаг Т8), вряд ли стоит останавливать его работу только для вывода сообщения "Возникла петля". Лучше распечатать одну из петель с отображением части входного потока, который привел к ошибке. Расширьте алгоритм Т так, чтобы в нем была предусмотрена дополнительная возможность распечатки петли в случае необходимости. [Указание. В этом разделе приводится доказательство существования петли, если N > О на шаге Т8, на основании которого можно создать данный алгоритм.]

24. [24] Реализуйте расширения алгоритма Т из упр. 23 в коде программы Т.

25. [47] Напишите максимально эффективный алгоритм для выполнения топологической сортировки для очень больших множеств 5, которые содержат гораздо больше узлов, чем может поместиться в памяти компьютера. Предположим, что операции ввода, вывода и временного хранения данных выполняются с помощью накопителя на магнитной ленте. [Указание. При обычной сортировке входных данных предполагается, что все отношения узла располагаются рядом. Что в таком случае можно было бы предпринять? В частности, необходимо предусмотреть самый неблагоприятный случай, когда задано сильно перемешанное линейное упорядочение. В упр. 24, во введении к главе 5, описывается вариант решения этой задачи с помощью O(logn) итераций.]

26. [29] {Распределение памяти для подпрограмм.) Допустим, что на магнитной ленте хранится основная библиотека подпрограмм в перемещаемом виде, который широко использовался в компьютерах 60-х годов. Процедуре загрузки нужно определить величину перемещения для каждой применяемой подпрограммы, чтобы для загрузки каждой необходимой программы потребовалось выполнить только один проход по всем данным. Проблема заключается в том, что для работы одних подпрограмм необходимо загрузить в память другие подпрограммы. При этом редко используемые подпрограммы (которые эбычно располагаются в конце ленты) могут вызывать часто используемые подпрограммы

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

Один из способов решения этой проблемы заключается в хранении "каталога ленты" в памяти. Процедура загрузки обладает правом доступа к двум таблицам.

а) Каталог ленты. Эта таблица состоит из узлов переменной длины следующего вида:

Здесь SPACE - количество слов памяти, необходимых для данной подпрограммы; LINK - ссылка на элемент каталога для подпрограммы, которая находится сразу за данной подпрограммой; SUB1, SUB2, SUBn (п > 0) - связи с элементами каталога для других подпрограмм, которые необходимы для работы данной подпрограммы; В = О для всех слов, за исключением последнего, В = - 1 для последнего слова в узле. Адрес элемента каталога для первой подпрограммы на магнитной ленте с библиотекой подпрограмм задается переменной связи FIRST.

b) Список подпрограмм, непосредственно указанных загружаемой программой. Он хранится в последовательных позициях Х[1], Х[2], X[N], где N > О - переменная, которая известна процедуре загрузки. Каждый элемент этого списка является связью с элементом каталога для соответствующей подпрограммы.

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

В качестве небольшого примера рассмотрим следующую конфигурацию.

Каталог ленты

Необходимые подпрограммы

Каталог ленты в данном случае показывает, что в указанном порядке на ленте хранятся подпрограммы 1002, 1010, 1006, 1000, 1005, 1003 и 1007. Подпрограмма 1007 занимает 200 позиций, и при ее работе предполагается использовать подпрограммы 1005, 1002 и 1006; и т. д. Для загрузки этой подпрограммы потребуются подпрограммы 1003 и 1010, которые будут размещены в ячейках по адресам > 2400. В свою очередь, для этих подпрограмм потребуется загрузить также подпрограммы 1000, 1006 и 1002.

Блок распределения памяти подпрограммы должен изменить таблицу X так, чтобы каждый элемент Х[1], Х[2] ,... принял следующую форму: