AOP_Tom1 (1021736), страница 76
Текст из файла (страница 76)
Установить СООИТ[/с] +- О и ТОР[?с] с — Л для 0 < А < п. (Учестьь что 011ИХ [О] с- О на шаге Т4.) Свободная область начинается после Х [и]. Приготовиться к чтению первой пары (1, )с). Т2. Сле ю ее отношение. Верно ли, что 1 > О? Входной поток исчерпан? Метка конца замечена; считать другой блок с ленты, дождаться завершения. Переустановить указатель буфера.
ТВ. Зались отношения. СООМТ [)с] +1 ° СООИТ [А]. АТА11 с- АЧА11 + 1. ТОР [1] -+ ИЕХТ(Р). (с -+ ЯОС(Р). Р «ТОР[1]. Увеличить указатель буфера. и > й > 1. и+1 и+1 и с — 1 с — 1 тл и 1 1 1 59 4Н 46 41 49 49 4Н 44 45 46 47 46 49 ь ФАЗА 50 51 ЯН 59 55 54 55 56 57 56 59 60 61 бН 69 65 64 65 66 67 66 69 70 ?Н 71 79 8Н 75 74 75 Х (ТАРЕ[И) 1ОО ,4(саоит) +з ,З(ОПИК) ,4 в овкн (011ИК) (ТАРеоот) ОРРЕЕ+ 1ОО, б +з ОРРЕК (ТАРЕООТ) 100 ,1(ТОР) ,2(ЯОС) .4(СООМТ) ,4(СОРИТ) 3 ,3(011ИК) ,4 ,2(ИЕХТ) ,1 ИН.1ИК) РЕЕ(ТАРЕООТ) (ТАРЕООТ) РЯОНТ 10С 0 ЕИТ4 О ЕИТЯ- ЕИТЗ О РРА Х ЗАР ЯТ4 Х ЕИТЗ О РЕС4 1 14Р 4 СОРТИР ь01 Х 1803 ь ЯТ1 В 112 8 1ИСЯ 1 ЗЯИ ООТ В ЕИТЯ- РЕСЯ 1 102 Х 122 ? 104 О 1РА Х РЕСА 1 ЯТА Х ЗАР л+ ЯТ4 Х ЕИТЗ О 102 О 12Р бВ 101 ЗНР ЯВ ООТ ВУР 10С О НЕТ О ЕМР ТО Перемотать ленту ввода.
Гьл~дх .. Переустановить указатель буфера вывода. К+- О. Проверить значение СОРИТ [А) . Не равно лн оно нулю? ЦПИК[Е) с — А. Е + — А. Р +- 01[ИХ [О) . Т5. Выв начала оче е Сохранить Р в области буфера. Не равно ли нулю значение Р? Увеличить указатель буфера. Проверить, заполнен ли буфер. Если дополнен, переписать блок на ленту. Переустановить указатель буфера, И ~- И вЂ” 1. Р +- ТОР [Р) . Тб. У аление отношений. г14 <- ЯОС(Р).
СООМТ [Н4) — 1 -+ СООМТ ЕН4) . Достигнут ли нуль? Если достигнут, установить Ц11ИК [Е] +- г14. Е < — г14. Р +- ИЕХТ(Р). Если Р )А Л, повторить. Т?. У алевие вз оче е и. Р < — 011ИК(Р), перейти к шагу Тз. Х8. К Вывести последний блок н перемотать ленту. Останов с выводом значения М на консоль. Начало области таблицы. 6 Анализ алгоритма Т достаточно просто можно выполнить с помощью закона Кирхгофа.
Используя этот закон, время выполнения можно приблизительно оценить с помощью формулы с1 т+ сзп, где т — количество введенных отношений, ив количество объектов, а с1 и сз — константы. Более быстрый алгоритм для решения этой задачи просто невозможно себе представить! Что касается программы Т, то для нее можно получить точную оценку времени выполнения, используя следующие параметры; а = количество объектов, не имеющих предшественника, 6 = количество блоков на входе, = Ит+ 2)/50), и с = количество блоков на выходе = ((и + 1)/100) . Если не принимать во внимание продолжительность операций ввода-вывода, общее время выполнения в таком случае будет равно всего лишь (32т+ 24п+?6+ 2с+1б) и.
Метод топологической сортировки, аналогичный алгоритму Т (но без важной особенности связанных списков), впервые был опубликован А. Б. Каном (А. В. Кайн, САСМ 5 (1962), 558-562), а доказательство того, что топологическая сортировка частичного упорядочения всегда возможна, было впервые опубликовано Э. Шпильрайном (Е. 9яр!1га]п, 1"пцс(аэпепга МагпепаНса 16 (1930), 386 — 389). Он доказал этот результат как для бесконечных, так и для конечных множеств, причем упомянул, что он уже был известен некоторым из его коллег. Несмотря на столь высокую эффективность алгоритма Т в разделе 7.4.1 будет рассмотрен еще более эффективный алгоритм топологической сортировки. УПРАЖНЕНИЯ 1. [10] В операции (9) для "выталкивания" элемента из стека предусмотрена возмож- ность обработки события недостатка (ОМОЕМР?.ОН).
Почему тогда в операции (8) для "про- талкивания" элемента в стек не предусмотрена возможность обработки события перепол- нения (ОТМЕРОМ)? 2. [22] Напишите подпрограмму "общего назначения" для компьютера М1Х, которая вы- полняла бы операцию вставки (10). Эта подпрограмма должна удовлетворять следующим требованиям (так же, как и в разделе 1.4.1). Условия вызова: ЛИР 1МЕЕЕТ Переход к подпрограмме. ИОР Т Адрес указательной переменной, Условия ввода: гА = информация, которая должна быть введена в поле 1МРО нового узла. Условия вывода: Стек, указатель которого является переменной связи Т и имеет сверху новый узел; г11 = Т; г12, г13 изменяются. 3.
[22] Напишите подпрограмму "общего назначения" для компьютера И1Х, которая вы- полняла бы операцию удаления (11). Эта подпрограмма должна удовлетворять следующим требованиям. Условия вызова: ЛИР ОЕЕЕТЕ Переход к подпрограмме. ИОР Т Адрес указательной переменной. ЛИР ОМОЕКР1.00 Первый выход, если происходит событие ОМОЕКРЧ.ОМ. Условия ввода: Не определены. Условия вывода: Если стек, указателем которого является переменная связи Т,пуст, срабатывает первый выход, в противном случае удаляется верхний узел стека и выход переносится к третьей позиции после ЛИР ОЕ|ЕТЕ. В последнем случае гП = Т и в гА нахолится содержимое поля 1ИРО удаленного узла. В любом случае г12 н г13 используются этой подпрограммой. 4.
[22] Программа (10) основана на операции Р ~м АЧА11, определенной действиями (6). Покажите, как можно создать такую подпрограмму обработки событий переполнения (ОТЕЕР1.0М), чтобы без каких-либо изменений в коде (10) в операции Р ~ АРАП. использо- валось ограничение БЕЦИ1М, указанное в (7). В общем случае эта подпрограмма не должна изменять содержимое регистров, за исключением регистра гЛ и, возможно, индикатора сравнения. Она должна иметь выход в позиции гЛ вЂ” 2 вместо обычной позиции гЛ. 5. [24] Операции (14) н (17) эквивалентны операциям с очередью. Покажите, как можно было бы определить операцию "вставка элемента с начала очереди" для получения набо- ра всех действий, выполняемых для дека с ограниченным вводом.
Как в таком случае определить операцию "удаление с конца" (для получения дека общего типа)? 6. [21] В операции (14) было установлено 1.1ИК(Р) +- й, тогда как следующая операция вставки элемента в конце очереди изменит значение того же самого поля связи. Покажите, ках можно было бы избежать установки 01ИК(Р) в (14) при внесении изменений в проверку условия Р = Л в (17). 7. [22] Предложите алгоритм "обращения" связанного линейного списка наподобие (1), т. е. такого изменения связей, чтобы его элементы расположились в обратном порядке. [Если, например, обратить, список (1), то в нем указатель Г1687 будет связан с узлом, содержащим элемент 5, а этот узел будет связан с узлом, содержащим элемент 4, и т.
д.] Допустим, что узлы имеют вид (3). 8. [24] Напишите программу для компьютера М11, чтобы выполнить упр. 7, оптимизируя скорость ее выполнения. 9. [20] Какое из приведенных ниже отношений является частичным упорядочением некоторого множества 5? [Заме ~ание. Если ниже определено отношение х к у, то задача заключается в определении отношения х Е у щ (х .ч у нли х = у) и выяснении, является ли Е частичным упорядочением.) (а) 5 = множество всех раг(напальных чисел; х Е у означает, что х > у.
(Ь) Я = множество всех людей; х Ч у означает, что х является предком у, (с) 5 = множество всех целых чисел; х Е у означает, что х кратно у (т. е. х щоб у = 0). (е!) Я = множество всех доказанных в этой книге математических результатов; х -Е у означает, что доказательство у зависит от истинности х. (е) Я = множество всех положительных целых чисел; х ч у означает, что х+ у четно. (() 5 = множество подпрограмм: х -е у означает, что х вызывает у, т. е.
подпрограмма у может быть вызвана во время работы подпрограммы х, но рекурсия при этом не допускается, 10. [М21] При условии, что С является отношением, которое удовлетворяет свойствам (!) и (й) частичного упорядочения, докажите, что отношение -<, определенное правилом "х ! у тогда и только тогда, когда х = у или х с у", обладает всеми тремя свойствами частичного упорядочения. ° 11. [24] Результат топологической сортировки не всегда полностью определен, поскольку может существовать несколько способов упорядочения узлов и удовлетворения условий топологического порядка. Найдите все возможные способы топологического упорядочения узлов, показанных на рис.
6. 12. [М20] Существует 2 подмножеств множества п элементов, и эти подмножества частично упорядочены с помощью отношения включения множества. Предложите два способа упорядочения данных подмножеств в топологическом порядке. 13. [Мдд] Сколько существует способов упорядочения в топологическом порядке 2" подмножеств, описанных в упр. 12? (Дайте ответ в виде функции от и.) 14. [М21] Линейным упорядочением (1ъпеаг оп!ег(пд) или полным упорядочением (1о!а1 оп(ег!пд) множества 5 называется частичное упорядочение, которое удовлетворяет дополнительному условию "сраанимости".
(и ) Для любых двух элементов х, у множества Я верно либо х -< у, либо у ч х. Докажите непосредственно на основе этого определения, что топологическая сортировка может быть получена в единственном варианте тогда и только тогда, когда отношение ч является линейным упорядочением. (Предположим, что множество 5 конечно.) 16. [М25] Покажите, что для любого частичного упорядочения конечного множества Я существует единственное множество неприводимых отношений, которое характеризует это упорядочение, например таких, как отношения (18) и отношения, показанные на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
