1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 18
Текст из файла (страница 18)
Каждый иэ путей создает свой маршрут за исключением АВСРЕН, в котором оператор Р препъ1вает возможные связи А с Е и Н, создавая «свои» маршруты РЕ и РЕН. Дав точное определение маршрута как конструкции, оэеществляющей информационную свяэь, мы автоматически приходим к понятию носителя СН как множества всех маршрутов операторной схемы. Заметим, что хотя маршруты строятся по Заданной операторной схеме, т. е. скелет + память + распределение памяти, сам носитель состоит нэ конструкций, построенных только из элементов скелета (операторы и полюсы). Это важное свойство носителя позволяет сравнивать носители схем с одним скелетом, но с рааными Х и Ь. Если носитель СН строится по схеме 6, то чтобы подчеркнуть эту зависимость, мы будем обозначать носитель СН(6).
«еперь мы»«ол«ем дать следующее 83 % аг. ОБШ»я твогпя О и р е д е л е и и е. Пусть даны две операторные схемы 6 = (Я, Х, Ь) и 6' = (Я, Х', Ь'). Мы скажем, что 6' вычисляетп С (6' ) 6), если СВ(6') ~ СВ(6). Теперь мы можем сказать, что задача экономии памяти в заданной схеме 6 = (Я, Х, Ь) состоит в нахождении среди схем 6' = (Я, Х', В') любой такой схемы, вычисляющей 6; у которой Х' будет иметь наименьшую мощность. Содержательный анализ задачи подсказал нам, что эта задача решается в два этапа: построение графа несовместимости У и его раскраска. В следующем разделе мы займемся обоснованием этой гипотезы, 8 2.3.
Общая теория Информационный граф. Начнем исследование с описания графа У. Его вершинами являются «сзязки» вЂ” некоторые совокупности информационных связей, (г, а), которые в свою очередь аадаются бинарным отношением М существования маршрута, реализующего «передачу информации» от г к а. Сказанное дает нам основание рассмотреть ориентированный граф, вершинами которого являются полюсы Р, а множество дуг задается бинарным отношением М. Этот граф, который мы, не называя его никак специально, уже рисовали во всех наших примерах пунктирными стрелочками, естественно назвать инфор.мационным графом 1= (Р, М). Получив мимоходом его определение, мы, как обычно, займемся его анализом. Начнем с того, что перернсуем информационные графы со всех построенных в главе 1 примеров и соберем их на рис.
2.5. Для наглядности и более четкой сдяаи с исходными схемами мы расположим результаты в верхнем ряду, аргументы — в нижнем и пометим полюсы символами операторов, к которым эти полюсы относятся. Простое рассмотрение йолучнвшихся графов позволяет сделать несколько наблюдений.
П е р в о е. Дуги информационного графа — особого рода. Результат в этих дугах бывает только предшественником, а аргумент — только преемником. По существу, бинарное отношение М задано не на прямом произведении Р ХР, а на прямом произведении В хА, где В с: Р, А ~ Р и В () А = Я. Графы такого рода называются двудольныг«и. В т о р о е.
Знакомство с теоремой 1 из предыдущего раадела убеждает нас в том, что «связки» информационных связей, использованные в главе 1, суть не что иное, как компоненты связности информационного графа. Это наблюдение, в данном контексте почти тривиальное, является для нас сущей находкой. Оно полностью формализует поня- ГЛ. 2. ПОСТАНОВКА ЗАДАЧИ И ОБЩАЯ ТЕОРИЯ тие связки и одновременно показывает, какой важной конструкцией является информационный граф. Т р е т ь е. Информационный граф в ряде случаев оказывается более глубоким инвариантом, чем носитель. Например, для г а с" ' г) 'Г Г с" Р 1 2 пг пг Й Сг пг пг пг Гг Гг Рг Гг 'г 1г ''г пг 1г 2г 11 аг а ) с 11 гу Жг р 2 11 нср1 нср1 нср2нср2прссн 11йагг)г 12свс р, с, г~гпсг)г < прин нср1,' 11г нср1г' ирр1 ар2г сысс 11, нср."г нср2г нср2г РсгРг 5ыИ с) ссг I суг )и гс + а)с сс гр г - — +1 1 а Зы1 гг и ~ асс 12 / гг с1 и 5г г ) +г ге16 «г) ~гюыс г) Рнс.
2.8. Информационные графы. и) Примеры б, 6, 7 и 8. а) Пример 9. н) Пример Ю. е) Пример П. операторных схем примеров 5, 6 и 7, 8 мы обнаруживаем„что носители в примерах 5, 6 и 7, 8 разные, а информационный граф— один и тот же. Пытливый ум сразу задаст вопрос о самостоятельной роли информационного графа как инварианта в задаче экономного распределения памяти. Выясняя, этот вопрос, читатель легко может показать, что имеет место $ хг. ОБщАя Фвогия ВВ Т е о р е м а 2. Пусть 1(С) — информационный граф операторной схемы б. Тогда если 6' ) С, то 1(С) является подграфом 1(6'). К сожалению, пример рис.
2.4, г) с такой же очевидностью шоказывает, что обратное утверждение не верно. Совмещение х и у не выбросит ни одной дуги из информационного графа, но полностью исказит картину информационных связей. По-настоящему пытливый ум тем не менее не удовольствуется этим отрицательным общим результатом и будет выяснять, когда же все-таки информационный граф может быть спасен как инвариант. Заметим, что на атом пути исследователь быстро обнаружит, что для линейных операторных схем информационный граф является исчерпывающим инвариантом не только распределения памяти, но и более широкого класса преобразований схемы, связанного с перестановкой операторов.
Для более же общего случая он «втравится» в исследование такого класса схем, в которых различные распределения памяти строго сохраняют совокупность информационных связей, не расширяя ее. Мы, однако, сейчас не будем отвлекаться от нашей основной линии общей теории.
Уточнение несовместимости. Итак, на основе сделанного небольшого открытия мы можем сформулировать нашу гипотезу так, что вершинами графа несовместимости являются компоненты связности информационного графа операторной схемы. Как таковые, они ааслуживают особого термина. Исторически сложилось так, что они называются областями действия (величины). Так как содержательный анализ у нас позади, то смысл этого термина нам ясен: всем полюсам, входящим в область действия, сопоставляется одна и та же величина. Для полного описания графа П нам надо описать бинарное отношение несовместимости между областями действия. Гипотеза для этого у нас уже готова. Дадим сначала чисто словесную формулировку отношения несовместимости. О п р е д е л е н и е.
Две области действия несовместимы, если в кам;дой из них найдется информационная связь, причем начальный оператор некоторого маршрута одной связи ока»кется начальным или внутренним оператором некоторого маршрута другой связи. Это определение хотя и требует много воздуха, чтобы произнести его беэ запинки, все же вполне точно и строго соответствует нашим догадкам, сделанным в 1-й главе. Тем не менее в этом определении есть одна недоговоренность, которая нам была совершенно не видна прн рассмотреяяи содержательных примеров и до которой и сейчас было бы непросто догадаться, если только не бросить еще раа взгляд на рис.
2.1 с различными примерами компонент связности ориентированных графов. На одном из примеров нзобрал<ены компоненты связности, состоящие из изолиро- ГЛ. 2. ПОСТАНОВКА ЗАДАЧИ И ОБЩАЯ ТЗОРИЯ ванных вершин. Спрашивается, может ли информационный граф иметь изолированные вершины-полюсы. Определение операторной схемы с очевидностью подсказывает, что это вполне возможно.
Изолированный результат — это результат, который нигде не используется, изолированный аргумент — это аргумент, для которого нет «питающего» его результата. Но тогда возникает вопрос, как для изолированных полюсов определить отношение несовместимости, поскольку при отсутствии дуг информационного графа (информационных связей) говорить о маршрутах нельзя— они отсутствуют тоже. Здесь возникает традиционная дилемма.
Надо ли сузить определение операторной схемы, чтобы сохранить определение несовместимости в силе, изгнав из информационного графа изолированные вершины, либо обобщить определение несовместимости на случай произвольного информационного графа. В последнем случае появляется дополнительная задача сделать это обобщение таким образом, чтобы не нарушить наше допущение сопоставления одинаковых величин компонентам свяаности, оказавшимся совместимыми. Рассмотрим сначала случай изолированного результата г. Вернемся к содержательной трактовке оператора. Когда оператор вырабатывает результат, он «не знает», когда и будет ли вообще его результат использован.
Отношение несовместимости возникает из-за того, что при присваивании значения результата неудачно выбранной величине этот результат «убивает» (в американской литературе так и пишут я111з) нужное значение (формально — делает невозможным определить тот же маршрут в схеме с перераспределенной памятью).
«Этот же» маршрут будет невовможно определить, если конкурирующий результат окажется результатом его внутреннего или начального оператора. Таким образом, оператор У(г) при сопоставлении с информационной связью ведет себя так же, как и начальный оператор маршрута„ конкурирующего в смысле сделанного выше определения. Сопоставим изолированные результаты г и г' друг с другом.
Очевидно, что не страшно «убить» неиспользуемый результат, поэтому несовместимость появляется только в том случае, если. изолированные результаты оказываются результатами одного и того н<е оператора Г(г) = У(г'). Объявление их совместимыми нарушит правила построения операторной схемы. Рассмотрим теперь изолированный аргумент а. Содержательная интерпретация изолированного аргумента означает, что его значение не влияет иа характер выполнения оператора И(а).
Какая бы величина ни окааалась сопоставленной аргументу а, К(а) будет выполняться одинаково. Это дает нам возможность считать изолированный аргумент совместимым с любой областью действия в информационном графе. 5 ХЗ. ОБ)ЦАЯ ТЕОРИЯ Итак, мы рассмотрели все воаможные случаи сочетания компонент свяаности и внаем, как нам надо модифицировать определение несовместимости.
О и р е д е л е н и е. Две области действия несовместимы тогда и только тогда, когда в каждой из них найдутся соответственно результаты г и г', такие, что либо г'(г) = У(г'), либо г(г) оказывается внутренним оператором некоторого маршрута информационной связи (г', а'), либо )г(г') оказывается внутренним оператором некоторого маршрута информационной свяаи (г, а), где а и а' — некоторые аргументы. Теперь отношение несовместимости Н у нас определено для всех областей действия с(м..., и, информационного графа 1 (Р, М). Пусть В (с(„..., с(,). Тогда граф несовместимости У полностью определен как П = (Й, Н).
Критерий несовместимости. Сделанные определения и их анализ позволяют нам приступить к строгому доказательству основной гипотезы, сложившейся при содержательном рассмотрении задачи, о том, что допустимые распределения памяти — это те, в которых всем полюсам любой пары совместимых областей действия сопоставляется одна и та же величина. Дадим аккуратную формулировку, предварив ей еще одно обозначение. Если в распределении памяти Ь всем полюсам некоторой области действия а сопоставлена одна и та же величина, то она будет обозначаться Ь(д). Т е о р е и а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
