Д. Кнут - Искусство программирования том 1 (1119450), страница 72

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 72)

вставка и удаление данных в списках с изменяемыми размерами, а также использование таблиц в виде стеков или очередей имеют настолько широкое применение, что читатель наверняка еще не раз встретится с ними и сможет оценить их важность.

Однако в остальной части данной главы мы покинем область абстрактных рассуждений и приступим к изучению важных практических примеров использования этих методов. Первый пример такой практической задачи называется цюполоацческай сортиировкой (!про!од!са! эпгг!пу), которую часто приходится выполнять при проектировании сетей, в так называемых РЕНТ-диаграммах, и даже в лингвистике. Действительно, она может быть очень полезной всегда, когда приходится выполнять частичное упорядочение (рагг!а! отйегту), Частичным упорядочением некоторого множества 5 называется такое отношение между элементами множества 5, которое может быть обозначено символом "~" и обладает следующими свойствами для любых х, у и х (причем необязательно разных) элементов множества 5.

1) Если х С у и у С э, то х ~ ю (Транзитивность.) 1!) Если х С у и и С х, то х = у. (Антисимметричность.) ш) х С х. (Рефлексивность.) х -( у можно трактовать так: ьх предшествует или равно у". Если х ~ у и з ф у, будем обозначать это отношение через х с у и трактовать его как ая предшествует у". Легко видеть, что из (1) — (ш) можно получить следующее. 1') Если х -ч у и я ч г, то х ~ ю(Транзитивность.) 11') Если х ч у, то у г~ х. (Антисимметричность.) ш') х ~ х.

(Нерефлексивность.) Отношение, обозначенное через у ~ я, трактуется так: "у не предшествует я". Если сначала определить отношение С со свойствами (!')-(й!'), то описанный выше процесс можно выполнить в обратной последовательности, т. е. определить отношение х -< у, как такое, для которого х -с у или х = у. Тогда для него должны выполняться условия (!)-(и). Следовательно, свойства (1) — (ш) и (1') — (ш') можно рассматривать как определения частичного упорядочения. Обратите внимание на то, что свойство (и') на самом деле является следствием свойств (Г) и (ш'), однако свойство (й) не следует из свойств (!) и (ш) . Частичное упорядочение довольно часто встречается не только в математике, но и в повседневной жизни.

Примерами его использования в математике являются отношение х < у между яействительными числами х и у, отношение х С у между множествами, отношение хну (х делит у) между положительными целыми числами. В РЕВТ-диаграммах 5 — это набор заданий, которые следует выполнить, а отношение х -< у означает "х должно быть выполнено раньше у". Рис. 6. Частичное упорядочение. Вполне естественно было бы предположить, что 5 является конечным множеством, поскольку оно используется в компьютере. Частичное упорядочение конечного множества всегда можно представить в виде диаграммы, изображенной на рис. 6, на которой объекты изображены маленькими квадратиками, а отношение между ними — стрелками между этими квадратиками. В таком случае х ~ у означает, что от квадратика с ярлыком х к квадратику с ярлыком у проходит некоторый путь, указанный стрелками.

Свойство (й) частичного упорядочения означает, что в такой схеме не сущесглвуетп вамкнушмх пеглель (т. е, не существует путей, замкнутых на себя). Например, если в схеме на рис. 6 провести стрелку от квадратика 4 к квадратику 1, то для них нельзя будет установить отношение частичного упорядочения. Задача топологической сортировки заключается в устпановлении частичного порядка среди обвектпов, упорядоченных в линейном порядке, т.

