1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 14
Текст из файла (страница 14)
Чисто эстетические критерии простоты и стройности побуждают математика выдерживать уровень общности, пока он не столкнется с противоречащим примером или окажется не в состоянии построить докааательство из-за трудности задачи. С другой стороны, он должен без колебаний расставаться с «пустыми» обобщениями, которые, ничего не добавляя к нашему зна нню, делают наложение утомительным, а алгоритмы громоздкимп. В нашем случае анализ определения операторной схемы на общность тоже будет носить предварительный характер, касаясь анализа графа переходов, раси.»деления полюсов и памяти. Гл.
3. постАнов1 А ЗАЛАчн н Овзгвя твогия Анализ понятия графа переходов. По определению граф переходов — зто произвольный ориентированный граф с вершинамн Г' = (ГА, ..., Рв). МОжЕт ЛИ ПрОГраММа ИМЕТЬ ПрОИЗВОЛЬНЫН граф своим графом переходов 1' У нас есть, конечно, под влиянием О О Е! ' и Уио. 2Л. Примеры графов. упорядоченной логики программирования ходячее представление о «типичной» программе, к которому, несколько пофантазировав, мы добавляем некоторую коллекцию менее обычных грифов, представленных всех вместе на рис. 2.1.
ь г.г. исходныв огп кдклвния Прежде чем обсудить по существу разнообрааие этих картинок, дадим нескояько определений и свойств, которые позволят нам вести обсуждение болев четко и, кроме того, пригодятся в дальнейшем. Приведенные примеры графов делятся на две категории: в одной из них, а) и в), графы изображены в виде «связных» фигур, в другой, б) и г), четко распадаются на иаолированные друг от друга, но связные «вяутри ~себя» части.
Наконец о д) мы затрудняемся сказать что-либо дпределенное. Разберемся в этом подробнее. Свойство свяаностн состоит в том, что какие бы две вершины связного графа мы не взяли, существует путь иа дуг, соединяющих эти вершины. Для интуитивного представления этих слов достаточно, но нам нужны более точные определения. А. Две вершины в графе называются соседними, если одна нз них является предшественником другой (или они смежные— для неорнентированных графов). Б. Две вершины, а и Ь, в графе называются связанными, если существует последовательность вершин графа о„и», ..., и„, такая, что иг = а, и„= Ь и любая пара (ио и,+г) (г = 1,... ..., и — 1) образована соседними вершинами.
В. Граф называется связным, если в нем любая пара вершин является связанной. Пусть нам даны два графа, 6 = (А„Г ) и 6 = (А, Г,) Очевидно, что пересечение Г,П Г«будет подмножеством прямого произведения (А,ПА ) Х(А«ПА»). Граф 6' = (А,ПА», Г«ПГ») называется пересечением графов 6,' и 6,: 6' = 6,П6». Аналогично определяется объединение графов 6,() 6». По определению, граф называется пустым, если пусто множество его вершин. Наконец два графа называются непересепаюшимися, если пусто "их пересечение. Смысл этих определений станет ясным, когда мы сформулируем простую, но замечательную теорему: Т е о р е м а 1.
Любой непустой граф 6 можно однозначно представить в виде объединения непустых попарно непересекающихся связи»«х пвдграфвв 6п..., 6~ (2 в 1). Д о к а з а т е л ь с т в о. Опишем следующую одноаначно выполняемую процедуру. Пусть граф 6 образован вершинамп а,..., а„. Построим для каждой вершины а~ (г = 1, ..., и) множество Р; связанных с ней вершин.
В результате мы получим и множеств Р„..., Р„. Покажем, что для любой пары Р~ н Р либо Р~ = Рг, либо Р, П Р; = Я, где Я вЂ” введенный ранее символ пустого множества. Сначала декан~ем лемму. Л е м м а. Если в графе две егришнм а и Ь наждая связаны с вершиной с, тс они связаны друг с другом. ГЛ.
Х ПОСТАНОВКА ЗАДАЧИ И ОБЩАЯ ТЕОРИЯ Действительно; по определению связности есть две цепочки соседних вершин: а = вм из, ..., и„= с Ь = ип и„..., и,„= с. Из них можно. составить одну цепочку а = ип и„.; ., и„= с = — и, ..., Им иг = Ь, которая доказывает связанность а и Ь. Вернувшись теперь к множествам Р~ и Р;, сразу устанавляваем, что если а; и ат связаны, то, во-первых, кал<дая изних входит как з РО так н в РП и любая вершина, связанная с одной иа них, будет связанной и с другой, т. е.
в этом случае Р~ =,Р;. Если же а; и ат не связаны, то Р~ и Р; не могут иметь ни одной общей вершины, так как если бы такая вершина д существовала, то из связанности а; с Ь и а, с Ь следовала бы связанность а; н а,, что противоречит допущению. В результате у нас получилось однозначное разбиение множеотва А = (а„ ..., а„)на некоторое количество попарно пересекающихся множеств „„..., В,.
Построим для каждого из В~ (( = 1,..., 1) подграф С, графа 6, имеющий В, своими вершинами. По определению подграфа такое построение также однозначно, при этом также очевидно, что полученные графы попарно не пересекаются.. Осталось показать, что 6 = 6, () 6,()...
() СО Мы ул'е показали, что А = В, () Вз 0... () Вы Пусть à — множество дуг графа С и Г; (Г = — 1, ..., 1)— то же для графа 6;. Покажем, что Г = Г О Г ()... () Г,. Гак как С, *— зто подграфы графа С, то Г, () Гв()... () Г, С: Г. 'Докажем обратное включение. Каждая дуга графа Г либо принадлежит одному из подграфов 6;, либо соединяет вершины, принадлежащие разным подграфам, например, аМ; и ЬяС~. Этот случай, однако, невозможен, так как если бы а и Ь оказались соседними вершинами, то в силу леммы и свойств множеств В~ и Вт любая вершина из В~ оказалась бы связанной с каждой из вершин Вп что в силу построения В~ и Вт возможно, только если В; = Вт, что также противоречит их попарной непересекаемос- $ аи исходные Опгедклення 69 ти.
Теорема доказана (что в дальнейшем мы будем отмечать дву- мя «наблами» туту, оставляя одну «наблу» ~7 для признака окончания доказательства леммы). Графы бм ..., С, иа формулировки теоремы называются компонентами сеяеноппи графа б~ Продолжим рассмотрение примеров графов с рис.
2.1. Итак, мы видим, что в общем случае граф переходов может состоять из нескольких компонент связности. Даже не дождавшись пост- роения общей теории, мы можем немедленно заметить, что если операторная схема распадается на изолированные части, представ- ленные компонентами графа переходов, то в каждой части эконо- мию памяти можно проводить раадельно, так как величины, от- носящиеся к разным частям, заведомо совместимы друг с другом.
С этой точки зрения естественно потребовать, чтобы граф пере- ходов был связным. С другой стороны, можно представить себе реальную ситуа- цию, в которой объектом экономии является комплекс программ, с заранее не иавестным строением, например, полученный с по- мощью транслятора или просто слишком сложный, чтобы раз- бираться заранее, сколько компонент связности в графе перехо- дов (рис. 2.1, д)). Тогда нам может оказаться более выгодным иметь одну процедуру экономии памяти, которая сделает свое дело, не вовлекая нас в анализ графов переходов.
Оказавшись перед лицом этих противоречивых факторов, мы фиксируем воз- можную полезность разбиения, или, как говорят, факторизации экономии памяти по отдельным компоненталг графа переходов, но развиваем теорию для общего случая столь долго, сколько это окажется естественным. Сравнивая «типичный» граф переходов с рис. 2.1, а) с дру- гими примерами, мы усматриваем такие особенности, как одно- операторные компоненты (2.1, б)), графы без заключительного и без начального операторов, графы с несколькими начальными или несколькими заключительными операторами.
Практика программирования подсказывает нам, что эти особенности, вооб- ще говоря, не должны быть объектом априорных ограничений. Случай нескольких начальных или заключительных операторов уже должен быть предусмотрен хотя бы из допущения несколь- ких компонент связности. Наконец, бывают такие программы. которые либо не имеют команд останова или имеют вместо них команду паузы, допускающую продолжение работы — это де- лает приемлемым случай рис. 2.1, е). Одним словом, мы сохра- няем пока что определение графа переходов во всей его все- общности, Распределение полюсов. Продолжим наш анализ определения операторной схемы с распределения полюсов '«': (А () В) -» Р. 70 ГЛ.
Х ПОСТАНОВКА ЗАДАЧИ И ОБШАЯ ТЕОРИЯ Мы уже освоились с мыслью, что оператор может иметь любое число как аргументов, так и результатов (в тем числе и равное нулю). Допущение произвольного $' может, однако, привести к таким схемам, в которых входной оператор будет иметь аргументы (которые нечем загружать) или выходной оператор— результаты (которые негде использовать). Другими словами, у нас могут получаться «бессмысленные» операторные схемы.
Как нам к атому относиться? Как обычно, ответ на этот вопрос дают не в меньшей степени общие сообра»)«ения, не>нели специфика задачи. Уже повседневная практика подсказывает нам, что любая формальная конструкция всегда создает объекты «с запасом», по отношению к которому «осмысленные» объекты обраауют подмножество.
Такой запас, например, создают грамматические правила русского языка, да и не только его, но и любого языка программирования, того же алгола. Существование такого запаса не случайно. Во-первых, смысл, т. е. связь абстрактного объекта о явлениями реальной жизни, есть, строго говоря, категория, находящаяся за рамками математического рассуждения. Можно давать, конечно, формальное определение смысла, или, как говорят, интерпретацию объекта и проверять его выполнимость.
Такой подход существует, и мы в атой книге еще коснемся вопросов интерпретации, в том числе и для теории, развиваемой в этой главе. Во-вторых, описание смысла, даже если оно п предпринимается, сильно усложняет теорию, не давая иногда каких-либо заметных преимуществ. Одна из причин сложности состоит в том, что смысл не зависит целиком от состава объекта, не определяется им самим, а требует учета какого-то более широкого контекста, описать который не всегда возможно. Услышанная как-то автором фраза: «Вчера клево побалдели с хипарями в одной кодле», рез сомнения, вполне понятна кому-то из молодых читателей, но для других будет таким же экзотическим словосочетанием, как знаменитый пример А. В.
Щербы: «Глокая Куздра штеко будланула бокра»,— фразы, грамматически беаупречной, но бессмысленной. Природу другой сложности нам можно будет пояснить и на материале нашей задачи. Скажем, нам не нравится, что конечный оператор может иметь нигде не используемые результаты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
