Д. Кнут - Искусство программирования том 1 (1119450), страница 74
Текст из файла (страница 74)
ГЬП, «. 1 Переустановить указатель буфера вывода. В+- О. Проверить значение СООИТ[Ь) . Не равно ли оно нулю? 011ИК[В) +- й. В+- Ь. Р+- ЦАХИК [ОБ Т5. Вые начала оче Сохранить Р в области буфера. Не равно ли нулю значение Р? Увеличить указатель буфера. Проверить, заполнен ли буфер.
Если дополнен, переписать блок на ленту. Переустановить указатель буфера. И+- И вЂ” 1. Р +- ТОР(РК Тб. У аненне отношений. г14 +- БОС(Р) СОСИ? ЬН4) — 1 -+ СОВЕТ [г14Е Достигнут ли нуль? Если достигнут, установить ЦХТИК[М) +- г14. М+- г14. Р +- ИЕХТ(Р).
Если Р Р' й, повторить. Т7. У аленне нз оче н. Р +- 011ИК(Р), перейти к шагу Т5. У8. К Вывести последний блок и перемотать ленту. Останов с выводом значения И на консоль. Начало области таблицы. $ Анализ алгоритма Т достаточно просто можно выполнить с помощью закона Кирхгофа. Используя этот закон, время выполнения можно приблизительно оценить с помощью формулы с1 т+ сзи, где т — количество введенных отношений, и— количество объектов, а с1 и сз — константы.
Более быстрый алгоритм для решения этой задачи просто невозможно себе представить! Что касается программы Т, то для нее можно получить точную оценку времени выполнения, используя следующие параметры; а = количество объектов, не имеющих предшественника, Ь = количество блоков на входе, = Ит+ 2)/501, и с = количество блоков на выходе = ~(и+1)/1001. Если не принимать во внимание продолжительность операций ввода-вывода, общее время выполнения в таком случае будет равно всего лишь (52т+ 24и+ 7Ь+ 2с+16) и. Метод топологической сортировки, аналогичный алгоритму Т (но без важной особенности связанных списков), впервые был опубликован А.
Б. Каном (А. В. Кайн, САСМ 5 (1962), 558-562), а доказательство того„что топологическая сортировка частичного упорядочения всегда возможна, было впервые опубликовано Э. Шпильрайном (Е. Вхрйга)п, Ешь)атепса МасЬетаНса 16 (1930), 386 — 389). Он доказал этот результат как для бесконечных, так и для конечных множеств, причем упомянул, что он уже был известен некоторым из его коллег. Несмотря на столь высокую эффективность алгоритма Т в разделе 7.4.1 будет рассмотрен еще более эффективный алгоритм топологической сортировки.
УПРАЖНЕНИЯ 1. [10] В операции (9) для "выталкивания" элемента из стека предусмотрена возможность обработки события недостатка (ОИОЕЕРЧ.Ои). Почему тогда в операции (8) для "проталкивания" элемента в стек не предусмотрена возможность обработки события переполнения (ОЧЕИН.ОИ)? 2. [88] Напишите подпрограмму "общего назначения" для компьютера И1Х, которая выполняла бы операцию вставки (10).
Эта подпрограмма должна удовлетворять следующим требованиям (так же, как и в разделе 1.4.1). Условия вызова: ЛИР 1ИБЕИТ Переход к подпрограмме. ИОР Т Адрес указательной переменной. Условия ввода: гА = информация, которая должна быть введена в поле 1ИРО нового узла. Условия вывода: Стек, указатель которого является переменной связи Т и имеет сверху новый узел; г11 = Т; г12, г13 изменяются. 3. [82] Напишите подпрограмму "общего назначения" для компьютера И1Х, которая выполняла бы операцию удаления (11).
Эта подпрограмма должна удовлетворять следующим требованиям. Условия вызова: Л(Р ОЕ1.ЕТЕ Переход к подпрограмме. ИОР Т Адрес указательной переменной. ЛР ОИРЕЕР1.ОИ Первый выход, если происходит событие ОИОЕИН.ОИ. Условия ввода: Не определены. Условия вывода: Если стек, указателем которого является переменная связи Т, пуст, срабатывает первый выход, в противном случае удаляется верхний узел стека и выход переносится к третьей позиции после ЛИР ОЕ1.ЕТЕ. В последнем случае гП = Т и в гА находится содержимое поля 1ИРО удаленного узла. В любом случае г12 и г13 используются атой подпрограммой. 4. [вв] Программа (10) основана на операции Р ~м АРАП., определенной действиями (6).
Покажите, квк можно создать такую подпрограмму обработки событий переполнения (ОТЕИРьОИ), чтобы без каких-либо изменений в коде (10) в операции Р ~м АРА11 использовалось ограничение ЕЕОИ1И, указанное в (7), В общем случае эта подпрограмма не должна изменять содержимое регистров, за исключением регистра гЛ и, возможно, индикатора сравнения.
Она должна иметь выход в позиции гЛ вЂ” 2 вместо обычной позиции гЛ. б [24] Операции (14) и (17) эквивалентны операциям с очередью. Покажите, как можно было бы определить операцию "вставка элемента с начала очереди" для получения набора всех действий, выполняемых для дека с ограниченным вводом. Как в таком случае определить операцию "удаление с конца" (для получения дека общего типа)? 6.
[21] В операции (14) было установлено ~.1ИХ(Р) е- й, тогда как следующая операция вставки элемента в конце очереди изменит значение того же самого поля связи. Покажите, как можно было бы избежать установки 1.1ИК(Р) в (14) при внесении изменений в проверку условия Р = й в (17). ° 7. [дд] Предложите алгоритм "обращения" связанного линейного списка наподобие (1), т, е, такого изменения связей, чтобы его элементы расположились в обратном порядке.
[Если, например, обратить список (1), то в нем указатель 8188? будет связан с узлом, содержащим элемент б, а этот узел будет связан с узлом, содержащим элемент 4, и т. д.] Допустим, что узлы имеют вид (3). 8. [22] Напишите программу для компьютера 611, чтобы выполнить упр. 7, оптимизируя скорость ее выполнения. 9. [ЯО] Какое из приведенных ниже отношений является частичным упорядочением некоторого множества 5? [Замечание. Если ниже определено отношение х с у, то задача заключается в определении отношения х -с у ы (х -с у или х = у) н выяснении, является ли ~ частичным упорядочением.] (а) 5 = множество всех рациональных чисел; х с у означает, что х > у.
(Ь) 5 = множество всех людей; х с у означает, что х является предком у. (с) 5 = множество всех целых чисел; х ч у означает, что х кратно у (т. е. х шод у = О). (Й) 5 = множество всех доказанных в этой книге математических результатов; х м у означает, что доказательство у зависит от истинности х. (е) 5 = множество всех положительных целых чисел; х ч у означает, что х+ у четно. (Г) 5 = множество подпрограмм: х м у означает, что х вызывает у, т, е. подпрограмма у может быть вызвана во время работы подпрограммы х, но рекурсия при этом не допускается. 10. [М21] При условии, что С является отношением, которое удовлетворяет свойствам (1) и (й) частичного упорядочения, докажите, что отношение ч, определенное правилом ох -ч у тогда и только тогда, когда х = у нли х С у", обладает всеми тремя свойствами частичного упорядочения.
э 11. [й(] Результат топологической сортировки не всегда полностью определен, поскольку может существовать несколько способов упорядочения узлов и удовлетворения условий топологического порядка. Найдите все возможные способы топологического упорядочения узлов, показанных на рис. 6. 12. [МЯО] Существует 2" подмножеств множества п элементов, и эти подмножества частично упорядочены с помощью отношения включения множества. Предложите два способа упорядочения данных подмножеств в типологическом порядке. 13.
[Мдд] Сколько существует способов упорядочения в топологнческом порядке 2" подмножеств, описанных в упр, 12? (Дайте ответ в виде функции от и.) 14. [М21] Линейным упорядочением (йпеаг оп1сгчпд) или полним упорядочением (1оФа! огдегЫд) множества 5 называется частичное упорядочение, которое удовлетворяет дополнительному условию "сравнимости".
(1ч) Для любых двух элементов х, у множества 5 верно либо х ~ у, либо у -с х. Дохажите непосредственно на основе этого определения, что топологическая сортировка может быть получена в единственном варианте тогда и только тогда, когда отношение ч является линейным упорядочением. (Предположим, что множество 5 конечно.) 16. [Мдд] Покажите, что для любого частичного упорядочения конечного множества 5 существует единственное множество неприводимых отношений, которое характеризует это упорядочение, например таких, как отношения (18) и отношения, показанные на рнс.
6. Верно ли это утверждение, если 5 является бесконечным множеством? 16. [МЯУ] Для любого заданного частичного упорядочения множества 5 = (хм...,х ) можно построить его матрицу инцидентности (гпсЫепсе та1гЫ) (аи), где ао = 1, если х, -с х„и аи = 0 в противном случае, Покажите, что существует такая перестановка строк и столбцов этой матрицы, при которой все ее элементы, расположенные ниже диагонали, будут равны нулю.
ь 17. [И] Каким будет результат выполнения алгоритма Т для исходного набора отношений (18)? 18. [80] Какой смысл нмеютэшачения Ц1.1ИК [0], Ц1.1ИК [1],..., 01.1ИК Ы после завершения алгоритма Т (если они вообще его имеют)? 19. [18] В алгоритме Т на шаге Т5 проверяется начальный элемент очереди, но этот элемент не удаляется из очереди до шага Т7. Что произойдет, если установить Г +- 01.1ИК [Р) в конце шага Т5, а не на шаге Т7? ь 20. ]34] Р, К и таблица 011ИК используются в алгоритме Т для организации очереди с узлами, в которых поле СООИТ уже стало равным нулю, но их отношения с наследниками еще не были удалены. Можно ли для этого вместо очереди использовать стек? Если можно, то сравните полученный алгоритм с алгоритмом Т.
21. [81] Сможет ли алгоритм Т правильно выполнять топологнческую сортировку при многократном повторении отношения У с 5 во входном потоке? Что произойдет, если входной поток будет содержать некоторое отношение в виде у -с у? 22. [ЯЯ] В программе Т предполагается, что на входной магнитной ленте содержится корректная информация, но в программе общего назначения всегда следует предусматривать тщательную проверку входного потока для обнаружения описок и попыток "самоуничтожении" программы. Например, если одно из входных отношений является отрицательным для некоторого к, программа Т может ошибочно изменить одну из своих команд во время записи в 1[кП Предложите такой способ изменения программы Т, который позволил бы избежать подобных сбоев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
