1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 19

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

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

3. Пусть даны две операторные схемы 6 = = (Я, Х, А) и 6' = (Я, Х', Ь') и йп..., д~ — области действия графа 1(6). В этих условиях 6' ) 6 тогда и только тогда, когда: а) для любой с(; (г = 1,..., () В'(р) одно и то ясе для любого полюса р иг йь б) Х'(а;) Чь Г(й) для любой пары й; и Ы., удовлетворяющих вт машению несовместимости в графе У(6). Приступим к д о к а а а т е л ь с т в у теоремы. Она содержит необходимое и достаточное условие, поэтому нам нужно провести рассуждение в оба конца: от вычисляемости схемой 6' схемы 6 к уу1говию и наоборот. Не о б ход и и о от ь. Пусть 6') 6.

Проверим выполнение условий. Для областей действия, образованных изолированными полюсами,. условие а) выполняется тривиально. Предположим, что в некоторой области а, содержащей дуги, есть два полюса, р и р', для которых Ь(р) 4=Цр'). Тогда в д обязательно найдется дуга (г, а), для которой также Цг) чь Ца) (подробное доказательство атой мини-леммы требует некоторого рассуждения, в котором по существу используется свойство связности области д).

Но в этом случае пара (г, а) не может быть в 6' ннформаци- Гл. к постАНОвкА ЗАдАчи и ОБщАя твогня анной связью, реалиауемой каким бы то ни было маршрутом. А это противоречит условию 6' ) 6. Предположим теперь, что нашлись две несовместимые в графе У(6) области действия Ы, и а';, для которых тем не менее А'(а,.) = = Ь'(Щ = х. По определению несовместимости мы либо обнару- живаем в таком случае, что в схеме С' оказывается оператор с двумя реаультатами, которым сопоставлена одна и та же вели- чина (это противоречит правилам аадания схемы 6'), либо обна- руживаются два результата, г, г', аргумент а и такой путь Р(г)... )г(г')...

)г(а) (остальные операторы не показаны), который в схеме 6 оказывается маршрутом т информационной связи г, а: т = ((г, а), Р(г) ... )г(г') ... )г(а)), а в схеме 6', тем не менее, Ь'(г) = А"(г') = Ца) = л. Это значит, что т не является маршрутом в схеме С', что опять-таки противоречит условию 6' ) С. Необходимость доказана. Д о с т а т о ч н о с т ь. Пусть теперь выполнены условия теоремы. Предположим, что схема 6 содержит маршрут т, который отсутствует в схеме 6'. Пусть т = ((г, а), )г(г)...

Р,... )г(а)), где Р, — произвольный транзитный оператор маршрута т, может быть, отсутствующий. Рассмотрим, по каким причинам этот набор не может быть маршрутом в 6'. Во-первых, если Ь'(г) 4= Ь'(а). Этого, однако, не может быть, потому что как г, так и а принадлежат одной и той же области действия И в схеме 6 и по условию а) Л'(г) = Ь'(а). Таким образом, если т, не содержит транзитных операторов, то он является маршрутом связи (г, а) в схеме 6 .

Во-вторых, если имеется результат г', такой, что г'(г') = г'; и Ь'(г') = Ь'(г). Так как Р; — внутренний оператор маршрута т в 6, то в 6 г' принадлежит обязательно некоторой И', отличной от области действия И, содержащей (г, а). (Это еще одна мини- лемма, требующая проработки определения маршрута и компоненты связности.) В этом случае области действия а и Н', по определению, оказываются несовместимыми.

Но тогда выполнение условия б) требует, чтобы Ь'(г') чьЬ'(г). Таким образом, ничто при выполнении условий теоремы не мешает тому, чтобы любой т был бы также и маршрутом в С'. с7~7 Только что доказанная теорема является основной в нашей общей теории. Она обосновывает весь наш подход к задаче, экономии памяти. Нахождение графа несовместимости. Теперь наше внимание концентрируется на способах задания графа несовместимости. Мы уже рааобрались с его вершинами — компонентами связности $2.3. ОБЩАЯ ТЕОРИЯ 89 информационного графа. Мы дали также точное определение несовместимости. Оно в общем случае использует понятие маршрутов, находящихся в специфическом взаимном положении (начало одного является началом или транзитом другого).

Мы уже понимаем, что основное направление развития нашей теории — это конструнтивизация нашего исходного определения вычисляемости Одной схемы другой. Мы не можем контролировать допустимость распределения памяти, изучая непосредственно носитель — множество маршрутов в общем случае бесконечно. Мы уже с помощью теоремы 3 свели контроль за допустимостью распределения памяти к анализу графа несовместимости. Теперь нам нуягно сделать еще один шаг и «изгнать» маршруты как рабочую конструкцию из самого определения несовместимости. Кстати говоря, нам в этом отношении помог анализ изолированных полюсов в информационном графе. Обобщенная формулировка отношения несовместимости, как надеется автор, сделает для читателей естественной формулировку следующей теоремы, которой мы, однако предварим пару обозначений.

