Одна из тех радостей, что доставляет нам изучение информатики, – это знакомство с замечательными алгоритмами. В этой лекции мы займемся исследованием алгоритма, который обладает рядом достоинств, заслуживающих нашего внимания. Он полезен на практике, он, обладая хорошим математическим базисом, элегантен, он иллюстрирует технику решения задач, применимую в различных контекстах.
Познакомить вас с уже готовым решением неинтересно. Вместо этого мы начнем разрабатывать это решение шаг за шагом, как это делается для всякой научной проблемы. Мы начнем с постановки задачи, перейдем к ее математическому анализу, займемся поиском структуры данных, обеспечивающих корректность и эффективность решения. Мы не только спроектируем алгоритм, но, не останавливаясь на этом, получим полное инженерное решение, удовлетворяющее всем практическим требованиям. В конце лекции уроки этого примера позволят сформулировать некоторые общие принципы разработки алгоритмов и инженерии программ.
Вы решили сегодняшний день посвятить культуре: что может быть лучше, чем посещение Лувра и музея Орсе в Париже? Но для этого вам понадобится карта, и нужно приобрести проездной на метро, поскольку срок старого уже истек, но для проездного нужны деньги, так что придется зайти в банк или воспользоваться банкоматом. Можно выразить эти ограничения следующим образом:
[Map, Louvre], [Map, Orsay], [Pass, Louvre], [Pass, Orsay], [Money, Pass]
Здесь каждое ограничение задается парой [x, y], означающей, что "x должно случиться прежде чем y". Это можно отобразить графически:
(рис 10.1) Упорядочение ограничений
Топологической сортировкой множества элементов, подчиняющихся ограничениям порядка, называется перечисление элементов в порядке, удовлетворяющем ограничениям. В данном примере топологическими сортировками являются последовательности:
Money, Pass, Map, Louvre, Orsay
Map, Money, Pass, Orsay, Louvre
Money, Map, Pass, Louvre, Orsay
Заметьте: последовательность Pass, Money, Map, Louvre, Orsay некорректна, поскольку нарушается ограничение [Money, Pass].
Задача
[Orsay, Money], создавая тем самым цикл, то никакого решения больше существовать не будет, так как мы, с одной стороны, требуем, чтобы "утром – стулья, вечером – деньги", а с другой стороны, требуем "деньги вперед".Если существует более одного решения, то возникает проблема выбора одного из них. Обычно с любым решением связывается некоторая стоимость, тогда целью может быть поиск решения с минимальной стоимостью. Вскоре при анализе алгоритма мы увидим, где может применяться этот критерий при поиске нужного решения. Другой подход может состоять в том, чтобы найти все решения.
Задача
[B, A], [D, A], [D, C], [B, D], [E, C]. Здесь ограничение [x, y] содержательно означает "x не должно скрывать никакую часть y". Возможным решением является последовательность: B, D, E, A, C.
(рис 10.2) Прямоугольники с ограничением предшествования
Вот пример, дающий удобную визуализацию задачи. Рассмотрим точки на плоскости:
(рис 10.3) Конечное множество точек
Введем для точек $$p_1$$ с координатами $$(x_1, y_1)$$ и $$p_2$$ с координатами $$(x_2, y_2)$$ отношение $$\ll$$ ("строго меньше"), устанавливающее, что $$p_1 \ll p_2$$, если:
Для четырех точек, показанных на рисунке, справедливо следующее:
$$a\ll b\qquad\qquad a\ll d\qquad\qquad b\ll d\qquad\qquad c\ll d$$p « q, то в списке перечисления p предшествует q. Для наших четырех точек существуют три таких перечисления:
a, b, c, d
a, c, b, d
c, a, b, d
Три возможных обхода точек можно визуализировать:
(рис 10.4) Три типологических сортировки множества точек
С другой стороны, перечисление a, d, b, c не совместимо с отношением, поскольку свойство c « d требует, чтобы c предшествовало d.
Задача, обсуждаемая в этой главе, имеет точную математическую формулировку.
r требуется найти отношение полного порядка, для которого r является подмножеством.Это определение использует математические понятия – отношения как множества, ациклические отношения, отношения порядка (полного или частичного), которые теперь предстоит рассмотреть.
А (для простоты рассматривается только бинарное отношение) задается множеством пар в форме [x, y], где оба элемента пары являются элементами А.Примером отношения на множестве {1, 2, 3} является:
{[1, 2], [1, 3], [2, 3]}
Мы можем назвать это отношением < ("меньше", так как x и y принадлежат множеству {1, 2, 3} и x меньше y).
Мы можем использовать отношения для описания предыдущих примеров.
below (ниже) на множестве прямоугольников, содержащее все пары прямоугольников [x, y], таких, что в области наложения прямоугольников должны показываться точки y, а не x.before (прежде) – множество пар {[Map, Louvre], [Map, Orsey], …} – является отношением на множестве {Pass, Money, Map, Louvre, Orsay}, содержащим пары [x, y], такие, что событие x должно произойти раньше y.used_in ("используется в"), заданное на множестве терминов словаря, содержит все пары [x, y], такие, что определение термина y содержит термин x.called_by ("вызывается в"), заданное на множестве методов класса, содержит все пары [x, y], такие, что тело метода y содержит вызов метода x.« над точками – множество пар {[a, b], [a, d], [b, d], [c, d]}.Все наши примеры были до сих пор
Это определение следует дополнить.
r над множеством A является последовательность $$x_1,\;\ldots x_m (m\ge 2)$$ из элементов $$A$$, такая, что все последовательные пары $$[x_i,x_{i+1}]$$ для $$1\le i < m$$ принадлежат $$r$$, и $$x_m = x_1$$.Отношение before, введенное ранее, циклов не имеет:
(рис 10.5) Отношение, описывающее ограничение порядка
r встречается (при m = 2) для элемента x, такого, что [x, x] принадлежит r.Для успеха
r над непустым, конечным множеством А существует элемент x из А, не имеющий предшественника в r.y для отношения r является элемент x, такой, что пара [x, y] принадлежит r.Теорема доказывается от противного. Предположим противное, что каждый элемент в $$А$$ имеет по меньшей мере одного предшественника. Пусть $$x_1$$ – элемент из $$А$$ (он существует, так как множество не пусто). По предположению, у него есть хоть один предшественник, выберем любой и назовем его $$x_2$$. По тем же причинам есть предшественник $$x_3$$ и у $$x_2$$, так что в $$r$$ существует пара $$[x_3, x_2]$$. Продолжая вывод, следует признать существование
Доказательство конструктивно, и мы будем его использовать при проектировании алгоритма
Предположение о конечности множества $$А$$ существенно. Теорема неприменима к бесконечным множествам, например, отношение "меньше" для целых чисел в математике
Идея
x, y, z из множества X, на котором оно определено.
| О1 | Антирефлексивность: отношение не имеет пар вида [x,x]. |
| O2 | Транзитивность: из того, что отношению принадлежат пары [x, y] и [y, z], следует, что отношению принадлежит и пара [x, z]. |
Такое отношение порядка является также:
| О3 | асимметричным: из того, что отношению принадлежит пара [x, y] следует, что отношению не принадлежит пара [y, x]. |
(Доказательство. Если бы обе пары принадлежали отношению, то из транзитивности следовала бы рефлексивность – существование пары [x, x], что противоречит свойству
< – "строго меньше, чем". Также возможно работать с нестрогими версиями отношения, такими как отношение <= ("меньше или равно").Отношение "<" на {1, 2, 3} (или на любом другом множестве целых) является отношением порядка. Таким же является отношение « на точках. Наши другие ациклические отношения – before для задач, used_in для терминов, called_by для методов – антирефлексивны и асимметричны, но они не обязательно транзитивны, так что они не являются отношениями порядка. Вскоре мы увидим, как можно получить транзитивную версию.
Отношения порядка тесно связаны с
Доказательство от противного. Предположим, существует цикл $$x_1, x_2, \ldots x_n$$, где $$x_n$$ то же, что и $$x_1$$. По транзитивности это влечет рефлексивность, что противоречит
[x,y] и [y, x]. Такой случай является частным случаем цикла с двумя элементами. Подобно, пара [x, x], нарушающая антирефлексивность, является циклом с одним элементом.Здесь еще одно интересное свойство:
Это может быть проиллюстрировано на отношении before, выражающего ограничения порядка между задачами. Отношение антирефлексивно, асимметрично и ациклично, но оно не транзитивно, поскольку содержит пары [Money, Pass] и [Pass, Louvre], но не содержит пары [Money, Louvre]. Мы можем расширить отношение до транзитивного, добавив все пары вида [x, z], для которых в исходном отношении есть пары [x, y] и [y, z], выполняя эту операцию, пока добавление не перестанет быть возможным. Результатом этого процесса является
(рис 10.6) Транзитивное замыкание ограничений порядка
Для отношения called_by между процедурами x и y, если у вызывает x прямо или косвенно. Для отношения child между людьми, обозначающего множество пар [x, y], таких, что x является потомком y, r обозначается как $$r^+$$, так что мы можем полагать, что $$child^+ = descendant$$ (потомок представляет
Доказательство.
Этот результат позволяет нам рассматривать before между стоящими перед нами задачами, – если задача Money должна предшествовать задаче Pass, а задача Pass должна предшествовать задаче Louvre, то мы понимаем, что задача Money должна предшествовать задаче Louvre. Другими словами, мы инстинктивно принимаем
Вычисление
Для описания выхода
| О4 | Для любых a и b имеет место одно из следующих свойств:
[a, b] принадлежит r;[b, a] принадлежит r;a = b. |
Для понимания О4 заметьте: из
Отношение "<" на целых является тотальным отношением. Но не каждое отношение порядка является таковым. Отношение "«" на точках плоскости таковым не является, так как это означало бы, что для любых двух различных точек плоскости p1 и p2 должно выполняться p1 « p2 или p2 « p1.
(рис 10.7) Точки на плоскости и отношение полного порядка
Заметьте, пара точек [a, c] не принадлежит отношению, так как не верно, что a « c; точно так же неверно, что и c « a. Другим контрпримером является пара точек [b, c].
На множестве четырех точек можно установить различные отношения порядка, являющиеся полными. В частности, любое перечисление, в котором каждая точка появляется ровно один раз, можно рассматривать как задание полного порядка t. Вот как можно определить этот порядок: пара точек [p, q] принадлежит t, если и только если p предшествует q в перечислении. Например, перечисление [a, b, c, d] определяет
{[a, b], [a, c], [a, d], [1]
[b, c], [b, d],
[c, d]}
Верно и обратное: каждый
Такой тотальный порядок является топологической сортировкой исходного отношения "« ", если и только если тотальный порядок совместим с исходным. Совместимость означает, что когда p « q в исходном порядке, то p предшествует q в тотальном порядке.
(рис 10.8) Точки на плоскости и отношение «
Мы уже видели, что три тотальных порядка удовлетворяют этому требованию для нашего примера: соответствующими перечислениями являются a, b, c, d (в примере 10.1 представлено в виде множества пар); a, c, b, d и c, a, b, d.
Что означает "совместимость", если это понятие рассматривать более точно? Его нетрудно специфицировать, благодаря определению отношения как множества пар. Сказать, что тотальный порядок, заданный перечислением a, b, c, d, совместим с заданным « является множеством пар:
{[a, b], [a, d], [b, d], [c, d]} [2]
Это множество действительно является подмножеством множества пар (пример 6.1), задающего тотальный порядок. Это свойство выражает тот факт, что когда ограничение задает некоторый порядок между двумя элементами, то на
Так вырабатывается определение
Ациклические отношения имеют
Отсутствие циклов является очевидным необходимым условием существования
Справедлива следующая теорема.
r над конечным множеством А существует тотальное отношение порядка t над А, такое, что $$r\subseteq t$$Для доказательства этой теоремы можно было бы использовать то наблюдение, что $$r\subseteq r^+$$, где $$r^+$$ – это r, и предыдущее доказательство того, что $$r^+$$ является отношением порядка. Этого достаточно, чтобы расширить $$r^+$$ до полного отношения порядка. Но для наших целей более интересно другое доказательство. Это конструктивное доказательство (основанное на теореме об отсутствии предшественника), позволяющее нам непосредственно получить схему алгоритма.
Доказательство ведется индукцией по числу элементов n множества A. Если n = 0, множество пусто, единственно возможным отношением является пустое отношение (пустое множество пар элементов из A), которое является полным порядком. Это доказывает
Если вы предпочитаете иное, в качестве базиса можно выбрать случай n = 1, для которого A состоит из одного элемента x. Хотя теперь A не пусто, единственное A снова является пустым отношением, так как единственная пара [x, x], которую можно создать, образует цикл.
n элементов, и рассмотрим n + 1 элементов. Рисунок поясняет идею доказательства:
(рис 10.9) Расширение, дополняющее топологическую сортировку
Теорема об отсутствии предшественника говорит нам, что А имеет по крайней мере один элемент, не имеющий предшественника. Пусть x – такой элемент. Пусть А' – множество элементов А за исключением x. Пусть r' – отношение на А', содержащее все пары из r, за исключением тех, что содержат x. Очевидно, что r' является A'. По предположению индукции, так как A' имеет n элементов, существует t' над A', совместимый с r' (это то же самое, что сказать $$r^\prime\subseteq t^\prime$$). Теперь рассмотрим отношение t над A, состоящее из следующих пар:
t';[x, y], где y – элемент из A'.t как перечисление элементов A, которое начинается с x и продолжается перечислением A', заданным t'.Нетрудно видеть, что t – это r, что и доказывает теорему.
Теорема о
С теоретическими основами все ясно, так что можно приступать к поиску инженерного решения. Ядром является алгоритм
Что можно сказать об ожидаемой емкостной и временной сложности алгоритма?
Входом для алгоритма является множество элементов и множество ограничений. Обозначим через n число элементов, m – число ограничений.
Алгоритм должен (в случае
Так что наилучшее время, на которое можно надеяться, – это O(n + m).
Самое удивительное, что разрабатываемый ниже алгоритм
Чисто алгоритмическое решение могло бы использовать функцию в форме:
topologically_sorted (elements:…; constraints:…): LIST[…]
— Перечисление элементов множества elements
— в порядке, совместимом с множеством ограничений constraints.
Предполагается, что входные типы позволяют задать множества элементов и ограничений – elements и costraints, соответствующие нашим прежним обозначениям A и r.
Лучшее решение – как покажет дальнейшая разработка – дает ОО-подход с построением класса TOPOLOGICAL_SORTED, любой экземпляр которого представляет задачу record_element и record_constraint.
Вместо функции topologically_sorted, как выше, будем иметь в классе:
process, выполняющую процесс sorted, который возвращает список элементов, созданный при работе процедуры process.Этот каркас даст нам больше гибкости, и мы получим возможность дополнить его многими полезными свойствами.
Множества элементов A и ограничений r могут поступать из различных источников. Например, мы могли бы иметь файл, перечисляющий ограничения, каждое из которых задается одной строкой файла:
Map Louvre
Map Orsay
Pass Louvre
Pass Orsay
Money Pass
(рис 10.10) Элементы и ограничения
Возможно, было бы полезно иметь отдельный файл, перечисляющий все элементы или, по меньшей мере, элементы, не включенные ни в одно из ограничений (мы не можем догадаться о существовании таких элементов, анализируя ограничения, но они должны быть частью вывода).
В других условиях ввод мог бы осуществляться интерактивно, используя программу или Web-форму. В примерах, таких как упорядочение прямоугольников, отображаемых на экране, упорядочение терминов словаря или методов класса, формат данных будет различным.
Для обеспечения общности сделаем наш базовый класс универсальным: TOPOLOGICAL_SORTED[G], где параметр G задает тип элементов. Тогда результат запроса sorted, который обозначает топологически отсортированный список элементов, созданный в process, имеет тип LIST[G]. Две процедуры инициализации, о которых говорилось выше, имеют сигнатуры:
record_element (e: G)
record_constraint (e, f: G)
Рассмотрим r на множестве элементов A. Так как нам необходимы имена, используемые в программе, то позвольте полагать, не предрешая выбор реализации, что класс TOPOLOGICAL_SORTED имеет доступные запросы elements и constraints. Общая схема для алгоритма process такова:
from …until elements.is_empty loop
"Пусть x – элемент без предшественников в ограничениях"
"Рассматривать x как следующий элемент sorted"
"Удалить x из множества элементов"
"Удалить все пары, начинающиеся x, из множества ограничений)"
end
Уточненная нужным образом эта форма будет работать при условии, что мы начинаем с
Теоремы о
process
— Выполняет в sorted перечисление элементов множества elements
— в порядке, совместимом с множеством ограничений constraints.
require
— "constraints описывают ациклическое отношение"
do
from
create {….} sorted. make
invariant
— "constraints описывают ациклическое отношение"
until
elements. is_empty
loop — Как и ранее, за тем исключением, что явно используется результат sorted:
"Пусть x – элемент без предшественников в ограничениях"
sorted. extend (x)
"Удалить x из множества элементов"
"Удалить все пары, начинающиеся x, из множества ограничений"
variant
elements. count
end
ensure
— "sorted представляет топологическую сортировку elements, согласованную
— с constraints"
end
Версия схемы алгоритма, в принципе, корректна, но не подходит для большинства приложений, встречающихся в реальной жизни.
Проблема в предусловии, требующем, чтобы на вход было подано [Map, Louvre] или [Map, Orsey], как выше. Такой вход может готовиться человеком, а ему свойственно ошибаться, и он имеет право на ошибку, что недопустимо в программе (при рассмотрении сборки промышленных изделий могут встречаться тысячи узлов и десятки тысяч ограничений между ними, задающих порядок сборки).
В примере с терминами словаря мы не можем надеяться, что не встретятся два или более термина, ссылающихся друг на друга в своих определениях (следовательно, создающих циклы), но у нас нет способа принуждать авторов словаря. Справедливо обратное – автор может требовать от программы: "Упорядочьте в словаре термины так, чтобы определение термина встречалось раньше его использования. Но, кстати, если вы обнаружите взаимные ссылки терминов, сообщите мне о них, чтобы я мог скорректировать определения".
Аналогично задача упорядочения методов класса, чтобы определение метода предшествовало его вызову, невозможна в случае
Эти рассмотрения приводят к изменениям контракта метода process, более благосклонного к своим клиентам. Прежний контракт:
require
— "constraints описывают ациклическое отношение"
ensure
— "sorted представляет топологическую сортировку elements,
— согласованную с constraints"
заменяется новым, более реалистичным контрактом:
— (Нет предусловия)
ensure
— "sorted представляет топологическую сортировку, согласованную
— с constraints, для всех членов elements, не входящих в цикл"
Этого все же недостаточно. Класс должен предоставлять своим клиентам отчет о возникающих циклах и указывать, какие элементы в них включены. Одним из способов обеспечения такой функциональности является введение булевской функции.
has_cycle: BOOLEAN
— Содержат ли циклы отношение, заданное elements и constraints?
do …end
Говоря неформально, нужна функция, которая будет возвращать список элементов, включенных в цикл (void, если и только если has_cycle имеет значение false). Концептуально это звучит разумно, но это не лучший способ, так как вычислительно представляет дорогое решение. Нахождение циклов – задача функции has_cycle, фактически является столь же трудной по времени и памяти, как и сама задача
Теорема об отсутствии предшественника подсказывает нам, что цикл можно найти как побочный бонус процесса
Рассматриваемая далее программа
Вместо прежнего инварианта:
—"constraints описывают ациклическое отношение на elements"
будем теперь использовать его ослабленную форму:
—"constraints описывают подмножество исходного отношения на elements"
Отсюда следует, что
—"Любой цикл в constraints присутствует в исходном отношении"
а также:
—"constraints описывает ациклическое отношение, если исходное отношение ациклично".
Это та основа, которой мы будем придерживаться. Как следствие, мы больше не будем использовать в качестве условия выхода из цикла elements.is_empty, как ранее, так как непустое множество elements не гарантирует больше, что можно корректно выполнить оператор:
"Пусть x – элемент без предшественников в ограничениях"
В качестве нового условия выхода будем иметь:
"Нет элементов без предшественников в ограничениях"
Отрицание этого условия означает, что есть по крайней мере один элемент без предшественников, – а это гарантия того, что в теле цикла можно найти очередного кандидата, включаемого в результат выхода.
Мы можем теперь определить полную форму класса, который будет служить каркасом нашего решения:
class
TOPOLOGICAL_SORTER [G –> HASHABLE]
feature {NONE} — Внутренние структуры данных
…Смотри следующие разделы этой главы…
feature — Инициализация
record_element (a: G)
— Включить а в множество элементов.
require
not_sorted: not done
do
…Смотри следующие разделы…
end
record_constraint (a, b: G)
— Включить [a, b] в ограничения.
require
not_sorted: not done
do
…Смотри следующие разделы…
end
feature — Status report
done: BOOLEAN
— Выполнена ли топологическая сортировка?
feature — Element change
process
— Выполнить топологическую сортировку над всеми применимыми элементами.
— Результаты доступны через sorted, cycle-found и cyclists.
require
not_sorted: not done
do
…Смотри следующие разделы…
ensure
sorted: done
end
feature — Access
cycle_found: BOOLEAN
— Исходное ограничение приводит ли к циклу?
cyclists: LIST [G]
— Элементы, включенные в какой-либо цикл.
sorted: LIST [G]
— Список из всех элементов, которые допускают упорядочивание,
— согласованное с ограничениями
feature — Status setting
reset
— Допустить дальнейшее обновление элементов и ограничений.
do
done:= False
cycle_found:= False; cyclists:= Void; processed_count:= 0
ensure
fresh: not done
end
invariant
elements_exist: elements /= Void
constraints_exist: constraints /= Void
cyclists_only_if_cycle: done implies (cycle_found = (cyclists /= Void))
end
Класс является универсальным, его родовой параметр G представляет тип элементов. Запись G -> означает, что мы "ограничиваем" G (понятие, вводимое в следующей главе) типом
Алгоритм будет основываться на внутренних структурах данных, проектируемых в следующих разделах этой главы. Поскольку соответствующие методы создаются для внутреннего использования, они не будут доступны клиентам класса и потому объявлены как feature {NONE}.
Сразу же после того, как метод process выполнит свою работу, его результаты будут доступны клиентам через несколько связанных запросов.
done, позволяющий клиентам выяснить, выполнена ли false.sorted, дает порядок, совместимый со всеми ограничениями, и включает все элементы, не входящие в цикл.Булевский запрос cycle_found показывает, что есть элементы, включенные в какой-либо цикл.
cyclists. Предложение инварианта cyclists_only_if_cycle говорит нам, что запрос имеет смысл только при условии истинности cycle_found.Клиент, желающий выполнить
your_structure: TOPOLOGICAL_SORTER [YOUR_ELEMENT_TYPE]
…
create your_structure
…Вызовы вида your_structure.record_element(x) для записи элементов …
…и your_structure.record_constraint(x, y) для записи ограничений…
your_structure. process
— Теперь становятся доступными результаты топологической сортировки
— your_structure.sorted
if your_structure. cycle_found then
— Теперь становятся доступными элементы, включенные в цикл
— your_structure.cyclists …
end
Было бы желательно для согласованности поставлять запросы sorted, cycle_found и cyclists с предусловием done, но мы временно будем опускать предусловие.
Однако предусловие not done задано для процедур инициализации record_element и record_constraint, так же как и для процедуры process, имеющей постусловие done. Как результат, попытка повторного вызова процедуры process на одном и том же экземпляре класса будет приводить к ошибке. Конечно, запросы можно вызывать сколь угодно много раз. Процедура reset добавлена на случай, когда вы хотите явно добавлять элементы и ограничения уже после вызова process для подготовки нового его вызова.
Процедура reset просто устанавливает done равным false, не производя очистки предыдущих элементов и ограничений. Мы можем добавить процедуру forget, которая вызовет reset и очистит структуры данных. Но в этом случае клиенту проще создать новый экземпляр TOPOLOGICAL_SORTER.
Теперь мы можем приступить к полной реализации ключевой части нашего решения – процедуре process.
Общий алгоритм этого метода уже написан, осталось адаптировать его с учетом всех сделанных уточнений (ослабление инварианта, использование метода sorted, представляющего результат в TOPOLOGICAL_SORTER). В результате получаем:
from
create {…} sorted. make
until
"Нет элемента без предшественников"
Loop
"Пусть x — элемент без предшественников"
sorted. extend (x)
"Удалить x из множества элементов"
Удалить все ограничения, начинающиеся с x
end
if "остался хоть один элемент" then — Отчет о цикле:
cycle_found:= True
"Вставьте эти элементы в cyclists"
end
Все, что осталось, – но не спешите слишком радоваться, главные трудности еще впереди, – это уточнить
| Т1 | Найти элемент без предшественников – или отчитаться об отсутствии такового. |
| Т2 | Для заданного элемента x удалить его из множества элементов. |
| Т3 | Для заданного элемента x удалить из множества ограничений все ограничения, начинающиеся этим элементом (все пары вида [x, y]). |
Мы должны найти такие представления данных (множеств элементов и ограничений), которые делают эти операции эффективными, насколько это возможно. Структуры данных будут появляться как закрытые компоненты класса в разделах, резервированных для этих целей.
Приведенная выше схема класса оставила незаполненными тела двух методов класса: add_element и add_constraint. Нам предстоит дополнить методы, основываясь на структурах данных, которые мы сейчас спроектируем.
Для нашей первой попытки построения структуры данных естественно выбрать представление, которое непосредственно моделирует входные данные в том виде, как они к нам приходят (наш небольшой опыт в изучении программирования говорит, что не следует утверждать, что некоторое решение является "естественным". То, что кажется естественным мне, вовсе может не казаться таковым для вас, а то, что естественно для меня и для вас, может оказаться довольно посредственным решением).
Чаще всего входные данные могли бы поступать в виде списка элементов и списка ограничений. Мы могли бы использовать атрибуты класса, которые непосредственно отображают эти структуры данных (сделав их закрытыми для клиентов, размещая их в секции feature {NONE}):
elements: LINKED_LIST [G]
constraints: LINKED_LIST [TUPLE [G, G]]
В нашем примере структуры данных будут выглядеть подобным образом:
(рис 10.11) Элементы и ограничения
Для простоты предполагается, что мы присвоили номера нашим элементам следующим образом (рис 10.12).
(рис 10.12) Нумерация элементов
Можем ли мы реализовать при таком представлении данных операции Т1, Т2, Т3 и процедуры record_element и record_constaint, и если да, то какова цена решения – сложность по времени и по памяти?
Две процедуры реализуются непосредственно. Например, для выполнения record_constaint достаточно вызывать стандартный метод:
constraints. extend ([x, y])
Новая пара [x,y] добавится в конец списка ограничений. Подобным образом record_element(x) реализуется вызовом elements.extend(x).
elements и constaints имеют значения, отличные от void. Соответствующие операторы создания create могут появляться в форме default_create или вызываться по требованию, когда в них возникает необходимость. Все это справедливо и для других структур данных, рассматриваемых ниже.Это представление можно использовать и при реализации других операций. Давайте проанализируем их стоимость, когда у нас есть n элементов и m ограничений.
constaints и считать предшественников для каждого элемента, затем обойти список элементов для поиска тех, у кого число предшественников равно нулю. Первый обход потребует $$O(m)$$ операций, второй – $$O(n)$$, и поскольку это нужно делать на каждом шаге, в целом понадобится операций $$O(n^*m + n^2)$$.В практических приложениях следует ожидать, что для каждого элемента задается несколько ограничений, так что $$m > n$$, а потому $$O(m^*n)$$ хуже, чем $$O(n^2)$$. Поскольку в реальных задачах $$n$$ может быть велико, сложность $$O(n^2)$$ представляется неприемлемо высокой.
Так что наш первый выбор структуры данных дает решение задачи, но его производительность не позволяет построить масштабируемое приложение, пригодное для задач большой размерности.
К счастью, мы можем найти решение лучшее, чем "естественное". Как показывает опыт, мы не всегда должны использовать структуры данных в том виде, как они к нам приходят. Списки elements и constraints – это непосредственное отражение данных внешнего мира, естественного представления данных человеком, который вводит задачи и описывает ограничения между задачами. Но форма данных, простая и естественная для внешнего мира, вовсе не является лучшей формой для алгоритма, предназначенного для обработки этих данных некоторым специальным образом. Вместо того чтобы слепо следовать форме приходящих данных, алгоритм может начинаться с этапа инициализации, который преобразует данные в формат, наилучшим образом приспособленный к их обработке.
Следующие структуры данных помогают выполнить работу
successors: ARRAY [LINKED_LIST [INTEGER]]
— Индексами массива являются номера элементов. Для каждого элемента x
— задается список его непосредственных последователей – элементов y,
— таких, что есть ограничение [x, y].
predecessor_count: ARRAY [INTEGER]
— Индексами массива являются номера элементов.
— Для каждого элемента x указывается число его непосредственных
— предшественников.
Следующий рисунок иллюстрирует представление данных для нашего примера.
(рис 10.13) Число предшественников и список последователей
На следующем рисунке приведена уже хорошо нам знакомая схема, где введена нумерация элементов. Она поясняет предыдущий рисунок. По схеме ясно, что, например, у задачи 1 предшественников нет, но есть два последователя, а у задачи 5 – один предшественник и те же два последователя (2 и 4).
(рис 10.14) Знакомая схема с нумерацией элементов
В этом представлении интересно то, что массив, задающий число предшественников, является избыточным, поскольку всю хранимую в нем информацию можно извлечь из массива последователей. Но ничего ошибочного в таком представлении информации нет, поскольку, как мы увидим, за счет этого дублирования можно добиться существенного улучшения времени вычислений.
Нахождение компромисса память-время является ключевой составляющей проектирования хорошего алгоритма. Конечно, компромисс должен быть приемлемым. В данном случае наша цель — получить алгоритм с временной сложностью O(m + n), сохраняя ту же сложность и для памяти, требуемой для хранения данных. Такая память нужна для хранения массива predecessor_count с емкостью O(n) не меняет
Исходные структуры данных – elements и constraints – также требуют памяти O(m + n).
Удобно для пущей ясности добавить запрос, доступный клиентам:
count: INTEGER
— Число элементов
Также полезно для улучшения читабельности добавить инварианты класса. Два последних предложения выражены неформально:
elements.count = count
predecessor_count. count = count
successors.count = count
— Для каждого i из интервала 1..count элемент predecessor_count[i]
— задает число предшественников i-го элемента для заданных ограничений.
— Для каждого i из интервала 1..count элемент successors[i]
— задает список всех последователей i-го элемента для заданных ограничений
— или void, если последователей нет.
Чтобы использовать массив, нужно некоторым образом пронумеровать наши элементы. Ранее это было сделано в интересах удобства обращения. Теперь это становится необходимостью, связанной с нашим выбором структуры данных.
Значит ли это, что теперь требуется изменить родовой параметр класса TOPOLOGICAL_SORTER[G], поскольку все манипуляции над элементами будут теперь использовать их целочисленные номера? Абсолютно нет. Остается необходимым для выразительности создать механизм, применимый к элементам любого типа. На практике для этого потребуется хэш-таблица и массив:
index_of_element: HASH_TABLE [INTEGER, G]
— Для каждого элемента дает его индекс
element_of_index: ARRAY [G]
— Для каждого индекса дает ассоциированный с ним элемент
Элемент хэш-таблицы index_of_element[e] дает целое x – индекс элемента e типа G. В свою очередь, element_of_index[x] = e.
В обоих случаях используется нотация с квадратными скобками.
(рис 10.15) Взаимное отображение элементов и индексов
Обе эти структуры при разумной реализации требуют памяти O(n).
Для определения хэш-таблицы с элементами типа G требуется, чтобы тип G удовлетворял G -> (ограниченная универсальность будет подробно рассматриваться в следующей главе, сейчас же понятно, что элементы должны допускать построение хэш-функции).
Класс TOPOLOGICAL_SORTER[G -> не будет экспортировать компоненты index_of_element и element_of_index, так как они необходимы только для целей реализации, но мы должны позволять клиентам находить элементы, поскольку это является частью общей задачи работы с элементами, поэтому мы будем экспортировать запрос:
has_element (e: G): BOOLEAN
— Является ли e одним из элементов топологической сортировки?
do
Result:= index_of_element. has (e)
ensure
consistent: Result = index_of_element.has (e) and then
index_of_element [e] >= 1 and then
index_of_element [e] <= element_of_index. count and then
element_of_index [index_of_element [e]] = e
end
Убедитесь, что вы понимаете постусловие.
Давайте теперь докажем, что новые структуры данных позволяют добиться нашей цели – времени O(m + n). Необходимо рассмотреть два аспекта: выполнение операций Т1-Т3 и затраты на инициализацию – создание структур данных predecessor_count и O(m + n), но для создания структур требовалось бы $$O(m^*n)$$ времени, то в целом никакого выигрыша мы бы не получили.
Представляется, что несложно реализовать построение требуемых структур данных за время O(m + n). Обрабатывая последовательно каждое ограничение [x, y], зная y, можно увеличить на 1 значение соответствующего элемента predecessor_count, а зная x, можно добавить последователя y в список соответствующего элемента O(m + n) возможно и сосредоточимся на рассмотрении операций Т1-Т3.
Начнем с Т3: "Для заданного элемента x удалить из множества ограничений все ограничения, начинающиеся этим элементом (все пары вида [x, y])". Если мы знаем номер x, то выполнить удаление совсем просто.
| L1 | Нам больше не нужен список последователей элемента x. Мы можем очистить этот список простым присваиванием |
| L2 | Нам требуется также обновить соответствующие элементы в массиве predecessor_count. Для каждого последователя y элемента x нужно уменьшить predecessor_count[y] на 1, так как в связи с удалением ограничения уменьшается число предшественников, и для выполнения операции потребуется обход списка, связанного с элементом x. Это будет делаться непосредственно в цикле, чей код появится ниже. Процесс будет выполняться самое большее один раз за всю обработку для каждого ограничения, так что он потребует времени O(m). Снова прекрасно! |
В целом операция Т3 требует времени O(m + n) в худшем случае.
Вся только что описанная обработка сопровождается инвариантами класса, выражающими тот факт, что массивы predecessor_count и
Рассмотрим теперь операцию Т2: "Для заданного элемента x удалить его из множества элементов". Фактически, для нашей новой структуры данных нам ничего не нужно делать. Выполняя Т3, мы уже позаботились обо всем, что нужно было сделать, удаляя ограничение, начинающееся с x. Отлично!
Осталась операция T1: "Найти элемент без предшественников – или уведомить об отсутствии такового". Для этого достаточно выполнить обход массива predecessor_count и найти элемент со значением 0. Но для этого понадобится время O(n), а для всех элементов $$O(n^2)$$. Это плохо!
Нам недостает еще одной структуры данных!
Нам не избежать O(n) обхода массива predecessor_count при инициализации (предложения from нашего главного цикла) для поиска первоначальных кандидатов – элементов без предшественников в исходном отношении. Если только не каждый элемент включен в цикл, то такие элементы найдутся. Это потребует O(n) времени, но выполнить эту операцию придется лишь один раз, так что пока все хорошо. По ходу процесса
— Уменьшить на единицу число предшественников y:
predecessor_count [y]:= predecessor_count [y] – 1
то теперь соответствующий код будет выглядеть так:
— Уменьшить на единицу число предшественников y
— и проверить, не становится ли y кандидатом:
predecessor_count [y]:= predecessor_count [y] – 1
[3]
if predecessor_count [y] = 0 then
"Записать, что y не имеет предшественников"
end
"Записать, что y не имеет предшественников" может быть реализовано как добавление в структуру candidates, которая будет заполняться при инициализации и пополняться по ходу обработки. Ее элементами являются еще не обработанные элементы, не имеющие предшественников. Какую конкретную структуру следует выбрать для candidates? Для алгоритма
feature — Access
item: G
— Получить ранее вставленный элемент.
require
not_empty: not is_empty
feature — Measurement
count: INTEGER
— Число элементов.
ensure
non_negative: Result >= 0
feature — Status report
is_empty: BOOLEAN
— Пуста ли структура?
ensure
definition: Result = (count = 0)
feature –- Element change
put (x: G)
— Вставить элемент x.
ensure
one_more: count = old count + 1
remove: G
— Удалить прочитанный элемент.
require
not_empty: not is_empty
ensure
one_fewer: count = old count – 1
Структуры данных с такими свойствами называются распределителями.
(рис 10.16) Распределитель
Как вы помните, основная идея распределителя в том, что не вы задаете, какой элемент будет получен и удален из распределителя, – стратегия задается типом распределителя. Стеки характеризуются политикой FIFO.
Для
Мы можем рассматривать распределитель кандидатов в виде:
candidates: PRIORITY_QUEUE [INTEGER]
— Элементы без предшественников, готовые к удалению
— Дополнительное предложение для инварианта:
— predecessor_count[x] = 0 для каждого элемента x из массива candidates
Реализация распределителя стеком или очередью (STACK или QUEUE) допустима, но очередь с приоритетами является более общим видом, где каждый элемент может сопровождаться приоритетом. В такой очереди элементы отсортированы по приоритетам, и операции item и remove выполняются для элемента с наибольшим приоритетом. Стек и очередь – это специальные случаи, когда приоритет задается порядком поступления элементов. Распределитель PRIORITY_QUEUE позволяет вам, играя приоритетами, управлять политикой выбора.
Мы можем теперь выписать главный цикл алгоритма x и y типа INTEGER и x_successors типа LIST[INTEGER], сохраняющего последователей конкретного элемента. Мы также добавим целочисленную переменную processed_count, используемую далее, чтобы сохранять историю того, как много элементов уже обработано.
from
create sorted. make
find_initial_candidates — Смотри далее
invariant
— "Структуры данных представляют подмножество исходных элементов
— и соответствующее подмножество исходного отношения"
until
candidates.is_empty
loop
— "Пусть x – элемент без предшественников в ограничениях"
x:= candidates.item; candidates.remove
sorted.extend (element_of_index [x])
— "Удалим x и все пары в ограничениях, начинающиеся с x"
x_successors:= successors [x] — список
from x_successors.start until x_successors. after loop
y:= x_successors. item
— Следующие несколько строчек взяты из [3]:
predecessor_count [ y]:= predecessor_count [y] – 1
if predecessor_count [ y] = 0 then
— "Записать, что теперь y не имеет предшественников"
candidates. put (y)
end
x_successors. forth end
processed_count:= processed_count + 1
variant
count – processed_count
end
report_cycles — Смотри далее
done:= True
Этот алгоритм предполагает, что массивы predecessor_count и process. Детали инициализации появятся чуть позже.
Процедура find_initial_candidates должна наполнить распределитель candidates элементами, изначально не имеющими предшественников. Она реализуется просто:
find_initial_candidates
— Поместите в массив элементы без предшественников.
local
x: INTEGER
do
if candidates = Void then create candidates end
from x:= 1 until x > count loop
if predecessor_count [x] = 0 then
candidates. put (x)
end
x:= x + 1
end
end
Это обход за время O(n). Без введения такого массива пришлось бы выполнять такой обход на каждом шаге цикла. Теперь достаточно выполнить его один раз в самом начале работы.
Не является ошибкой, если в процедуре не будут найдены элементы, удовлетворяющие условию predecessor_count[x] = 0. Это просто означает, что структура candidates пуста, что цикл завершится незамедлительно и что все элементы включены в какой-либо цикл.
Процедура process по завершении цикла должна выполнить еще одну важную часть работы – она должна уведомить клиента о циклах, встречающихся в отношении. Это и делается при вызове процедуры report_cycles. Чтобы ее реализовать, предварительно заметим, что цикл завершается, когда в массиве candidates не остается элементов. Если исходное отношение было processed_count, чтобы понять, остались ли элементы, и, если да, то сколько их:
report_cycles
— Сделать информацию о циклах доступной клиентам.
do
if processed_count < count then
— В исходном отношении есть цикл!!
cycle_found:= True
create {LINKED_LIST [G]} cyclists. make
from x:= 1 until x > count loop
if predecessor_count [x] /= 0 then
— x включен в цикл
cyclists. extend (element_of_index [x])
x:= x + 1
end
end
end
Мы достигли эффективной реализации за время O(m + n) ядра predecessor_count и candidates. Дополняя работу, следует убедиться, что инициализация не нарушает требуемых ограничений на время работы.
Инициализация должна выполнять:
record_element(e) для каждого элемента – всего n раз;record_constraint(e, f) для каждого ограничения – всего m раз.Работа record_element(e) состоит в том, чтобы присвоить номер элементу e, так чтобы в дальнейшей работе можно было бы использовать целые, а не сами элементы, имеющие тип G.
(рис 10.17) Массив и хеш-таблица
Это делается согласованным заполнением массива element_of_index и хэш-таблицы index_of_element, задающих взаимное отображение:
record_element (e: G)
— Добавить e в множество элементов, если там его еще нет.
require
not_sorted: not done
do
if not has_element (e) then
count:= count + 1
index_of_element. extend (count, e)
element_of_index. force (e, count)
—extend и force расширяют структуры при необходимости; это означает,
—что нам не требуется знать, сколь много элементов может появиться.
end
ensure
inserted: has_element (e)
one_more: not (old has_element (e)) implies (count = old count + 1)
end
Начальный тест должен убеждать, что процедура игнорирует повторную попытку вставки данного элемента. Эта политика позволяет record_constraint(e, f) стартовать, вызывая record_element как на e, так и на f, просто для того, чтобы убедиться, что элементы вставлены надлежащим образом. В упражнении вас попросят найти способ, позволяющий избежать дублирования работы между has_element и extend.
(рис 10.18) Добавление ограничения
При подходящей реализации extend и force код процедуры record_element выполняется за O(1), что для всех элементов дает время O(n). Это согласуется с нашими требованиями.
Оставшийся механизм инициализации дается процедурой для ввода ограничений. Вызов record_constraint(e, f) должен увеличивать на 1 число предшественников f в массиве predecessor_count и добавлять f в список последователей e. Этот список является одним из элементов массива
Вот текст процедуры:
record_constraint (e, f: G)
— Добавить ограничение [e, f]
require
not_sorted: not done
exist: e /= Void and f /= Void
local
x, y: INTEGER
do
— Убедиться, что e и f вставлены (нет эффекта, если они уже там присутствуют):
record_element (e); record_element (f )
x:= index_of_element [e]
y:= index_of_element [f ]
predecessor_count [ y]:= predecessor_count [ y] + 1
add_successor (x, y)
ensure
both_there: has_element (e) and has_element (f)
end
Дополнительная процедура, которую можно не экспортировать:
add_successor (x, y: INTEGER)
— Запись y как последователя x.
require
1 <= x; x <= count
1 <= y; y <= count
local
x_successors: LINKED_LIST [INTEGER]
do
x _successors:= successors [x]
— Список последователей для x может быть еще не создан:
if x_successors = Void then
create x_successors. make
successors [x]:= x_successors
end
x_successors. extend (y)
end
Как уже отмечалось, работа record_constraint начинается с двух вызовов record_element для пары аргументов, задаваемых в ограничении. Из-за способа проектирования record_element эффекта от вызова не будет, если элементы уже присутствовали. Эта политика делает возможным для клиентского приложения начинать непосредственно со списка ограничений, никогда явно не обращаясь к записи элементов.
record_element из интерфейса, доступного клиенту. Для некоторых вариантов задачи, о чем ранее говорилось, в исходном множестве элементов могут встречаться такие элементы, которые не входят ни в одно из ограничений. Понятно, что после Говоря о дублировании, заметим, что процедура record_constraint не пытается определить, встречалось ли уже вводимое ограничение. Можете убедиться, что алгоритм сортировки корректно будет работать и в случае, когда ограничение повторяется. Применение другой политики, запрещающей дублирование, возлагается на клиента, ответственного за ввод данных.
Вернемся к эффективности. Код каждой из двух дополнительных процедур выполняется за время O(1): доступ к элементу массива, запись в конец списка во втором случае (при хорошей организации списка с курсором в конце операция выполняется за константное время). Так что время работы record_constraint также задается O(1), а поскольку процедура должна отработать для каждого ограничения, в целом получаем O(m). Таким образом, достигнута наша цель: получить алгоритм, выполняющийся за время O(m + n) как на этапе инициализации, так и при выполнении основной задачи –
Мы уже познакомились со всеми элементами нашей программы, необходимыми для реализации
Напишите класс TOPOLOGICAL_SORTER, обеспечивающий универсальную, практичную
Убедитесь, что решение отвечает принципам инженерии программ, не только обеспечивает эффективный алгоритм, но и включает процедуры инициализации (record_element, record_constraint). Для тестирования решения используйте файл, доступный на сайте, который связан с курсом. Этот файл содержит несколько сотен ограничений и все возможные варианты
Из алгоритма
Мы уже рассматривали два стиля выполнения программ, написанных на некотором языке программирования S.
(рис 10.19) Интерпретация и компиляция программ
Как отмечалось, практическая реализация языков часто комбинирует оба подхода.
Эти концепции обобщаются на многие проблемные области, отличающиеся от выполнения программ, которые написаны на языках высокого уровня. Для выполнения некоторой обработки на некотором входе мы можем использовать структуры данных, которые непосредственно отображают вход, или можем разбить процесс обработки на два этапа.
Этот прием (который, как и при обработке языков, может и в общем случае включать несколько итераций процесса) в точности был применен для
В таком двухэтапном решении шаг "компиляции", инициализирующий структуры данных, может быть столь же сложным для проектирования, как и фактическая обработка, основанная на этих структурах, – он может требовать столь же много времени, а иногда и больше, чем время самой обработки. Этот подход хорош, если общая производительность соответствует вашим целям, но, конечно же, нельзя перепрыгивать к заключению о производительности алгоритма, не учитывая время инициализации, а не только самой обработки.
(рис 10.20) "Интерпретация" и "компиляция" данных
Подход может быть обобщен в виде эвристики – универсальной стратегии, подобной "образцу проектирования", но в существенно более абстрактной форме.
Хорошие алгоритмы часто создаются с использованием двухэтапной стратегии, где:
Мы увидим еще одно применение этой идеи при обсуждении архитектуры процесса проектирования, управляемого событиями.
Выбора тяжко бремя – память иль время!
Тесно связанным с эвристикой "Вначале компилируй данные" является наблюдение, что идеальная структура данных, та, которая наилучшим способом помогает реализации второго шага, часто не является наиболее экономичным по памяти представлением информации. В [x, y] ведет к тому, что y появится также в списке последователей x в массиве predecessor_count[y]. Если для заданного y ограничения отсутствуют, то это приводит к добавлению элемента в массив candidates. При таком представлении нам приходится жертвовать памятью для достижения требуемой по времени производительности. Компромиссы такого вида в ту или иную сторону – ключевые моменты проектирования эффективных алгоритмов.
Вполне возможно было бы привести описание алгоритма TOPOLOGICAL_SORTER. Экземпляр этого класса характеризует задачу process), но и весь инструментарий, необходимый клиенту для того, чтобы он мог:
process для выполнения Разница между этим подходом и чистым алгоритмом является частью разницы между программной инженерией и чистым программированием. В инженерии программ недостаточно спроектировать умный алгоритм и связанные с ним структуры данных. Целью становится подготовка решения, которое может быть интегрировано в успешные программные системы.
Наши решения должны допускать повторное использование, так что они не просто представляют "образцы проектирования", которые программист может интегрировать в свою систему, купив и прочитав книги (особенно выдающиеся книги, такие как эта, например). Решения должны быть реализованы как компоненты, доступные всегда и для всех, непосредственно доступные, а не стоящие на полках.
Вы также обратили внимание на то, как в этом процессе контракты позволяют нам точно знать, что нам следует делать, – что мы ожидаем, что гарантируется и что мы поддерживаем.
n элементов и m ограничений O(m + n) время, используя память того же порядка.| Acyclic | Antisymmetric | ||
| Asymmetric | Асимметричность | Binary relation | Бинарное отношение |
| Cycle | Цикл | Irreflexive | Иррефлексивность |
| Order relation | Отношение порядка | Partial order | |
| Relation | Отношение | Strict order | Строгий порядок |
| Topological sort | Total order | Тотальный или |
|
| Transitive closure |
Для обсуждения "<", заданное на числах. В некоторых задачах может быть более полезным иметь дело с нестрогим отношением, как отношение "<=" для чисел. Пара элементов связана нестрогим отношением x <= y, если и только если либо x < y, либо x = y. Общепринятое соглашение для "отношения порядка" предполагает нестрогую версию. В этой главе, так как мы использовали только строгое отношение порядка, слово "строгое" обычно опускалось, так что "порядок" означал "строгий порядок".
Для отношения
Еще одна проблема: является ли отношение тотальным или нет. Тотальность означает, что для любых пар различных элементов x и y имеет место одно из двух – либо x < y, либо y < x. Отношение порядка, удовлетворяющее этому свойству, называется тотальным порядком. Частичным порядком должно было бы называться отношение, которое не удовлетворяет этому свойству, такое, что для него найдется по крайней мере одна пара различных элементов, для которой ни [x, y], ни [y, x] не принадлежат отношению. Но не так определяется
Если же мы не знаем, каков порядок, или хотим включить оба случая – лучше применять термин "порядок". В случае неопределенности –использовать термин "возможно частичный порядок".
Дайте точные определения символам словаря.
Отношение порядка было определено как транзитивное и иррефлексивное. Было доказано, что следствием является асимметричность отношения. Докажите, что если отношение определяется как транзитивное и асимметричное, то следствием является иррефлексивность.
Докажите, что если отношение r является отношением строгого тотального порядка на конечном множестве, то существует единственное перечисление элементов, такое, что для любых элементов x и y элемент x появится перед y в перечислении, если и только если пара [x, y] принадлежит r.
Обсуждение в этой лекции строилось на строгом отношении порядка (частичном или полном), таком, как отношение "<" на числах – "меньше чем". Также возможно использовать нестрогое отношение порядка, такое, как "≤" – "меньше или равно". Определение строгого частичного порядка, которое мы будем называть отношением "<", хотя оно и не должно быть обычным отношением на числах, должно удовлетворять свойствам:
| О1 | иррефлексивности: | x < x не выполняется для любого x. |
| О2 | транзитивности: | из того, что x < y и y < z, следует x < z. |
Для этого отношения также выполняется свойство:
| О3 | асимметричности: | не могут одновременно иметь место x < y и y < x. |
Свойство О3 является следствием двух предыдущих свойств. Для частичного нестрогого отношения порядка "≤" имеют место три независимых свойства:
| N1 | рефлексивности: | x≤x для любого x. |
| N2 | транзитивности: | из того, что x≤y и y≤z, следует x≤z. |
| N3 | антисимметричности: | из того, что x≤y и y≤x, следует x = y. |
Для любого частичного строгого отношения порядка "<" существует связанное с ним нестрогое отношение "≤", определенное как
x ≤ y если и только если: x < y или x = y [4]
Справедливо и обратное утверждение: для любого частичного строгого отношения порядка "≤" существует связанное с ним строгое отношение "<", определенное как
x < y если и только если: x ≤ y и x ≠ y [5]
В этом упражнении требуется исследовать связь между этими ассоциированными отношениями – строгим "<" и нестрогим "≤"
Докажите теорему о
Объясните постусловие функции has_element.
В процедуре record_element проверяется, присутствует ли уже вставляемый элемент в таблице index_of_element, и запись осуществляется только в случае, когда такого элемента нет. В реализации используются две операции поиска – одна при вызове has_element, другая при вызове extend. Проанализируйте контрактную форму класса HASH_TABLE, найдите нужные компоненты, перепишите процедуры так, чтобы устранить эту небольшую неэффективность.
Постройте класс TOPOLOGICAL_SORTER в соответствии с обсуждением этой лекции.
(Это упражнение предполагает, что выполнено предыдущее)
Расширьте реализацию
Одна из тех радостей, что доставляет нам изучение информатики, – это знакомство с замечательными алгоритмами. В этой лекции мы займемся исследованием алгоритма, который обладает рядом достоинств, заслуживающих нашего внимания. Он полезен на практике, он, обладая хорошим математическим базисом, элегантен, он иллюстрирует технику решения задач, применимую в различных контекстах.
Познакомить вас с уже готовым решением неинтересно. Вместо этого мы начнем разрабатывать это решение шаг за шагом, как это делается для всякой научной проблемы. Мы начнем с постановки задачи, перейдем к ее математическому анализу, займемся поиском структуры данных, обеспечивающих корректность и эффективность решения. Мы не только спроектируем алгоритм, но, не останавливаясь на этом, получим полное инженерное решение, удовлетворяющее всем практическим требованиям. В конце лекции уроки этого примера позволят сформулировать некоторые общие принципы разработки алгоритмов и инженерии программ.
Вы решили сегодняшний день посвятить культуре: что может быть лучше, чем посещение Лувра и музея Орсе в Париже? Но для этого вам понадобится карта, и нужно приобрести проездной на метро, поскольку срок старого уже истек, но для проездного нужны деньги, так что придется зайти в банк или воспользоваться банкоматом. Можно выразить эти ограничения следующим образом:
[Map, Louvre], [Map, Orsay], [Pass, Louvre], [Pass, Orsay], [Money, Pass]
Здесь каждое ограничение задается парой [x, y], означающей, что "x должно случиться прежде чем y". Это можно отобразить графически:
(рис 10.1) Упорядочение ограничений
Топологической сортировкой множества элементов, подчиняющихся ограничениям порядка, называется перечисление элементов в порядке, удовлетворяющем ограничениям. В данном примере топологическими сортировками являются последовательности:
Money, Pass, Map, Louvre, Orsay
Map, Money, Pass, Orsay, Louvre
Money, Map, Pass, Louvre, Orsay
Заметьте: последовательность Pass, Money, Map, Louvre, Orsay некорректна, поскольку нарушается ограничение [Money, Pass].
Задача
[Orsay, Money], создавая тем самым цикл, то никакого решения больше существовать не будет, так как мы, с одной стороны, требуем, чтобы "утром – стулья, вечером – деньги", а с другой стороны, требуем "деньги вперед".Если существует более одного решения, то возникает проблема выбора одного из них. Обычно с любым решением связывается некоторая стоимость, тогда целью может быть поиск решения с минимальной стоимостью. Вскоре при анализе алгоритма мы увидим, где может применяться этот критерий при поиске нужного решения. Другой подход может состоять в том, чтобы найти все решения.
Задача
[B, A], [D, A], [D, C], [B, D], [E, C]. Здесь ограничение [x, y] содержательно означает "x не должно скрывать никакую часть y". Возможным решением является последовательность: B, D, E, A, C.
(рис 10.2) Прямоугольники с ограничением предшествования
Вот пример, дающий удобную визуализацию задачи. Рассмотрим точки на плоскости:
(рис 10.3) Конечное множество точек
Введем для точек $$p_1$$ с координатами $$(x_1, y_1)$$ и $$p_2$$ с координатами $$(x_2, y_2)$$ отношение $$\ll$$ ("строго меньше"), устанавливающее, что $$p_1 \ll p_2$$, если:
Для четырех точек, показанных на рисунке, справедливо следующее:
$$a\ll b\qquad\qquad a\ll d\qquad\qquad b\ll d\qquad\qquad c\ll d$$p « q, то в списке перечисления p предшествует q. Для наших четырех точек существуют три таких перечисления:
a, b, c, d
a, c, b, d
c, a, b, d
Три возможных обхода точек можно визуализировать:
(рис 10.4) Три типологических сортировки множества точек
С другой стороны, перечисление a, d, b, c не совместимо с отношением, поскольку свойство c « d требует, чтобы c предшествовало d.
Задача, обсуждаемая в этой главе, имеет точную математическую формулировку.
r требуется найти отношение полного порядка, для которого r является подмножеством.Это определение использует математические понятия – отношения как множества, ациклические отношения, отношения порядка (полного или частичного), которые теперь предстоит рассмотреть.
А (для простоты рассматривается только бинарное отношение) задается множеством пар в форме [x, y], где оба элемента пары являются элементами А.Примером отношения на множестве {1, 2, 3} является:
{[1, 2], [1, 3], [2, 3]}
Мы можем назвать это отношением < ("меньше", так как x и y принадлежат множеству {1, 2, 3} и x меньше y).
Мы можем использовать отношения для описания предыдущих примеров.
below (ниже) на множестве прямоугольников, содержащее все пары прямоугольников [x, y], таких, что в области наложения прямоугольников должны показываться точки y, а не x.before (прежде) – множество пар {[Map, Louvre], [Map, Orsey], …} – является отношением на множестве {Pass, Money, Map, Louvre, Orsay}, содержащим пары [x, y], такие, что событие x должно произойти раньше y.used_in ("используется в"), заданное на множестве терминов словаря, содержит все пары [x, y], такие, что определение термина y содержит термин x.called_by ("вызывается в"), заданное на множестве методов класса, содержит все пары [x, y], такие, что тело метода y содержит вызов метода x.« над точками – множество пар {[a, b], [a, d], [b, d], [c, d]}.Все наши примеры были до сих пор
Это определение следует дополнить.
r над множеством A является последовательность $$x_1,\;\ldots x_m (m\ge 2)$$ из элементов $$A$$, такая, что все последовательные пары $$[x_i,x_{i+1}]$$ для $$1\le i < m$$ принадлежат $$r$$, и $$x_m = x_1$$.Отношение before, введенное ранее, циклов не имеет:
(рис 10.5) Отношение, описывающее ограничение порядка
r встречается (при m = 2) для элемента x, такого, что [x, x] принадлежит r.Для успеха
r над непустым, конечным множеством А существует элемент x из А, не имеющий предшественника в r.y для отношения r является элемент x, такой, что пара [x, y] принадлежит r.Теорема доказывается от противного. Предположим противное, что каждый элемент в $$А$$ имеет по меньшей мере одного предшественника. Пусть $$x_1$$ – элемент из $$А$$ (он существует, так как множество не пусто). По предположению, у него есть хоть один предшественник, выберем любой и назовем его $$x_2$$. По тем же причинам есть предшественник $$x_3$$ и у $$x_2$$, так что в $$r$$ существует пара $$[x_3, x_2]$$. Продолжая вывод, следует признать существование
Доказательство конструктивно, и мы будем его использовать при проектировании алгоритма
Предположение о конечности множества $$А$$ существенно. Теорема неприменима к бесконечным множествам, например, отношение "меньше" для целых чисел в математике
Идея
x, y, z из множества X, на котором оно определено.
| О1 | Антирефлексивность: отношение не имеет пар вида [x,x]. |
| O2 | Транзитивность: из того, что отношению принадлежат пары [x, y] и [y, z], следует, что отношению принадлежит и пара [x, z]. |
Такое отношение порядка является также:
| О3 | асимметричным: из того, что отношению принадлежит пара [x, y] следует, что отношению не принадлежит пара [y, x]. |
(Доказательство. Если бы обе пары принадлежали отношению, то из транзитивности следовала бы рефлексивность – существование пары [x, x], что противоречит свойству
< – "строго меньше, чем". Также возможно работать с нестрогими версиями отношения, такими как отношение <= ("меньше или равно").Отношение "<" на {1, 2, 3} (или на любом другом множестве целых) является отношением порядка. Таким же является отношение « на точках. Наши другие ациклические отношения – before для задач, used_in для терминов, called_by для методов – антирефлексивны и асимметричны, но они не обязательно транзитивны, так что они не являются отношениями порядка. Вскоре мы увидим, как можно получить транзитивную версию.
Отношения порядка тесно связаны с
Доказательство от противного. Предположим, существует цикл $$x_1, x_2, \ldots x_n$$, где $$x_n$$ то же, что и $$x_1$$. По транзитивности это влечет рефлексивность, что противоречит
[x,y] и [y, x]. Такой случай является частным случаем цикла с двумя элементами. Подобно, пара [x, x], нарушающая антирефлексивность, является циклом с одним элементом.Здесь еще одно интересное свойство:
Это может быть проиллюстрировано на отношении before, выражающего ограничения порядка между задачами. Отношение антирефлексивно, асимметрично и ациклично, но оно не транзитивно, поскольку содержит пары [Money, Pass] и [Pass, Louvre], но не содержит пары [Money, Louvre]. Мы можем расширить отношение до транзитивного, добавив все пары вида [x, z], для которых в исходном отношении есть пары [x, y] и [y, z], выполняя эту операцию, пока добавление не перестанет быть возможным. Результатом этого процесса является
(рис 10.6) Транзитивное замыкание ограничений порядка
Для отношения called_by между процедурами x и y, если у вызывает x прямо или косвенно. Для отношения child между людьми, обозначающего множество пар [x, y], таких, что x является потомком y, r обозначается как $$r^+$$, так что мы можем полагать, что $$child^+ = descendant$$ (потомок представляет
Доказательство.
Этот результат позволяет нам рассматривать before между стоящими перед нами задачами, – если задача Money должна предшествовать задаче Pass, а задача Pass должна предшествовать задаче Louvre, то мы понимаем, что задача Money должна предшествовать задаче Louvre. Другими словами, мы инстинктивно принимаем
Вычисление
Для описания выхода
| О4 | Для любых a и b имеет место одно из следующих свойств:
[a, b] принадлежит r;[b, a] принадлежит r;a = b. |
Для понимания О4 заметьте: из
Отношение "<" на целых является тотальным отношением. Но не каждое отношение порядка является таковым. Отношение "«" на точках плоскости таковым не является, так как это означало бы, что для любых двух различных точек плоскости p1 и p2 должно выполняться p1 « p2 или p2 « p1.
(рис 10.7) Точки на плоскости и отношение полного порядка
Заметьте, пара точек [a, c] не принадлежит отношению, так как не верно, что a « c; точно так же неверно, что и c « a. Другим контрпримером является пара точек [b, c].
На множестве четырех точек можно установить различные отношения порядка, являющиеся полными. В частности, любое перечисление, в котором каждая точка появляется ровно один раз, можно рассматривать как задание полного порядка t. Вот как можно определить этот порядок: пара точек [p, q] принадлежит t, если и только если p предшествует q в перечислении. Например, перечисление [a, b, c, d] определяет
{[a, b], [a, c], [a, d], [1]
[b, c], [b, d],
[c, d]}
Верно и обратное: каждый
Такой тотальный порядок является топологической сортировкой исходного отношения "« ", если и только если тотальный порядок совместим с исходным. Совместимость означает, что когда p « q в исходном порядке, то p предшествует q в тотальном порядке.
(рис 10.8) Точки на плоскости и отношение «
Мы уже видели, что три тотальных порядка удовлетворяют этому требованию для нашего примера: соответствующими перечислениями являются a, b, c, d (в примере 10.1 представлено в виде множества пар); a, c, b, d и c, a, b, d.
Что означает "совместимость", если это понятие рассматривать более точно? Его нетрудно специфицировать, благодаря определению отношения как множества пар. Сказать, что тотальный порядок, заданный перечислением a, b, c, d, совместим с заданным « является множеством пар:
{[a, b], [a, d], [b, d], [c, d]} [2]
Это множество действительно является подмножеством множества пар (пример 6.1), задающего тотальный порядок. Это свойство выражает тот факт, что когда ограничение задает некоторый порядок между двумя элементами, то на
Так вырабатывается определение
Ациклические отношения имеют
Отсутствие циклов является очевидным необходимым условием существования
Справедлива следующая теорема.
r над конечным множеством А существует тотальное отношение порядка t над А, такое, что $$r\subseteq t$$Для доказательства этой теоремы можно было бы использовать то наблюдение, что $$r\subseteq r^+$$, где $$r^+$$ – это r, и предыдущее доказательство того, что $$r^+$$ является отношением порядка. Этого достаточно, чтобы расширить $$r^+$$ до полного отношения порядка. Но для наших целей более интересно другое доказательство. Это конструктивное доказательство (основанное на теореме об отсутствии предшественника), позволяющее нам непосредственно получить схему алгоритма.
Доказательство ведется индукцией по числу элементов n множества A. Если n = 0, множество пусто, единственно возможным отношением является пустое отношение (пустое множество пар элементов из A), которое является полным порядком. Это доказывает
Если вы предпочитаете иное, в качестве базиса можно выбрать случай n = 1, для которого A состоит из одного элемента x. Хотя теперь A не пусто, единственное A снова является пустым отношением, так как единственная пара [x, x], которую можно создать, образует цикл.
n элементов, и рассмотрим n + 1 элементов. Рисунок поясняет идею доказательства:(рис 10.9) Расширение, дополняющее топологическую сортировку
Теорема об отсутствии предшественника говорит нам, что А имеет по крайней мере один элемент, не имеющий предшественника. Пусть x – такой элемент. Пусть А' – множество элементов А за исключением x. Пусть r' – отношение на А', содержащее все пары из r, за исключением тех, что содержат x. Очевидно, что r' является A'. По предположению индукции, так как A' имеет n элементов, существует t' над A', совместимый с r' (это то же самое, что сказать $$r^\prime\subseteq t^\prime$$). Теперь рассмотрим отношение t над A, состоящее из следующих пар:
t';[x, y], где y – элемент из A'.t как перечисление элементов A, которое начинается с x и продолжается перечислением A', заданным t'.Нетрудно видеть, что t – это r, что и доказывает теорему.
Теорема о
С теоретическими основами все ясно, так что можно приступать к поиску инженерного решения. Ядром является алгоритм
Что можно сказать об ожидаемой емкостной и временной сложности алгоритма?
Входом для алгоритма является множество элементов и множество ограничений. Обозначим через n число элементов, m – число ограничений.
Алгоритм должен (в случае
Так что наилучшее время, на которое можно надеяться, – это O(n + m).
Самое удивительное, что разрабатываемый ниже алгоритм
Чисто алгоритмическое решение могло бы использовать функцию в форме:
topologically_sorted (elements:…; constraints:…): LIST[…]
— Перечисление элементов множества elements
— в порядке, совместимом с множеством ограничений constraints.
Предполагается, что входные типы позволяют задать множества элементов и ограничений – elements и costraints, соответствующие нашим прежним обозначениям A и r.
Лучшее решение – как покажет дальнейшая разработка – дает ОО-подход с построением класса TOPOLOGICAL_SORTED, любой экземпляр которого представляет задачу record_element и record_constraint.
Вместо функции topologically_sorted, как выше, будем иметь в классе:
process, выполняющую процесс sorted, который возвращает список элементов, созданный при работе процедуры process.Этот каркас даст нам больше гибкости, и мы получим возможность дополнить его многими полезными свойствами.
Множества элементов A и ограничений r могут поступать из различных источников. Например, мы могли бы иметь файл, перечисляющий ограничения, каждое из которых задается одной строкой файла:
Map Louvre
Map Orsay
Pass Louvre
Pass Orsay
Money Pass
(рис 10.10) Элементы и ограничения
Возможно, было бы полезно иметь отдельный файл, перечисляющий все элементы или, по меньшей мере, элементы, не включенные ни в одно из ограничений (мы не можем догадаться о существовании таких элементов, анализируя ограничения, но они должны быть частью вывода).
В других условиях ввод мог бы осуществляться интерактивно, используя программу или Web-форму. В примерах, таких как упорядочение прямоугольников, отображаемых на экране, упорядочение терминов словаря или методов класса, формат данных будет различным.
Для обеспечения общности сделаем наш базовый класс универсальным: TOPOLOGICAL_SORTED[G], где параметр G задает тип элементов. Тогда результат запроса sorted, который обозначает топологически отсортированный список элементов, созданный в process, имеет тип LIST[G]. Две процедуры инициализации, о которых говорилось выше, имеют сигнатуры:
record_element (e: G)
record_constraint (e, f: G)
Рассмотрим r на множестве элементов A. Так как нам необходимы имена, используемые в программе, то позвольте полагать, не предрешая выбор реализации, что класс TOPOLOGICAL_SORTED имеет доступные запросы elements и constraints. Общая схема для алгоритма process такова:
from …until elements.is_empty loop
"Пусть x – элемент без предшественников в ограничениях"
"Рассматривать x как следующий элемент sorted"
"Удалить x из множества элементов"
"Удалить все пары, начинающиеся x, из множества ограничений)"
end
Уточненная нужным образом эта форма будет работать при условии, что мы начинаем с
Теоремы о
process
— Выполняет в sorted перечисление элементов множества elements
— в порядке, совместимом с множеством ограничений constraints.
require
— "constraints описывают ациклическое отношение"
do
from
create {….} sorted. make
invariant
— "constraints описывают ациклическое отношение"
until
elements. is_empty
loop — Как и ранее, за тем исключением, что явно используется результат sorted:
"Пусть x – элемент без предшественников в ограничениях"
sorted. extend (x)
"Удалить x из множества элементов"
"Удалить все пары, начинающиеся x, из множества ограничений"
variant
elements. count
end
ensure
— "sorted представляет топологическую сортировку elements, согласованную
— с constraints"
end
Версия схемы алгоритма, в принципе, корректна, но не подходит для большинства приложений, встречающихся в реальной жизни.
Проблема в предусловии, требующем, чтобы на вход было подано [Map, Louvre] или [Map, Orsey], как выше. Такой вход может готовиться человеком, а ему свойственно ошибаться, и он имеет право на ошибку, что недопустимо в программе (при рассмотрении сборки промышленных изделий могут встречаться тысячи узлов и десятки тысяч ограничений между ними, задающих порядок сборки).
В примере с терминами словаря мы не можем надеяться, что не встретятся два или более термина, ссылающихся друг на друга в своих определениях (следовательно, создающих циклы), но у нас нет способа принуждать авторов словаря. Справедливо обратное – автор может требовать от программы: "Упорядочьте в словаре термины так, чтобы определение термина встречалось раньше его использования. Но, кстати, если вы обнаружите взаимные ссылки терминов, сообщите мне о них, чтобы я мог скорректировать определения".
Аналогично задача упорядочения методов класса, чтобы определение метода предшествовало его вызову, невозможна в случае
Эти рассмотрения приводят к изменениям контракта метода process, более благосклонного к своим клиентам. Прежний контракт:
require
— "constraints описывают ациклическое отношение"
ensure
— "sorted представляет топологическую сортировку elements,
— согласованную с constraints"
заменяется новым, более реалистичным контрактом:
— (Нет предусловия)
ensure
— "sorted представляет топологическую сортировку, согласованную
— с constraints, для всех членов elements, не входящих в цикл"
Этого все же недостаточно. Класс должен предоставлять своим клиентам отчет о возникающих циклах и указывать, какие элементы в них включены. Одним из способов обеспечения такой функциональности является введение булевской функции.
has_cycle: BOOLEAN
— Содержат ли циклы отношение, заданное elements и constraints?
do …end
Говоря неформально, нужна функция, которая будет возвращать список элементов, включенных в цикл (void, если и только если has_cycle имеет значение false). Концептуально это звучит разумно, но это не лучший способ, так как вычислительно представляет дорогое решение. Нахождение циклов – задача функции has_cycle, фактически является столь же трудной по времени и памяти, как и сама задача
Теорема об отсутствии предшественника подсказывает нам, что цикл можно найти как побочный бонус процесса
Рассматриваемая далее программа
Вместо прежнего инварианта:
—"constraints описывают ациклическое отношение на elements"
будем теперь использовать его ослабленную форму:
—"constraints описывают подмножество исходного отношения на elements"
Отсюда следует, что
—"Любой цикл в constraints присутствует в исходном отношении"
а также:
—"constraints описывает ациклическое отношение, если исходное отношение ациклично".
Это та основа, которой мы будем придерживаться. Как следствие, мы больше не будем использовать в качестве условия выхода из цикла elements.is_empty, как ранее, так как непустое множество elements не гарантирует больше, что можно корректно выполнить оператор:
"Пусть x – элемент без предшественников в ограничениях"
В качестве нового условия выхода будем иметь:
"Нет элементов без предшественников в ограничениях"
Отрицание этого условия означает, что есть по крайней мере один элемент без предшественников, – а это гарантия того, что в теле цикла можно найти очередного кандидата, включаемого в результат выхода.
Мы можем теперь определить полную форму класса, который будет служить каркасом нашего решения:
class
TOPOLOGICAL_SORTER [G –> HASHABLE]
feature {NONE} — Внутренние структуры данных
…Смотри следующие разделы этой главы…
feature — Инициализация
record_element (a: G)
— Включить а в множество элементов.
require
not_sorted: not done
do
…Смотри следующие разделы…
end
record_constraint (a, b: G)
— Включить [a, b] в ограничения.
require
not_sorted: not done
do
…Смотри следующие разделы…
end
feature — Status report
done: BOOLEAN
— Выполнена ли топологическая сортировка?
feature — Element change
process
— Выполнить топологическую сортировку над всеми применимыми элементами.
— Результаты доступны через sorted, cycle-found и cyclists.
require
not_sorted: not done
do
…Смотри следующие разделы…
ensure
sorted: done
end
feature — Access
cycle_found: BOOLEAN
— Исходное ограничение приводит ли к циклу?
cyclists: LIST [G]
— Элементы, включенные в какой-либо цикл.
sorted: LIST [G]
— Список из всех элементов, которые допускают упорядочивание,
— согласованное с ограничениями
feature — Status setting
reset
— Допустить дальнейшее обновление элементов и ограничений.
do
done:= False
cycle_found:= False; cyclists:= Void; processed_count:= 0
ensure
fresh: not done
end
invariant
elements_exist: elements /= Void
constraints_exist: constraints /= Void
cyclists_only_if_cycle: done implies (cycle_found = (cyclists /= Void))
end
Класс является универсальным, его родовой параметр G представляет тип элементов. Запись G -> означает, что мы "ограничиваем" G (понятие, вводимое в следующей главе) типом
Алгоритм будет основываться на внутренних структурах данных, проектируемых в следующих разделах этой главы. Поскольку соответствующие методы создаются для внутреннего использования, они не будут доступны клиентам класса и потому объявлены как feature {NONE}.
Сразу же после того, как метод process выполнит свою работу, его результаты будут доступны клиентам через несколько связанных запросов.
done, позволяющий клиентам выяснить, выполнена ли false.sorted, дает порядок, совместимый со всеми ограничениями, и включает все элементы, не входящие в цикл.Булевский запрос cycle_found показывает, что есть элементы, включенные в какой-либо цикл.
cyclists. Предложение инварианта cyclists_only_if_cycle говорит нам, что запрос имеет смысл только при условии истинности cycle_found.Клиент, желающий выполнить
your_structure: TOPOLOGICAL_SORTER [YOUR_ELEMENT_TYPE]
…
create your_structure
…Вызовы вида your_structure.record_element(x) для записи элементов …
…и your_structure.record_constraint(x, y) для записи ограничений…
your_structure. process
— Теперь становятся доступными результаты топологической сортировки
— your_structure.sorted
if your_structure. cycle_found then
— Теперь становятся доступными элементы, включенные в цикл
— your_structure.cyclists …
end
Было бы желательно для согласованности поставлять запросы sorted, cycle_found и cyclists с предусловием done, но мы временно будем опускать предусловие.
Однако предусловие not done задано для процедур инициализации record_element и record_constraint, так же как и для процедуры process, имеющей постусловие done. Как результат, попытка повторного вызова процедуры process на одном и том же экземпляре класса будет приводить к ошибке. Конечно, запросы можно вызывать сколь угодно много раз. Процедура reset добавлена на случай, когда вы хотите явно добавлять элементы и ограничения уже после вызова process для подготовки нового его вызова.
Процедура reset просто устанавливает done равным false, не производя очистки предыдущих элементов и ограничений. Мы можем добавить процедуру forget, которая вызовет reset и очистит структуры данных. Но в этом случае клиенту проще создать новый экземпляр TOPOLOGICAL_SORTER.
Теперь мы можем приступить к полной реализации ключевой части нашего решения – процедуре process.
Общий алгоритм этого метода уже написан, осталось адаптировать его с учетом всех сделанных уточнений (ослабление инварианта, использование метода sorted, представляющего результат в TOPOLOGICAL_SORTER). В результате получаем:
from
create {…} sorted. make
until
"Нет элемента без предшественников"
Loop
"Пусть x — элемент без предшественников"
sorted. extend (x)
"Удалить x из множества элементов"
Удалить все ограничения, начинающиеся с x
end
if "остался хоть один элемент" then — Отчет о цикле:
cycle_found:= True
"Вставьте эти элементы в cyclists"
end
Все, что осталось, – но не спешите слишком радоваться, главные трудности еще впереди, – это уточнить
| Т1 | Найти элемент без предшественников – или отчитаться об отсутствии такового. |
| Т2 | Для заданного элемента x удалить его из множества элементов. |
| Т3 | Для заданного элемента x удалить из множества ограничений все ограничения, начинающиеся этим элементом (все пары вида [x, y]). |
Мы должны найти такие представления данных (множеств элементов и ограничений), которые делают эти операции эффективными, насколько это возможно. Структуры данных будут появляться как закрытые компоненты класса в разделах, резервированных для этих целей.
Приведенная выше схема класса оставила незаполненными тела двух методов класса: add_element и add_constraint. Нам предстоит дополнить методы, основываясь на структурах данных, которые мы сейчас спроектируем.
Для нашей первой попытки построения структуры данных естественно выбрать представление, которое непосредственно моделирует входные данные в том виде, как они к нам приходят (наш небольшой опыт в изучении программирования говорит, что не следует утверждать, что некоторое решение является "естественным". То, что кажется естественным мне, вовсе может не казаться таковым для вас, а то, что естественно для меня и для вас, может оказаться довольно посредственным решением).
Чаще всего входные данные могли бы поступать в виде списка элементов и списка ограничений. Мы могли бы использовать атрибуты класса, которые непосредственно отображают эти структуры данных (сделав их закрытыми для клиентов, размещая их в секции feature {NONE}):
elements: LINKED_LIST [G]
constraints: LINKED_LIST [TUPLE [G, G]]
В нашем примере структуры данных будут выглядеть подобным образом:
(рис 10.11) Элементы и ограничения
Для простоты предполагается, что мы присвоили номера нашим элементам следующим образом (рис 10.12).
(рис 10.12) Нумерация элементов
Можем ли мы реализовать при таком представлении данных операции Т1, Т2, Т3 и процедуры record_element и record_constaint, и если да, то какова цена решения – сложность по времени и по памяти?
Две процедуры реализуются непосредственно. Например, для выполнения record_constaint достаточно вызывать стандартный метод:
constraints. extend ([x, y])
Новая пара [x,y] добавится в конец списка ограничений. Подобным образом record_element(x) реализуется вызовом elements.extend(x).
elements и constaints имеют значения, отличные от void. Соответствующие операторы создания create могут появляться в форме default_create или вызываться по требованию, когда в них возникает необходимость. Все это справедливо и для других структур данных, рассматриваемых ниже.Это представление можно использовать и при реализации других операций. Давайте проанализируем их стоимость, когда у нас есть n элементов и m ограничений.
constaints и считать предшественников для каждого элемента, затем обойти список элементов для поиска тех, у кого число предшественников равно нулю. Первый обход потребует $$O(m)$$ операций, второй – $$O(n)$$, и поскольку это нужно делать на каждом шаге, в целом понадобится операций $$O(n^*m + n^2)$$.В практических приложениях следует ожидать, что для каждого элемента задается несколько ограничений, так что $$m > n$$, а потому $$O(m^*n)$$ хуже, чем $$O(n^2)$$. Поскольку в реальных задачах $$n$$ может быть велико, сложность $$O(n^2)$$ представляется неприемлемо высокой.
Так что наш первый выбор структуры данных дает решение задачи, но его производительность не позволяет построить масштабируемое приложение, пригодное для задач большой размерности.
К счастью, мы можем найти решение лучшее, чем "естественное". Как показывает опыт, мы не всегда должны использовать структуры данных в том виде, как они к нам приходят. Списки elements и constraints – это непосредственное отражение данных внешнего мира, естественного представления данных человеком, который вводит задачи и описывает ограничения между задачами. Но форма данных, простая и естественная для внешнего мира, вовсе не является лучшей формой для алгоритма, предназначенного для обработки этих данных некоторым специальным образом. Вместо того чтобы слепо следовать форме приходящих данных, алгоритм может начинаться с этапа инициализации, который преобразует данные в формат, наилучшим образом приспособленный к их обработке.
Следующие структуры данных помогают выполнить работу
successors: ARRAY [LINKED_LIST [INTEGER]]
— Индексами массива являются номера элементов. Для каждого элемента x
— задается список его непосредственных последователей – элементов y,
— таких, что есть ограничение [x, y].
predecessor_count: ARRAY [INTEGER]
— Индексами массива являются номера элементов.
— Для каждого элемента x указывается число его непосредственных
— предшественников.
Следующий рисунок иллюстрирует представление данных для нашего примера.
(рис 10.13) Число предшественников и список последователей
На следующем рисунке приведена уже хорошо нам знакомая схема, где введена нумерация элементов. Она поясняет предыдущий рисунок. По схеме ясно, что, например, у задачи 1 предшественников нет, но есть два последователя, а у задачи 5 – один предшественник и те же два последователя (2 и 4).
(рис 10.14) Знакомая схема с нумерацией элементов
В этом представлении интересно то, что массив, задающий число предшественников, является избыточным, поскольку всю хранимую в нем информацию можно извлечь из массива последователей. Но ничего ошибочного в таком представлении информации нет, поскольку, как мы увидим, за счет этого дублирования можно добиться существенного улучшения времени вычислений.
Нахождение компромисса память-время является ключевой составляющей проектирования хорошего алгоритма. Конечно, компромисс должен быть приемлемым. В данном случае наша цель — получить алгоритм с временной сложностью O(m + n), сохраняя ту же сложность и для памяти, требуемой для хранения данных. Такая память нужна для хранения массива predecessor_count с емкостью O(n) не меняет
Исходные структуры данных – elements и constraints – также требуют памяти O(m + n).
Удобно для пущей ясности добавить запрос, доступный клиентам:
count: INTEGER
— Число элементов
Также полезно для улучшения читабельности добавить инварианты класса. Два последних предложения выражены неформально:
elements.count = count
predecessor_count. count = count
successors.count = count
— Для каждого i из интервала 1..count элемент predecessor_count[i]
— задает число предшественников i-го элемента для заданных ограничений.
— Для каждого i из интервала 1..count элемент successors[i]
— задает список всех последователей i-го элемента для заданных ограничений
— или void, если последователей нет.
Чтобы использовать массив, нужно некоторым образом пронумеровать наши элементы. Ранее это было сделано в интересах удобства обращения. Теперь это становится необходимостью, связанной с нашим выбором структуры данных.
Значит ли это, что теперь требуется изменить родовой параметр класса TOPOLOGICAL_SORTER[G], поскольку все манипуляции над элементами будут теперь использовать их целочисленные номера? Абсолютно нет. Остается необходимым для выразительности создать механизм, применимый к элементам любого типа. На практике для этого потребуется хэш-таблица и массив:
index_of_element: HASH_TABLE [INTEGER, G]
— Для каждого элемента дает его индекс
element_of_index: ARRAY [G]
— Для каждого индекса дает ассоциированный с ним элемент
Элемент хэш-таблицы index_of_element[e] дает целое x – индекс элемента e типа G. В свою очередь, element_of_index[x] = e.
В обоих случаях используется нотация с квадратными скобками.
(рис 10.15) Взаимное отображение элементов и индексов
Обе эти структуры при разумной реализации требуют памяти O(n).
Для определения хэш-таблицы с элементами типа G требуется, чтобы тип G удовлетворял G -> (ограниченная универсальность будет подробно рассматриваться в следующей главе, сейчас же понятно, что элементы должны допускать построение хэш-функции).
Класс TOPOLOGICAL_SORTER[G -> не будет экспортировать компоненты index_of_element и element_of_index, так как они необходимы только для целей реализации, но мы должны позволять клиентам находить элементы, поскольку это является частью общей задачи работы с элементами, поэтому мы будем экспортировать запрос:
has_element (e: G): BOOLEAN
— Является ли e одним из элементов топологической сортировки?
do
Result:= index_of_element. has (e)
ensure
consistent: Result = index_of_element.has (e) and then
index_of_element [e] >= 1 and then
index_of_element [e] <= element_of_index. count and then
element_of_index [index_of_element [e]] = e
end
Убедитесь, что вы понимаете постусловие.
Давайте теперь докажем, что новые структуры данных позволяют добиться нашей цели – времени O(m + n). Необходимо рассмотреть два аспекта: выполнение операций Т1-Т3 и затраты на инициализацию – создание структур данных predecessor_count и O(m + n), но для создания структур требовалось бы $$O(m^*n)$$ времени, то в целом никакого выигрыша мы бы не получили.
Представляется, что несложно реализовать построение требуемых структур данных за время O(m + n). Обрабатывая последовательно каждое ограничение [x, y], зная y, можно увеличить на 1 значение соответствующего элемента predecessor_count, а зная x, можно добавить последователя y в список соответствующего элемента O(m + n) возможно и сосредоточимся на рассмотрении операций Т1-Т3.
Начнем с Т3: "Для заданного элемента x удалить из множества ограничений все ограничения, начинающиеся этим элементом (все пары вида [x, y])". Если мы знаем номер x, то выполнить удаление совсем просто.
| L1 | Нам больше не нужен список последователей элемента x. Мы можем очистить этот список простым присваиванием |
| L2 | Нам требуется также обновить соответствующие элементы в массиве predecessor_count. Для каждого последователя y элемента x нужно уменьшить predecessor_count[y] на 1, так как в связи с удалением ограничения уменьшается число предшественников, и для выполнения операции потребуется обход списка, связанного с элементом x. Это будет делаться непосредственно в цикле, чей код появится ниже. Процесс будет выполняться самое большее один раз за всю обработку для каждого ограничения, так что он потребует времени O(m). Снова прекрасно! |
В целом операция Т3 требует времени O(m + n) в худшем случае.
Вся только что описанная обработка сопровождается инвариантами класса, выражающими тот факт, что массивы predecessor_count и
Рассмотрим теперь операцию Т2: "Для заданного элемента x удалить его из множества элементов". Фактически, для нашей новой структуры данных нам ничего не нужно делать. Выполняя Т3, мы уже позаботились обо всем, что нужно было сделать, удаляя ограничение, начинающееся с x. Отлично!
Осталась операция T1: "Найти элемент без предшественников – или уведомить об отсутствии такового". Для этого достаточно выполнить обход массива predecessor_count и найти элемент со значением 0. Но для этого понадобится время O(n), а для всех элементов $$O(n^2)$$. Это плохо!
Нам недостает еще одной структуры данных!
Нам не избежать O(n) обхода массива predecessor_count при инициализации (предложения from нашего главного цикла) для поиска первоначальных кандидатов – элементов без предшественников в исходном отношении. Если только не каждый элемент включен в цикл, то такие элементы найдутся. Это потребует O(n) времени, но выполнить эту операцию придется лишь один раз, так что пока все хорошо. По ходу процесса
— Уменьшить на единицу число предшественников y:
predecessor_count [y]:= predecessor_count [y] – 1
то теперь соответствующий код будет выглядеть так:
— Уменьшить на единицу число предшественников y
— и проверить, не становится ли y кандидатом:
predecessor_count [y]:= predecessor_count [y] – 1
[3]
if predecessor_count [y] = 0 then
"Записать, что y не имеет предшественников"
end
"Записать, что y не имеет предшественников" может быть реализовано как добавление в структуру candidates, которая будет заполняться при инициализации и пополняться по ходу обработки. Ее элементами являются еще не обработанные элементы, не имеющие предшественников. Какую конкретную структуру следует выбрать для candidates? Для алгоритма
feature — Access
item: G
— Получить ранее вставленный элемент.
require
not_empty: not is_empty
feature — Measurement
count: INTEGER
— Число элементов.
ensure
non_negative: Result >= 0
feature — Status report
is_empty: BOOLEAN
— Пуста ли структура?
ensure
definition: Result = (count = 0)
feature –- Element change
put (x: G)
— Вставить элемент x.
ensure
one_more: count = old count + 1
remove: G
— Удалить прочитанный элемент.
require
not_empty: not is_empty
ensure
one_fewer: count = old count – 1
Структуры данных с такими свойствами называются распределителями.
(рис 10.16) Распределитель
Как вы помните, основная идея распределителя в том, что не вы задаете, какой элемент будет получен и удален из распределителя, – стратегия задается типом распределителя. Стеки характеризуются политикой FIFO.
Для
Мы можем рассматривать распределитель кандидатов в виде:
candidates: PRIORITY_QUEUE [INTEGER]
— Элементы без предшественников, готовые к удалению
— Дополнительное предложение для инварианта:
— predecessor_count[x] = 0 для каждого элемента x из массива candidates
Реализация распределителя стеком или очередью (STACK или QUEUE) допустима, но очередь с приоритетами является более общим видом, где каждый элемент может сопровождаться приоритетом. В такой очереди элементы отсортированы по приоритетам, и операции item и remove выполняются для элемента с наибольшим приоритетом. Стек и очередь – это специальные случаи, когда приоритет задается порядком поступления элементов. Распределитель PRIORITY_QUEUE позволяет вам, играя приоритетами, управлять политикой выбора.
Мы можем теперь выписать главный цикл алгоритма x и y типа INTEGER и x_successors типа LIST[INTEGER], сохраняющего последователей конкретного элемента. Мы также добавим целочисленную переменную processed_count, используемую далее, чтобы сохранять историю того, как много элементов уже обработано.
from
create sorted. make
find_initial_candidates — Смотри далее
invariant
— "Структуры данных представляют подмножество исходных элементов
— и соответствующее подмножество исходного отношения"
until
candidates.is_empty
loop
— "Пусть x – элемент без предшественников в ограничениях"
x:= candidates.item; candidates.remove
sorted.extend (element_of_index [x])
— "Удалим x и все пары в ограничениях, начинающиеся с x"
x_successors:= successors [x] — список
from x_successors.start until x_successors. after loop
y:= x_successors. item
— Следующие несколько строчек взяты из [3]:
predecessor_count [ y]:= predecessor_count [y] – 1
if predecessor_count [ y] = 0 then
— "Записать, что теперь y не имеет предшественников"
candidates. put (y)
end
x_successors. forth end
processed_count:= processed_count + 1
variant
count – processed_count
end
report_cycles — Смотри далее
done:= True
Этот алгоритм предполагает, что массивы predecessor_count и process. Детали инициализации появятся чуть позже.
Процедура find_initial_candidates должна наполнить распределитель candidates элементами, изначально не имеющими предшественников. Она реализуется просто:
find_initial_candidates
— Поместите в массив элементы без предшественников.
local
x: INTEGER
do
if candidates = Void then create candidates end
from x:= 1 until x > count loop
if predecessor_count [x] = 0 then
candidates. put (x)
end
x:= x + 1
end
end
Это обход за время O(n). Без введения такого массива пришлось бы выполнять такой обход на каждом шаге цикла. Теперь достаточно выполнить его один раз в самом начале работы.
Не является ошибкой, если в процедуре не будут найдены элементы, удовлетворяющие условию predecessor_count[x] = 0. Это просто означает, что структура candidates пуста, что цикл завершится незамедлительно и что все элементы включены в какой-либо цикл.
Процедура process по завершении цикла должна выполнить еще одну важную часть работы – она должна уведомить клиента о циклах, встречающихся в отношении. Это и делается при вызове процедуры report_cycles. Чтобы ее реализовать, предварительно заметим, что цикл завершается, когда в массиве candidates не остается элементов. Если исходное отношение было processed_count, чтобы понять, остались ли элементы, и, если да, то сколько их:
report_cycles
— Сделать информацию о циклах доступной клиентам.
do
if processed_count < count then
— В исходном отношении есть цикл!!
cycle_found:= True
create {LINKED_LIST [G]} cyclists. make
from x:= 1 until x > count loop
if predecessor_count [x] /= 0 then
— x включен в цикл
cyclists. extend (element_of_index [x])
x:= x + 1
end
end
end
Мы достигли эффективной реализации за время O(m + n) ядра predecessor_count и candidates. Дополняя работу, следует убедиться, что инициализация не нарушает требуемых ограничений на время работы.
Инициализация должна выполнять:
record_element(e) для каждого элемента – всего n раз;record_constraint(e, f) для каждого ограничения – всего m раз.Работа record_element(e) состоит в том, чтобы присвоить номер элементу e, так чтобы в дальнейшей работе можно было бы использовать целые, а не сами элементы, имеющие тип G.
(рис 10.17) Массив и хеш-таблица
Это делается согласованным заполнением массива element_of_index и хэш-таблицы index_of_element, задающих взаимное отображение:
record_element (e: G)
— Добавить e в множество элементов, если там его еще нет.
require
not_sorted: not done
do
if not has_element (e) then
count:= count + 1
index_of_element. extend (count, e)
element_of_index. force (e, count)
—extend и force расширяют структуры при необходимости; это означает,
—что нам не требуется знать, сколь много элементов может появиться.
end
ensure
inserted: has_element (e)
one_more: not (old has_element (e)) implies (count = old count + 1)
end
Начальный тест должен убеждать, что процедура игнорирует повторную попытку вставки данного элемента. Эта политика позволяет record_constraint(e, f) стартовать, вызывая record_element как на e, так и на f, просто для того, чтобы убедиться, что элементы вставлены надлежащим образом. В упражнении вас попросят найти способ, позволяющий избежать дублирования работы между has_element и extend.
(рис 10.18) Добавление ограничения
При подходящей реализации extend и force код процедуры record_element выполняется за O(1), что для всех элементов дает время O(n). Это согласуется с нашими требованиями.
Оставшийся механизм инициализации дается процедурой для ввода ограничений. Вызов record_constraint(e, f) должен увеличивать на 1 число предшественников f в массиве predecessor_count и добавлять f в список последователей e. Этот список является одним из элементов массива
Вот текст процедуры:
record_constraint (e, f: G)
— Добавить ограничение [e, f]
require
not_sorted: not done
exist: e /= Void and f /= Void
local
x, y: INTEGER
do
— Убедиться, что e и f вставлены (нет эффекта, если они уже там присутствуют):
record_element (e); record_element (f )
x:= index_of_element [e]
y:= index_of_element [f ]
predecessor_count [ y]:= predecessor_count [ y] + 1
add_successor (x, y)
ensure
both_there: has_element (e) and has_element (f)
end
Дополнительная процедура, которую можно не экспортировать:
add_successor (x, y: INTEGER)
— Запись y как последователя x.
require
1 <= x; x <= count
1 <= y; y <= count
local
x_successors: LINKED_LIST [INTEGER]
do
x _successors:= successors [x]
— Список последователей для x может быть еще не создан:
if x_successors = Void then
create x_successors. make
successors [x]:= x_successors
end
x_successors. extend (y)
end
Как уже отмечалось, работа record_constraint начинается с двух вызовов record_element для пары аргументов, задаваемых в ограничении. Из-за способа проектирования record_element эффекта от вызова не будет, если элементы уже присутствовали. Эта политика делает возможным для клиентского приложения начинать непосредственно со списка ограничений, никогда явно не обращаясь к записи элементов.
record_element из интерфейса, доступного клиенту. Для некоторых вариантов задачи, о чем ранее говорилось, в исходном множестве элементов могут встречаться такие элементы, которые не входят ни в одно из ограничений. Понятно, что после Говоря о дублировании, заметим, что процедура record_constraint не пытается определить, встречалось ли уже вводимое ограничение. Можете убедиться, что алгоритм сортировки корректно будет работать и в случае, когда ограничение повторяется. Применение другой политики, запрещающей дублирование, возлагается на клиента, ответственного за ввод данных.
Вернемся к эффективности. Код каждой из двух дополнительных процедур выполняется за время O(1): доступ к элементу массива, запись в конец списка во втором случае (при хорошей организации списка с курсором в конце операция выполняется за константное время). Так что время работы record_constraint также задается O(1), а поскольку процедура должна отработать для каждого ограничения, в целом получаем O(m). Таким образом, достигнута наша цель: получить алгоритм, выполняющийся за время O(m + n) как на этапе инициализации, так и при выполнении основной задачи –
Мы уже познакомились со всеми элементами нашей программы, необходимыми для реализации
Напишите класс TOPOLOGICAL_SORTER, обеспечивающий универсальную, практичную
Убедитесь, что решение отвечает принципам инженерии программ, не только обеспечивает эффективный алгоритм, но и включает процедуры инициализации (record_element, record_constraint). Для тестирования решения используйте файл, доступный на сайте, который связан с курсом. Этот файл содержит несколько сотен ограничений и все возможные варианты
Из алгоритма
Мы уже рассматривали два стиля выполнения программ, написанных на некотором языке программирования S.
(рис 10.19) Интерпретация и компиляция программ
Как отмечалось, практическая реализация языков часто комбинирует оба подхода.
Эти концепции обобщаются на многие проблемные области, отличающиеся от выполнения программ, которые написаны на языках высокого уровня. Для выполнения некоторой обработки на некотором входе мы можем использовать структуры данных, которые непосредственно отображают вход, или можем разбить процесс обработки на два этапа.
Этот прием (который, как и при обработке языков, может и в общем случае включать несколько итераций процесса) в точности был применен для
В таком двухэтапном решении шаг "компиляции", инициализирующий структуры данных, может быть столь же сложным для проектирования, как и фактическая обработка, основанная на этих структурах, – он может требовать столь же много времени, а иногда и больше, чем время самой обработки. Этот подход хорош, если общая производительность соответствует вашим целям, но, конечно же, нельзя перепрыгивать к заключению о производительности алгоритма, не учитывая время инициализации, а не только самой обработки.
(рис 10.20) "Интерпретация" и "компиляция" данных
Подход может быть обобщен в виде эвристики – универсальной стратегии, подобной "образцу проектирования", но в существенно более абстрактной форме.
Хорошие алгоритмы часто создаются с использованием двухэтапной стратегии, где:
Мы увидим еще одно применение этой идеи при обсуждении архитектуры процесса проектирования, управляемого событиями.
Выбора тяжко бремя – память иль время!
Тесно связанным с эвристикой "Вначале компилируй данные" является наблюдение, что идеальная структура данных, та, которая наилучшим способом помогает реализации второго шага, часто не является наиболее экономичным по памяти представлением информации. В [x, y] ведет к тому, что y появится также в списке последователей x в массиве predecessor_count[y]. Если для заданного y ограничения отсутствуют, то это приводит к добавлению элемента в массив candidates. При таком представлении нам приходится жертвовать памятью для достижения требуемой по времени производительности. Компромиссы такого вида в ту или иную сторону – ключевые моменты проектирования эффективных алгоритмов.
Вполне возможно было бы привести описание алгоритма TOPOLOGICAL_SORTER. Экземпляр этого класса характеризует задачу process), но и весь инструментарий, необходимый клиенту для того, чтобы он мог:
process для выполнения Разница между этим подходом и чистым алгоритмом является частью разницы между программной инженерией и чистым программированием. В инженерии программ недостаточно спроектировать умный алгоритм и связанные с ним структуры данных. Целью становится подготовка решения, которое может быть интегрировано в успешные программные системы.
Наши решения должны допускать повторное использование, так что они не просто представляют "образцы проектирования", которые программист может интегрировать в свою систему, купив и прочитав книги (особенно выдающиеся книги, такие как эта, например). Решения должны быть реализованы как компоненты, доступные всегда и для всех, непосредственно доступные, а не стоящие на полках.
Вы также обратили внимание на то, как в этом процессе контракты позволяют нам точно знать, что нам следует делать, – что мы ожидаем, что гарантируется и что мы поддерживаем.
n элементов и m ограничений O(m + n) время, используя память того же порядка.| Acyclic | Antisymmetric | ||
| Asymmetric | Асимметричность | Binary relation | Бинарное отношение |
| Cycle | Цикл | Irreflexive | Иррефлексивность |
| Order relation | Отношение порядка | Partial order | |
| Relation | Отношение | Strict order | Строгий порядок |
| Topological sort | Total order | Тотальный или |
|
| Transitive closure |
Для обсуждения "<", заданное на числах. В некоторых задачах может быть более полезным иметь дело с нестрогим отношением, как отношение "<=" для чисел. Пара элементов связана нестрогим отношением x <= y, если и только если либо x < y, либо x = y. Общепринятое соглашение для "отношения порядка" предполагает нестрогую версию. В этой главе, так как мы использовали только строгое отношение порядка, слово "строгое" обычно опускалось, так что "порядок" означал "строгий порядок".
Для отношения
Еще одна проблема: является ли отношение тотальным или нет. Тотальность означает, что для любых пар различных элементов x и y имеет место одно из двух – либо x < y, либо y < x. Отношение порядка, удовлетворяющее этому свойству, называется тотальным порядком. Частичным порядком должно было бы называться отношение, которое не удовлетворяет этому свойству, такое, что для него найдется по крайней мере одна пара различных элементов, для которой ни [x, y], ни [y, x] не принадлежат отношению. Но не так определяется
Если же мы не знаем, каков порядок, или хотим включить оба случая – лучше применять термин "порядок". В случае неопределенности –использовать термин "возможно частичный порядок".
Дайте точные определения символам словаря.
Отношение порядка было определено как транзитивное и иррефлексивное. Было доказано, что следствием является асимметричность отношения. Докажите, что если отношение определяется как транзитивное и асимметричное, то следствием является иррефлексивность.
Докажите, что если отношение r является отношением строгого тотального порядка на конечном множестве, то существует единственное перечисление элементов, такое, что для любых элементов x и y элемент x появится перед y в перечислении, если и только если пара [x, y] принадлежит r.
Обсуждение в этой лекции строилось на строгом отношении порядка (частичном или полном), таком, как отношение "<" на числах – "меньше чем". Также возможно использовать нестрогое отношение порядка, такое, как "≤" – "меньше или равно". Определение строгого частичного порядка, которое мы будем называть отношением "<", хотя оно и не должно быть обычным отношением на числах, должно удовлетворять свойствам:
| О1 | иррефлексивности: | x < x не выполняется для любого x. |
| О2 | транзитивности: | из того, что x < y и y < z, следует x < z. |
Для этого отношения также выполняется свойство:
| О3 | асимметричности: | не могут одновременно иметь место x < y и y < x. |
Свойство О3 является следствием двух предыдущих свойств. Для частичного нестрогого отношения порядка "≤" имеют место три независимых свойства:
| N1 | рефлексивности: | x≤x для любого x. |
| N2 | транзитивности: | из того, что x≤y и y≤z, следует x≤z. |
| N3 | антисимметричности: | из того, что x≤y и y≤x, следует x = y. |
Для любого частичного строгого отношения порядка "<" существует связанное с ним нестрогое отношение "≤", определенное как
x ≤ y если и только если: x < y или x = y [4]
Справедливо и обратное утверждение: для любого частичного строгого отношения порядка "≤" существует связанное с ним строгое отношение "<", определенное как
x < y если и только если: x ≤ y и x ≠ y [5]
В этом упражнении требуется исследовать связь между этими ассоциированными отношениями – строгим "<" и нестрогим "≤"
Докажите теорему о
Объясните постусловие функции has_element.
В процедуре record_element проверяется, присутствует ли уже вставляемый элемент в таблице index_of_element, и запись осуществляется только в случае, когда такого элемента нет. В реализации используются две операции поиска – одна при вызове has_element, другая при вызове extend. Проанализируйте контрактную форму класса HASH_TABLE, найдите нужные компоненты, перепишите процедуры так, чтобы устранить эту небольшую неэффективность.
Постройте класс TOPOLOGICAL_SORTER в соответствии с обсуждением этой лекции.
(Это упражнение предполагает, что выполнено предыдущее)
Расширьте реализацию
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.