1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 9
Текст из файла (страница 9)
в) Примерм 7,8. г) Пример 9. д) Пример 10. «более. слабо» соединены друг с другом ребрами и поэтому на их долю хватает того максимума величин, которые потребовались для ядра. Граф примера 10 таким свойством не обладает: в нем нет трех попарно смежных вершин, однако он требует трех «красок». Мы уже, пожалуй, привыкли к тому, что мелкие отличия оказываются источником серьезных проблем.
Так и сейчас: мы обязаны сказать себе,, что раскраской вершин графа несовместимости как самостоятельной аадачей нам надо будет в свое время серьезно заняться, $ !.«.НАКОПЛЕНИЕ ФАКТОВ. ПОДВЕДЕНИЕ ИТОГОВ $1.4. Накопление фактов. Подведение итогов Программа е процедурами. Обогатившись такой важной конструкцией, как граф несовместимости, мы спешим замкнуть наш содержательный анализ исследованием прогрев«м, содержащих функциональные обозначения, раскрываемых (для алгола) с помощью описаний процедур.
П р и и е р 11. Вычислить в+» если х( 1; Р(в) ' (х — Ь)Р(х), если х) 1, где Р(г) = г» + 1. Вычисление Р(х) оформим в соответствии с правилами алгола в качестве описания процедуры. Получаем исходную программу начало вещ Ь, и, х, у, з; вещ проц Р(г); вещ г; начало вещ >; >:= г(2; Р:= >'+ 1 конец; ввод (Ь, х); если (х ( 1), то начало з:=' х + Ь; у:= г/Р(х) конец иначе начало и:= х — Ь; у:= ихР(х) конец вывод (х) конец При построении операторной схемы нам нужно решить, как изображать'связь тела процедуры с местами указания ее выполнения, а также фактических параметров с формальными. Не занимаясь этим вопросом в его полном объеме, мы заметим, что фактический параметр в указателях функции один и тот же и сам вызывается именем.
Таким образом, тело процедуры выполняется с именем величины х вместо г. В местах указателей функции будут выполняться передачи управления на тело процедуры, а в конце тела процедуры подразумевается наличие «оператора возврата», который обеспечивает продолжение вычислений с того места, откуда было вызвано выполнение процедуры. В результате получаем схему, изображенную на рис. 1.10, а). Структура схемы достаточно проста и мы, уже. не связываясь с иажившими себя сечениями, определяем взаимную совместимость и несовместимость связок информационных связей.
Анализируя операторы схемы и маршруты информационных связей, обнаруживаем, для каких маршрутов данный оператор является начальным, и для каких — внутренним. Проделав это систематически, получаем показанную на рис. 1.11 таблицу. В позиции таблицы (1-я строка, у-й столбец) мы ставим Н (начальный оператор), если в )-й связке есть маршрут, который начинается 1-и оператором, и В гл, 1. содвржАтнльный АКАлиз зАдАчи (внутренний оператор), если в )-й связке есть маршрут, который минует 1-й оператор. Построение такой таблицы позволяет более однотипно провтрять попарную несовместимость связок.
Берем колонки ут и у и-их содержимое объединяем. Если у нас в результате хоть в какой-то позиции окажется вместе Н и Н или Н и В, то связки у Рис. 1 ДО. Операторная схема с процедурой. а) Начальный ввд. б) Схема с новыми информационяымн связями. и )в несовместимы, так как зто совместное появление Н, Н или Н, В означает, что соответствующий оператор имеет обе иелнчиньт своими результатами или является для некоторого марш'рута одной из связок начальным, а для другой — внутренним, что, атак мы установили, как раз и является условием существовачип$ конкурирующих информационных свявей, $ ьа ИАкопление ФАктОВ. подВедение итОГОВ Результирующий граф несовместимости также показан рядом с таблицей на рис. 1.11. Его 'раскраска ке составляет никакого труда, и мы видим, что для правильной работы программы достаточно обойтись только двумя величинами.
В этом примере„ однако, нам будет полезно переписать программу в новых обозначениях величин, и для того чтобы не нарушать формальные правила алгола 60, которые не разрешают изображать одним именем Рпс. 1.11. Поотроеиие графа иесовместимосги для примера 11. а) Таблица.
6) Граф. функцию и переменную, мы возьмем четыре величины Ь, х, / и Р, хоторымн й «раскрасим» наш граф. В результате 'экономии памяти получим следующую программу: начало вещ Ь, х; вещ проц Р(г); вещ г; начало вевц 1; 1:= г)2; Р:= 1 + 1 конец; ввод (Ь, х); если (х < 1) то начало Ь:= х + Ь; х:= Ь1'Р(х) конец иначе начало Ь: = х — Ь; х: = — Ь х Р(х) конец; вывод (х) конец расширение информационных связей. А теперь сделаем то, чего, будучи убежденными в правильности наших процедур экономии памяти, мы до сих пор не делали ни разу: построим снова по полученной программе операторную схему (рис. 10, 6)), а для нее проложим информационные связи. Мы имеем Ь в качестве реаультата операторов + и — и ее же в качестве аргумента операто- 46 ГЛ.
Ь СОДЕРЖАТЕЛЬНЫЙ АНАЛИЗ ЗАДАЧИ ров / и х. Вспоынив определение маршрута, мы обнаруживаем, что цепочки операторов (+, ), +1, Х) н ( —, Г, +1, 1) удовлетворяют этому определению так же, как и те, которые мы прокладывали в операторной схеме рис. 1.10, а); а именно: (+, 1, -(-1, !) и ( —, (, +1, х). В итоге оказывается, что совокупность информационных связей в результирующей операторной схеме, благодаря, как нам казалось, вполне законному распределению памяти, расширилась на две связи. Мало того, в исходной схеме мы имели две санаки информационных связей (по одной связи в каждой): з и з.
В результирующей — мы имеем одну свяшсу (с четырьмя связями): Ь. До сих пор все варианты распределения памяти сохраняли как число информационных связей (а также реализующие нх маршруты), так и их распределение по связкам. Так что, если бы мы взяли схему рис. 1.10, б) за исходную, мы никогда не могли бы для нее подобрать такое распределение памяти, при котором результат совпал бы со схемой рис. 1.10, а), так как мы всем аргументам и результатам связки Ь по нашим правилам обязаны сопоставлять одну и ту же величину.
Таким образо»1, принятая на»1н процедура экономии памяти оказывается необратимым преобразованием исходной схемы. Ситуация слишком серьезна, чтобы не рааобраться в ней как следует. Самое главное то, что, как нам казалось, мы на каждом шагу поступали правильно. Давайте еще раз перечислим шаги решения аадачи: — построение операторной схемы, — прокладка маршрутов и построение информационных связей, —, построение графа несовместимости, — «раскраска» графа несовместимости, — распределение памяти согласно «раскраске». Вспомнив правила выполнения каждого из этих шагов, мы понимаем, что секрет кроется в процедуре прокладки маршрутов. Цепочка операторов в исходной схеме (рис.
1 10,а) (+, 1, +1, х) не может осуществиться и смыслом задачи не предусмотрена. Аргументу и оператора Х предписако использовать только реаультат Р оператора — . Процедура вычисления Ь'(х) так и работает: оператор возврата передает управления не любому из операторов 1 или К, а выбирает один из них в строгой зависимости от »1еста выаова процедуры. Попав на 1 от +, мы уйдем на 1', попав на)от —, мы уйдем на х, а перекрестные свяаи от — к 1 и от + к х невозможны.
Таким образом, мы видим, что конструкция операторной схемы так, как мы ее ввели, не учитывает, что в реальной программе не все цепочки операторов, которые можно формально построить по схеме, на самом деле фактически выполняются. Первой реакцией па это открытие была бы попытка так подправить определение схемы, чтобы цепочки, невозмон«ные в каком-то смысле в исходной схеме, обяаательно оставались бы невозможными в результирующей. Например, мы видим, что цепочка (+, % ьь нлкоплвнин фактов.подвкдкник итогов 47 ), +1, х) невозможна хотя бы потому, что на таком пути для оператора х не оказывается питающего его результата.
Мы можем потребовать, чтобы эта цепочка оставалась бы невозможной и запретить любому реаультату вдоль этой цепочки сопоставлять ту же величину величине и. В реаультате связки х и э окажутся несовместимыми. Однако, еще не думая, насколько это усложнит правила построения графа несовместимости, мы обязаны подумать, что нам это усложнение даст? Ведь на самом-то деле, без всякой теории, величины з и и можно направить в одну ячейку! Эти информационные связи никогда не будут реализоваться одновременно и поэтому они не конкурируют. Реально, нам важно лишь, чтобы ни одна информационная связь, ни один маршрут не нарушились бы.
А если в результате интенсивной зкономии памяти у нас чисто формально появятся новые маршруты и сольются какие-то связки — так это пусть! Таким образом, у нас появляется новое и принципиальное допущение: мы считаем правильными такие распределения памяти, при которых для любой заданной информационной связи сохраняются все реализующие ее маршруты, но при этом не делаем никаких оговорок в отношении возможности появления новых маршрутов и новых связей.
Подведение итога. Итак, мы можем подводить итог содержательному анализу проблемы зкономии памяти. Мы рассмотрели способы программирования, которые влияют на об ьем расходуемой памяти для величии. Мы выяснили, что как выбор алгоритма решения задачи, так и расположение отдельных операторов в программе влияют на количество величин, требуемых для решения задачи. Однако в любом случае имеет смысл более ограниченная постановка проблемы, состоящая в том, чтобы, зафиксировав операторы программы и порядок их выполнения, перейти от исходной программы, з которой имена величин выбирались из соображений удобства обозначений, к другой программе, с минимально возможным числом величин, сохраняющих все возможные информационные связи исходной программы.
Мы, далее, нашли, какая информация о программе существенна для систематического решения этой задачи экономии памяти. Для этого нужно знать перечень операторов программы и для каждого оператора знать, какие операторы могут выполняться непосредственно за ним. Для каждого оператора нужно, кроме этого, знать, сколько он имеет аргументов и результатов и какие величины им сопоставлены. Вся эта информация задается в виде операторной схемы, которая наглядно изображается в виде графа (мы уже использовали это слово для графа несовместимости), где вершины — прямоугольники обозначают операторы, а стрелки показывают возможный порядок перехода от одного оператора к другому.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