е. в таком расположении объектов линейной последовательности а1аз...а„, чтобы для любых ау К аь выполнялось условие ( < й. Графически это означает, что квадратики следует расположить на одной линии так, чтобы все стрелки были направлены вправо (рис. 7). Такое переупорядочение не всегда возможно, хотя совершенно ясно, что его нельзя выполнить при наличии замкнутых петель.

Следовательно, искомый алгоритм интересен не только тем, что он позволяет выполнить очень полезную операцию, но и тем, что он доказывает, что данная операиия возмохсна для любого частичного упорядочения. Рис. 7. Отношение упорядочения, показанного на рис. б, после выполнения топологиче- ской сортировки. В качестве примера топологической сортировки представим себе большой словарь с определениями технических терминов. Запишем, что шз ~ шы если определение термина ш1 прямо нли косвенно зависит от определения термина шэ.

Это отношение является частичным упорядочением при условии, что не существует никаких "циклических определений". Тогда задача топологической сортировки заключается в поиске таноео способа упорядочения гперминов в эшом словаре, чтобы никакой гпермин не иснольэовалсл до шого, как он будегп определен. Аналогичные проблемы возникают цри создании программ для обработки объявлений в некоторых ассемблерных и компилируемых языках, а также при создании руководства пользователя с описанием языка программирования или при написании учебников об информационных структурах. Существует очень простой способ выполнения топологической сортировки.

Сортировку следует начать с объекта, которому не предшествует никакой другой объект данного множества. Этот объект удаляется из исходного множества Я н располагается первым в итоговой последовательности. Таким образом итоговая последовательность частично упорядочивается и процесс снова повторяется до тех пор, пока все множество не будет рассортировано. Например, на рис. б сортировку можно было бы начать, удалив элемент 1 или 9, затем (после удаления элемента 1)— удалив элемент 3 и т. д.

Этот алгоритм может оказаться бесполезным только тогда, когда найдется такое непустое частично упорядоченное множество, каждому элементу которого предшествует другой элемент. Но если каждый элемент имеет предшественника, то можно построить последовательность произвольной длины 6ы 6з, 6з,..., в которой 6э~ы с 6,. Так как о является конечным множеством, для некоторого 1 < 6 должно выполняться условие 6 = 6ы Но тогда предполагается, что выполняется условие 6ь ~ 6 +„а это противоречит свойству (В). Для эффективной реализации рассмотренного процесса на компьютере необходимо организовать выполнение перечисленных выше действий, т. е.

поиск объектов без предшественников, а также их удаление из множества. На окончательный вид алгоритма также повлияют заданные характеристики операций ввода и вывода. В общем случае программа должна уметь воспринимать символьные имена объектов и обрабатывать гигантские множества, размер которых может даже превышать размер оперативной памяти компьютера.

Однако обсуждаемые здесь основные идеи могут легко затеряться среди таких усложнений. Поэтому более подробно методы эффективной обработки символьных данных описываются в главе б, а задачу управления большими сетями читателю предлагается обдумать самостоятельно в качестве интересного упражнения. Далее предположим, что сортируемые объекты пронумерованы от 1 до н в произвольном порядке. Вводная часть программы будет находиться на накопителе на магнитной ленте 1. Каждая магнитная запись содержит 50 пар чисел, где пара (у,6) означает, что объект у предшествует объекту 6.

Однако первая пара выглядит как (О,п), где н — это количество объектов. Ввод завершается парой (О, 0). Предположим, что и и все пары помещаются в памяти компьютера, а потому необязательно проверять наличие свободного места в памяти во время ввода этих данных. Выводиться объекты будут уже в отсортированном порядке на накопитель на магнитной ленте 2, причем за ними будет следовать значение О. 7 В Э ь 1 2 3 4 в е соввт[ь1 ТОР [/с] ввс ХХХт впс хххт Рнс. 8. Компьютеряое представление показанной на рис. 6 последовательности элементов с отношениями (18). Например, поток ввода может содержать следующие объекты с такими отношениями между ними: 9~2, 3~7, 7<5, бс8, 8 сб, 4 сб, 1-43, 7-44, 9-45, 2.48.

(18) Здесь необязательно приводить какие-то дополнительные отношения для характеристики искомого частичного упорядочения. Например, дополнительные отношения типа 9 ~ 8 (которые можно вывести из отношений 9 .4 5 и 5 -ч 8) можно без какого-либо влияния на конечный результат опустить или добавить во входной поток данных. В общем случае необходимо указать только те отношения, которые соответствуют стрелкам на диаграмме, показанной на рис, 6. В приведенном ниже алгоритме используется последовательно упорядоченная таблица Х [1], Х[2],, Х [и], в которой каждый узел Х(сс] имеет вид Здесь СООИТ[сс] обозначает количество прямых предшественников объекта сс (т.

Характеристики

Список файлов книги