JINZ IB n РфА?

2H ST2 FIRST 1 Й. FIRST Q.

Время выполнения равно (7n --t 6)u, но его можно сократить до (5n + constant) (см. упр. 1.1-3).

9. (а) Да. (Ь) Да, если рассматривается биологическое отцовство (или материнство), и нет, если допускается юридическое отцовство (или материнство) (когда, например, дочь может выйти замуж за своего отца, совсем как в песне "Гт Му Own Grampa"). (с) Нет (-1 Ч 1 и 1 -< -1). (d) Следует надеяться, что это так, ибо в противном случае возможно существование циклической цепочки доказательств, (е) 1 -< 3 и 3 -< 1. (f) Это утверждение не однозначно. Если предположить, что вызываемые у подпрограммы зависят от подпрограмм, которые вызвали у, то можно прийти к выводу о том, что условие транзитивности не всегда выполняется. (Например, общая подпрограмма ввода-вывода может вызывать различные процедуры обработки для каждого имеющегося устройства ввода-вывода, но не все эти процедуры обработки обычно необходимы для функционирования какой-то одной программы. Эта проблема часто является причиной ошибок во многих системах автоматического программирования.)

10. Для (i) существует три случая: х = у; х С у и у = z; х С у и у С z. А для (ii) -два случая: х = у; х ф у. Решение очевидно для каждого из них, как и для (iii).

11. "Перемножьте" приведенные ниже комбинации, которые в итоге дадут 52 решения: 13749(25 -Ь 52)86 -Ь (1379 + 1397 + 1937 + 9137)(4258 + 4528 -Ь 2458 -Ь 5428 + 2548 -Ь 5248 -Ь 2584 -Ь 5284)6 -Ь (1392 -Ь 1932 -ь 1923 -Ь 9123 + 9132 + 9213)7(458 -Ь 548 + 584)6.

12. Рассмотрим следующие примеры, (а) Расположим (в любом порядке) все множества из к элементов до всех множеств с к + 1 элементами, Q <к < п. (Ь) Представим подмножество последовательностью нулей и единиц, которая указывает, какой элемент находится в множестве. Это позволит установить соответствие между всеми подмножествами и целыми числами от О до 2" - 1, которые записаны в двоичной системе счисления. Порядок соответствия и является топологической последовательностью.

13. Дж. Ша и Д. И. Кляйтман {Discrete Math. 63 (1987), 271-278) доказали, что это количество не превышает Пк=о it) 0"° больше очевидной нижней границы Пк=о (fc) ~ 22 (п+0(1)) множитель 2 причем предполагается, что нижняя оценка ближе к истине.

14. Если ai 02 ... On и 61.62 - Ьп -две допустимые топологические сортировки, то предположим, что j - такое минимальное значение, при котором Uj ф bj, тогда Ofc = 6j и Oj = bm для некоторого к,т > j. Теперь bj 2? Oj, поскольку к > j, а aj 2? 6j, так как m > j. Следовательно, (iv) не выполняется. И наоборот, если существует только одна топологическая сортировка 0102... Оп, условие Uj :< a+i должно выполняться для некоторого 1 < J < п, так как в противном случае aj и Oj+i можно поменять местами. Исходя из вышесказанного и условия транзитивности, получим (iv).

Замечание. Приведенное ниже альтернативное доказательство подходит и к бесконечным множествам, (а) Каждое частичное упорядочение может быть расширено до линейного упорядочения. Например, для некоторых двух элементов с отношениями хо 2< уо и Уо Хо можно создать другое частичное упорядочение по правилу "х < у, если х < хо и уо у" Последнее упорядочение "включает" первое из двух упорядочений к хо <уо-Теперь для завершения доказательства применим обычным способом лемму Дорна или трансфинитную индукцию. (Ь) Очевидно, что линейное упорядочение не может быть расширено до любого другого линейного упорядочения, (с) Частичное упорядочение, которое имеет несравнимые элементы хо и уо, как и в (а), может быть расширено до двух

линейных упорядочений, в которых хо -< уо ч уо :< хо соответственно, а потому существует по крайней мере два линейных упорядочения.