Пусть д — некоторая область действия в информационном графе схемы 6. Тогда обозначим В(д) — множество всех операторов, имеющих своими результатами полюсы иа д; Т(и) — множество всех операторов„каждый из которых является транзитным хотя бы для одного из маршрутов информационных свяаей из д. Т е о р е м а 4.

Двг области действия И и д' информационного графа схемы 6 нгсовмгстимы тогда и только тогда, когда нг пусто многкгство Л(д) П Л(д') и Л(д) П т(д ) () Л(д ) П т(д). Доказательство этой теоремы крайне просто и является, по существу, перефразировкой определения несовместимости. Если множество не пусто, значит имеется оператор, который вырабатывает результаты, относящиеся к областям действия И и Ю, либо, вырабатывая результат одной из областей, является транзитным для маршрута связи другой из областей. Наоборот, выполнение условия несовместимости обеспечивает непустоту указанного множества. Ч~7 На этом построение общей теории можно считать законченным.

Мы нашли точную постановку задачи, и описали как заданные, так и искомые объекты, нахождение которых в силу доказанных ~вором поможет нам в решении задачи. Это — компоненты связности информационного графа, а также множества В(д) и Т(И), которые позволят нам строить подлежащий раскраске граф несовместимостии. ГЛАВА 3 АЛГОРИТМИЗАЦИЯ Содержание этой главы можно рассматривать как углубление общей теории в некотором специфическом направлении.

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

В этой главе, оставаясь на уровне рассмотрения абстрактных объектов, мы постараемся понять, как все эти объекты могут быть построены: как найти компоненты связности информационного графа, как определить множества Л (что просто) и Т (что существенно сложнее), как, наконец, найти наилучшую раскраску графа несовместимости? Для этих построений нам нужно найти систематические процедуры, которые могут быть положены в основу практического решения задачи зкономии памяти, например, на ЭВМ с помощью алгольных программ. Следует напомнить, что содержательный анализ задачи, хотя и на частных примерах, оставил нам немало намеков на то, какими могут быть искомые вычислительные процедуры.

й ЗЛ. Информационный граф Итак, информационный граф 1 схемы 6 — зто г = (Р, М), где Р— множество полюсов, а М вЂ” бинарное отношение между парами (г, а) «иметь информационную связь от результата г к аргументу а». Для того чтобы найти множество Р = (г(»..., д,) компонент связности, нам достаточно знать, какие полюсы к каким коьшонептам отпосятсл. Из всех этих объектов нам в исход- 5 ЗЛ. ИНФОРМАЦИОННЫЙ ГРАФ З1 ной схеме дано только Р.

Кще не вникая в суть дела, мы можем высказать одно пожелание, а именно, чтобы в искомой процедуре .построения графа 1 выделение компонент связности происходило бы по возможности «само собой» по мере обнаружения информационных связей. Еще один намек на подход к разбиению вершин на группы, попадающие в одну компоненту, нам дает доказательство теоремы 1: каждая вершина а, графа «искала» соседей, начиная с себя как с нролированной вершины.

Затем в процессе построения множеств А>> (из теоремы 1) все связанные вершины вошли в одно и то же множество, а изолированные так и остались изолированными. Транзитивное замыкание. Важный ключ к процедуре нахожденияя информационного графа нам дала практика построения информационных связей в примерах главы 1: отправляясь от задания величины л, мы двигались вдоль некоторого пути (в линейных схемах — единственного) пока не находили использования к (устанавливая тем самым информационную связь), или пока не встречали новое прнсваивание величине х, обрывающее наши попытки продолжнть маршрут величины, начатый предыдущпм присваиванием. Это весьма наглядное напоминание должно быть, однако, сформулировано в более точных терминах, нежели «двнжение» и «встречи».

Здесь нам будет уместно усвоить одно общее О и р е д е л е н и е. Пусть  — бинарное отноп>>ение на.элементах множества А. Трапзитивным злмыпапием Тг (В) называется бинарное отношение В' на этих же элементах, выполняющееся для пары (а, а') тогда и только тогда, когда существует конечная последовательность аа>а»... а„а' (и ) О) элементов нз А, такая, что любая пара соседних элементов в этой последовательности удовлетворяет отношению В. В применении к графам две вершины (а, Ь) удовлетворяют транзитивному замыканию отношения соседства, если с графе есть нугь, ведущий от а к д. Идею пошагового движения по путям, соединяющим вершины в графе, развивает очевидный алгоритм нахождения транзитивного замыкания.

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

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