Tl. Инициализация

Т2. Следующее отношение

Больше нет

ТЗ. Запись отношения

Т4. Поиск нулей

Т5. Вывод начала очереди

Пусто

Т8, Конец процесса

Т6. Удаление отношений

Больше нет

Т7. Удаление из очереди

Рис. 9. Топологическая сортировка.

Анализ алгоритма Т достаточно просто можно выполнить с помощью закона Кирхгофа. Используя этот закон, время выполнения можно приблизительно оценить с помощью формулы Cim + C2n, где т - количество введенных отношений, п - количество объектов, а ci и сз-константы. Более быстрый алгоритм для решения этой задачи просто невозможно себе представить! Что касается программы Т, то для нее можно получить точную оценку времени выполнения, используя следующие параметры: о = количество объектов, не имеющих предшественника, b = количество блоков на входе, = \{тп -Ь 2)/50], и с = количество блоков на выходе = \{п + 1)/100]. Если не принимать во внимание продолжительность операций ввода-вывода, общее время выполнения в таком случае будет равно всего лишь (32тЧ-24п--7Ы-2с-- 16)и.

Метод топологической сортировки, аналогичный алгоритму Т (но без важной особенности связанных списков), впервые был опубликован А. Б. Каном (А. В. Kahn,

САСМ 5 (1962), 558-562), а доказательство того, что топологическая сортировка частичного упорядочения всегда возможна, было впервые опубликовано Э. Шпильрай-ном (Е. Szpilrajn, Fanjdamenta Mathematica 16 (1930), 386-389). Он доказал этот результат как для бесконечных, так и для конечных множеств, причем упомянул, что он уже был известен некоторым из его коллег.

Несмотря на столь высокую эффективность алгоритма Т в разделе 7.4.1 будет рассмотрен еще более эффективный алгоритм топологической сортировки.

УПРАЖНЕНИЯ

► 1. [10] в операции (9) для "выталкивания" элемента из стека предусмотрена возможность обработки события недостатка (UNDERFLOW). Почему тогда в операции (8) для "проталкивания" элемента в стек не предусмотрена возможность обработки события переполнения (OVERFLOW)?

2. [22] Напишите подпрограмму "общего назначения" для компьютера MIX, которая выполняла бы операцию вставки (10). Эта подпрограмма должна удовлетворять следующим требованиям (так же, как и в разделе 1.4.1).

Условия вызова: JMP INSERT Переход к подпрограмме.

NOP Т Адрес указательной переменной.

Условия ввода: гА = информация, которая должна быть введена в поле INFO нового

узла.

Условия вывода: Стек, указатель которого является переменной связи Т и имеет сверху новый узел; гП := Т; г12, г13 изменяются.

3. [22] Напишите подпрограмму "общего назначения" для компьютера MIX, которая выполняла бы операцию удаления (11). Эта подпрограмма должна удовлетворять следующим требованиям.

Условия вызова: JMP DELETE Переход к подпрограмме,

NOP Т Адрес указательной переменной.

JMP UNDERFLOW Первый выход, если происходит событие UNDERFLOW.

Условия ввода: Не определены.

Условия вывода: Если стек, указателем которого является переменная связи Т, пуст, срабатывает первый выход, в противном случае удаляется верхний узел стека и выход переносится к третьей позиции после JMP DELETE. В последнем случае г11 = Т и в гА находится содержимое поля INFO удаленного узла. В любом случае г12 и г13 используются этой подпрограммой.

4. [22] Программа (10) основана на операции Р -J= AVAIL, определенной действиями (6). Покажите, как можно создать такую подпрограмму обработки событий переполнения (OVERFLOW), чтобы без каких-либо изменений в коде (10) в операции Р AVAIL использовалось ограничение SEQMIN, указанное в (7). В общем случае эта подпрограмма не должна изменять содержимое регистров, за исключением регистра rJ и, возможно, индикатора сравнения. Она должна иметь выход в позиции rJ - 2 вместо обычной позиции rJ.

* 5. [24] Операции (14) и (17) эквивалентны операциям с очередью. Покажите, как можно было бы определить операцию "вставка элемента с начала очереди" для получения набора всех действий, выполняемых для дека с ограниченным вводом. Как в таком случае определить операцию "удаление с конца" (для получения дека общего типа)?

6. [21] В операции (14) было установлено LINK(P) ч- Л, тогда как следующая операция вставки элемента в конце очереди изменит значение того же самого поля связи. Покажите, как можно было бы избежать установки LINK(P) в (14) при внесении изменений в проверку условия F = Л в (17).