15. Если 5 являет<;я конечным множеством, можно перечислить все отнощения а -< Ь данного частичного упорядочения. Удаляя последовательно по одному все отнощения, которые следуют из других, получим неприводимое множество. Задача теперь заключается в том, чтобы доказать единственность такого множества независимо от порядка удаления избыточных отношений. Если существует два таких неизбыточных множества U и V, в которых отношение а -< 6 присутствует в U, но не в V, то существует к + 1 отношений aci--cfcbB множестве V для некоторого А; > 1. Однако в таком случае из множества U можно вывести отношения а -< ci и ci Ч 6 без использования отношения а Ч 6 (так как Ь ci и ci о), поэтому отношение а -< b является избыточным в множестве U.

Такой результат не верен для бесконечных множеств 5. Существует не более одного неизбыточного множества отношений. Например, если множество S включает целые числа плюс элемент оо, а отношения тг-<тг--1ип-<оо определены для всех тг, то не существует ни одного неизбыточного множества отношений, которые характеризуют это частичное упорядочение.

16. Пусть Хр2 Хр„ -топологическая сортировка множества S. Тогда для строк и столбцов следует применить перестановку pip2 Рп-

17. Если к на шаге Т4 увеличивается от 1 до тг, то получим 1932745860. Если к на шаге Т4 уменьшается от тг до 1, как в программе Т, то получим 9123745860.

18. Они связывают элементы списка в рассортированном порядке: QLINK[0] -первый, QLINK [QLINK [0]] -второй и т. д.; QLINK [последний] = 0.

19. В некоторых случаях это может привести к ошибке. Например, если в очереди содержится только один элемент на шаге Т5, то модифицированный метод может установить F = О (опустошая таким образом очередь), но другие элементы могут быть помещены в очередь на шаге Т6. Следовательно, в предлагаемой модификации этого алгоритма на шаге Т6 необходимо включить проверку условия F = 0.

20. Действительно, стек можно было бы использовать следующим образом. (Шаг Т7 исключается.)

Т4. Установить Т ч- 0. Для 1 < А; < тг, если COUNT [fc] равно нулю, выполнить следующие действия: установить SLINK [fc] ч- Т, Т ч- fc. (SLINK [fc] = QLINK [fc] .)

T5. Вывести значение Т. Если Т = 0, перейти к шагу Т8, в противном случае установить N ч- Й - 1, Р ч- ТОР[Т] , Т i- SLINK [Т] .

Т6. То же, что и прежде, но перейти к шагу Т5, а не к шагу Т7. Когда COUNT[SUC(P)] уменьшится до нуля, установить SLINK [SUC(P)] <- Т и Т ч- SUC(P).

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

22. Для создания "отказоустойчивой" программы следует: (а) проверить, что О < тг < некоторое максимальное значение, (Ь) проверить, что для каждого отношения j < к выполняются условия О < j, fc < т1, (с) убедиться в том, что количество отношений не переполняет область пула.

23. В конце шага Т5 добавьте TOP[F] ч- Л. (Затем всегда следует устанавливать Т0Р[1], ..., ТОР[п] для указания на все еще неотмененные отношения.) На шаге Т8, если N > О,

печатать LOOP DETECTED IN INPUT: и установить QLINK Ш 0 для 1 < к < п. Кроме того, необходимо добавить следую14ие шаги.

Т9. Для 1 < А; < тг установить Р ТОР [И, TOP[fc] О и выполнить шаг Т10 (Это позволит установить указатель QLINK [j] на один из предшественников объекта J для каждого еще невыведенного j.) Затем перейти к шагу Т11.

Т10. Если Р Л, установить QLINK [SUC(P)] <- к,Р -(г- NEXT(P) и повторить этот шаг.

Т11. Найти к с QLINK Ш ф 0.

Т12. Установить ТОР[И <г- 1 и к <- QLINK [А;]. Теперь, если TOP[fc] = О, повторить этот шаг.

Т13. (Найдено начало петли.) Печатать значение к, установить TOP[fc] <-0, к <-QLINK [fc] и, если TOP[fc] = 1, повторить этот шаг.

Т14. Напечатать значение fc (начало и конец петли) и прекратить выполнение. (Замечание. Петля распечатывается в обратном порядке; чтобы распечатать ее в прямом порядке, алгоритм, подобный описанному в упр. 7, следует вставить между шагами Т12 и Т13.)

24. В код программы следует вставить следующие три новые строки.

08а PRINTER EQU 18 Ца ST6 N0

59а STZ Х.КТОР) ТОР[Р]<-Л.

Строки 74-75 следует заменить приведенными ниже строками.