AOP_Tom1 (1021736), страница 77
Текст из файла (страница 77)
6. Верно ли это утверждение, если 5 является бесконечным множеством? 16. [М22] Для любого заданного частичного упорядочения множества 5 = (хе,..., х ) можно построить его матрицу инцидентнасти ((пс(депсе та!г(х) (ао), где ай = 1, если х, 4 хэ, и а,з = 0 в противном случае. Покажите, что существует такая перестановка строк и столбцов этой матрицы, при которой все ее элементы> расположенные ниже диагонали, будут равны нулю. ь 17. [81[ Каким будет результат выполнения алгоритма Т для исходного набора отношений (18)? 18. [ЯО] Какой смысл имеютЪначения 051ИК(03, 051ИК(1],..., 051ИК [п3 после завершения алгоритма Т (если они вообще его имеют)? 19.
[18) В алгоритме Т на шаге Т5 проверяется начальный элемент очереди, но этот элемент не удаляется нз очереди до шага Т7. Что произойдет, если установить Г +- 001ИК [с) в конце шага Т5, а не на шаге Т7? ° 20. [84[ И, 8 и таблица 051ИК используются в алгоритме Т для организации очереди с узлами, в которых поле СООИТ уже стало равным нулю, но их отношения с наследниками еще не были удалены.
Можно ли для этого вместо очереди использовать стек? Если можно, то сравните полученный алгоритм с алгоритмом Т. 21. [81) Сможет ли алгоритм Т правильно выполнять топологическую сортировку при многократном повторении отношения 1 .К й во входном потоке? Что произойдет, если входной поток будет содержать некоторое отношение в виде З -4 З? 22. [88[ В программе Т предполагается, что на входной магнитной ленте содержится корректная информация, но в программе общего назначения всегда следует предусматривать тщательную проверку входного потока для обнаружения список и попыток "самоуничтожения" программы. Например, если одно из входных отношений является отрицательным для некоторого?г, программа Т может ошибочно изменить одну из своих команд во время записи в КПс3. Предложите такой способ изменения программы Т, который позволил бы избежать подобных сбоев.
ь 23. [87[ Если алгоритм топологической сортировки не может продолжить работу из-за обнаружения замкнутой петли во входном потоке (см. шаг Т8), вряд ли стоит останавливать его работу только для вывода сообщения "Возникла петля". Лучше распечатать одну из петель с отображением части входного потока, который привел к ошибке. Расширьте алгоритм Т так, чтобы в нем была предусмотрена дополнительная возможность распечатки петли в случае необходимости. [Указание, В этом разделе приводится доказательство существования петли, если И > 0 на шаге Т8, на основании которого можно создать данный алгоритм.[ 24. [84[ Реализуйте расширения алгоритма Т из упр. 23 в коде программы Т.
25. [47[ Напишите максимально эффективный алгоритм для выполнения топологической сортировки для очень больших множеств Я, которые содержат гораздо больше узлов, чем может поместиться в памяти компьютера. Предположим, что операции ввода, вывода и временного хранения данных выполняются с помощью накопителя на магнитной ленте. [Указание. При обычной сортировке входных данных предполагается, что все отношения узла располагаются рядом.
Что в таком случае можно было бы предпринять? В частности, необходимо предусмотреть самый неблагоприятный случай, когда задано сильно перемешанное линейное упорядочение. В упр. 24, во введении к главе 5, описывается вариант решения этой задачи с помощью О(!об и) итераций.] 26, [Яэ[ (Распределеннс памяти длл подпрограмлс) Допустим, что на магнитной ленте хранится основная библиотека подпрограмм в перемещаемом виде, который широко использовался в компьютерах 60-х годов. Процедуре загрузки нужно определить величину перемещения для каждой применяемой подпрограммы, чтобы для загрузки каждой необходимой программы потребовалось выполнить только один проход по всем данным.
Проблема заключается в том, что для работы одних подпрограмм необходимо загрузить в память другие подпрограммы. Прн этом редко используемые подпрограммы (которые збычно располагаются в конце ленты) могут вызывать часто используемые подпрограммы (которые обычно располагаются в начале ленты), и потому нужно знать обо всех необходимых подпрограммах до вынолнения прохода по всем данным на ленте. Один из способов решения этой проблемы заключается в хранении "каталога ленты" в памяти. Процедура загрузкй обладает правом доступа х двум таблицам. а) Каталог ленты. Эта таблица состоит из узлов переменной длины следующего вцца: или Здесь ЯРАСŠ— количество слов памяти, необходимых для данной псшпрограммы; ЫИК— ссылка на элемент каталога для подпрограммы, которая находится сразу за данной подпрограммой; ЯОВ1, ЯСВ2, ..., ВОВп (и > 0) — связи с элементами каталога для других подпрограмм, которые необходимы для работы данной подпрограммы; В С для всех слов, за исключением последнего, В» — 1 для последнего слова в узле.
Адрес элемента каталога для первой подпрограммы на магнитной ленте с библиотекой подпрограмм задается переменной связи Р1ЕЯТ. Ь) Список подпрограмм, непосредственно указанных загружаемой программой. Он хранится в последовательных позициях 1[1], 2[2], ..., А[И], гдг И > 0 †переменн, которая известна процедуре загрузки.
Каждый элемент этого списка является связью с элементом каталога для соответствующей ппдпрограммы. Процедуре загрузки также известно количество перемещений (НССС). которые необходимо выполнить для загрузки первой подпрограммы. В качестве небольшого примера рассмотрим следующую конфигурацию. Каталог ленты Необходимые подпрограммы А[1] = 1003 А[2] = 1010 И=2 Р1ЕЯТ = 1002 И1.0С = 2400 Каталог ленты в данном случае показывает, что в указанном порядке на ленте хранятся подпрограммы 1002, 1010, 1006, 1000, 1005, 1003 и 1007.
Подпрограмма 1007 занимает 200 позиций, и при ее работе предполагается испольэовать подпрограммы 1005, 1002 и 1006; и т. д. Для загрузки этой подпрограммы потребуются подпрограммы 1003 и 1010, которые будут размещены в ячейках по адресам > 2400. В свою очередь, для этих подпрограмм потребуется загрузить также подпрограммы 1000, 1006 и 1002, Блок распределения памяти подпрограммы должен изменить таблицу Х так, чтобы каждый элемент 1[1], 2[2],... принял следующую форму: В 1000; 0 1001: -1 1002: -1 1003: 0 1004: -1 1005:, -1 1006: — 1 1007; 0 1008: 0 1009: -1 1010: — 1 ЯРАСЕ 11ИК 20 1005 1002 0 30 1010 200 1007 1000 1006 100 1003 60 1000 200 0 1005 1002 1006 0 20 1006 (за исключением последнего Ялемента, который описывается ниже), где ЯЯ — загружаемая подпрограмма и ВАЯŠ— величина перемещения. Данные элементы должны быть расположены в том же порядке, в котором они располагаются на ленте.
Ниже показано одно из возможных решений задачи из проведенного выше примера. ВАЯЕ ЯВВ ВАЯЕ ЯВВ Х[1]: 2400 1002 Х[4]: 2510 1000 Х[2]: 2430 1010 Х[5]: 2530 1003 Х [3]: 2450 1006 Х[6] г 2730 0 Последний элемент содержит значение адреса первой неиспользуемой ячейки памяти. (Очевидно, что зто не единственный способ работы с библиотеяой подпрограмм. Соответствующая ему организапия библиотеки в значительной степени зависит от типа используемого компьютера и выполняемых приложений. При работе с мощными современными компьютерами для организации библиотеки подпрограмм потребуется совершенно другой подход. Тем не менее рассмотренный выше метод является прекрасным примером использования интересных приемов работы с последовательными и связанными данными.) Назначение этого упражнения состоит в создании алгоритма решения поставленной задачи.
Созданный для этого блок распределения памяти может при подготовке решения преобразовывать каталог ленты произвольным образом, так как каталог ленты может считываться снова и снова блоком распределения памяти при следующем распределении, причем каталог ленты не будет востребован никакими другими частями процедуры загрузки. 27, [ЯЯ) Напишите программу для компьютера М1Х, реализуюшую алгоритм из упр. 26. 26. (40) Приведенная ниже конструкция демонстрирует способ "решения" достаточно общей задачи — игры для двух лиц, например шахматы, ним или другие более простые игры.
Рассмотрим конечное множество узлов, каждый из которых представляет собой возможное состояние игры. Существует несколько шагов (или ни одною), которые позволяют преобразовать каждое состояние в некоторое другое. Назовем состояние х предшественником состояния у (а у — наследником состояния х), если существует такой шаг, который переводит состояние х в состояние р. Состояния без наследников называются проигрышем нли выигрышем. Игрок, делающий ход с переходом в состояние х, является соперником игрока, который делает ход с переходом от состояния х к состояниям-наследникам. Имея такую конфигурацию состояний, полный набор выигрышных состояний (в которых может выиграть игрок, делающий следующий ход) и полный набор проигрышных состояний (в которых обязательно проигрывает игрок, делающий следующий ход) можно вычислить, повторяя следующую операцию до тех пор, пока не будет достигнуто неизменное состояние.
Обозначим состояние "проигрышным", если все состояния-наследники являются "выигрышными", и обозначим состояние "выигрышным", если хотя бы одно состояние-наследник является "проигрышным". После бесконечного повторения атой операции некоторые состояния могут быть никак не обозначены. Это значит, что игрок, делающий следующий ход из такого состояния, не может выиграть, но его нельзя победить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
