Содержание к диссертации
Введение
ГЛАВА I Экономия арифметических операций в циклах и системы рекуррентных соотношений 10
I Постановка задачи 10
2 Системы рекуррентных соотношений 12
3 Построение систем рекуррентных соотношений 18
4 Организация цикла с помощью систем рекуррентных соотношений 34
5 Реорганизация циклов в программах с помощью построения систем рекуррентных соотношений 43
ГЛАВА 2 Преобразование выражений,связанных с системами рекуррентных соотношений 52
I Элементарные преобразования выражений,связанных с системами рекуррентных соотношений 53
2 Преобразования,использующие свойства коммутативности и ассоциативности 59
3 Преобразования,использующие свойство дистрибутивности 78
4 Эквивалентность выражений,связанных с системами рекуррентных соотношений 103
5 Подстановки 112
ГЛАВА 3 Вопросы реализации 119
I Типы данных 119
2 Основные процедуры и функции 123
Литература
- Построение систем рекуррентных соотношений
- Реорганизация циклов в программах с помощью построения систем рекуррентных соотношений
- Преобразования,использующие свойства коммутативности и ассоциативности
- Основные процедуры и функции
Введение к работе
Реализация многих численных методов предполагает организацию вычислений по сложным формулам.Часто вычислительные формулы являются итерационными и для их реализации требуется цикл.Ясно, что конкретный вид этих формул существенно влияет на сложност-ные характеристики Г время выполнения,объем требуемой памяти) будущей программы.Поэтому актуальной является задача приведения данных вычислительных формул к такому виду,который задает способ экономной организации вычислений в цикле.
Некоторые аспекты этой проблемы рассматриваются в работах по оптимизации программ 1~ loCJ .Основными оптимизационными преобразованиями для циклов,используемыми в системах оптимизации программ,являются чистка циклов ]_ 1 ~ J, 1 oLJ и преобразование рекурсивно определяемых переменных і 1, 4,loCJ .Процедура чистки циклов уменьшает время выполнения цикла путем удаления из его тела арифметических выражений или их частей,не зависящих от управляющей переменной цикла.Процедура преобразования рекурсивно определяемых переменных в ряде случаев приводит к замене медленно выполняемых машинных команд более быстрыми. (Рекурсивно определяемая переменная - это переменная,значение которой при каждом выполнении цикла увеличивается или уменьшается на постоянную величину.В циклах,содержащих выражения, использующие такие переменные,есть возможность замены операции возведения в степень умножением и умножения - сложением. J Кроме того,в системах оптимизации программ часто применяется процедура оптимизации выражений [ 5*,6у 13- .суть которой состоит в поиске в программе семантически эквивалентных подвыражений и размещении их таким образом,чтобы избежать дублирования вычислений. Такая процедура особенно эффективна,когда с помощью ее
применения удается избежать повторения вычислений в цикле.
В данной работе задача экономной организации вычислений в циклах ставится более широко и решается более общими методами. Именно,пусть имеется набор итерационных вычислительных формул. Естественное желание построить вычисления так,чтобы на каждом итерационном шаге по возможности полнее использовались результаты предыдущих шагов,приводит к задаче сопоставления исходным формулам систем рекуррентных соотношений,определяющих те же вычисления. Пусть Ї =(}^) и і - набор переменных и требуется вычислить значения функции 1.(2,1) при l=W,ltt+i,...,)i(?Wt}H -целочисленные переменные) .Если этой функции можно сопоставить рекуррентное соотношение
((ї,і)Щ(фі),..ф,і-]),г,і) ,где :!(г,т)= ЧЦг),..., |(z,w.+j-l)= ),
и вычисление правой части (1) при известных (,L~i)r...l(z;L.-j) проще,чем непосредственное вычисление Lfefі) для каждого І , то это рекуррентное соотношение дает нам способ более экономной, по сравнению с непосредственным вычислением,организации цикла. Простейшие примеры зависимостей вида \L) : X - ОС X,
/»(L-i)M, -Ji = (i-iVh + h.
Итак,задача состоит в автоматическом построении по данным вычислительным формулам рекуррентных соотношений и в исследовании способов получения по возможности лучших Г с точки зрения экономии) соотношений.В диссертации эта задача решается сначала для отдельной функции 1(,1) ,значения которой необходимо вычислить при Ь~m?Hl+ir..,/t .Затем решение распространяется на произвольный набор формул.
В первой главе выделяется некоторый класс систем рекуррентных соотношений ( CPCJ ,а затем предлагаются методы сопостав-
ления систем этого класса заданным формулам и,соответственно, методы построения программ по заданным формулам.
В I определяются модели итерационных вычислений,которые будут рассматриваться в диссертации,и дается неформальная постановка задачи.В 2 определяются типы рекуррентных соотношений, сопоставляемых тем функциям,значения которых необходимо вычислять в цикле,а также указываются некоторые полезные свойства систем рекуррентных соотношений.Наряду с СРС общего вида (Ji) рассматриваются системы вида
' (V- і
составляемые из заданных наборов функций и знаков операций Oir..PQк ( ^J^X^^^W'^t-"^ ).Система вида СЯ) называется смешанной СРС,целое 1С - ее глубиной,а СРС для -f і[2,і) - подсистемой порядка ^ данной системы.В классе смешанных систем выделяются подклассы простейших О -систем ( системы вида 1$\ ,в которых все О/ = О j, О ^= {+>*:> ^\ Сформулированы критерии,которые позволяют,например,выяснять,является ли функция ^0(г-3і) определяемая смешанной системой, тождественно равной нулю или единице;можно ли по данной СРС получить систему меньшей глубины,определяющую ту же функцию;совпадают ли функции,определяемые различными сиетемами;имеются ли у двух данных СРС совпадающие подсистемы и т.д.
В 3 описывается метод построения по арифметическому выражению Р(?Д) .задающему функцию I(?, і),систем рекуррентных соотношений.Вначале определяются базовые операции,позволяющие
при известных СРС,сопоставленных некоторым выражениям,получать новые системы,соответствующие более крупным выражениям.Построение систем рекуррентных соотношений,соответствующих данному выражению Jrfe,l) .проводится за один обход в концевом порядке бинарного дерева,задающего это выражение.Техника построения CPG иллюстрируется примерами.
В 4 показано,как с помощью найденных для данной функции t(Zy'l) систем рекуррентных соотношений можно построить оператор цикла для экономного вычисления значений этой функции.Разбираются соответствующие примеры.В 5 показано,как методы из 2-3 применяются для организации циклических программ по данным итерационным вычислительным формулам.Вначале рассматривается случай одной вычислительной формулы вида ^=^.(2, i) , затем -
случай нескольких вычислительных формул.Рассмотрен также случай,
когда итерация проводится по нескольким параметрам Ц, ^,..., 1^. .
Базовые операции над СРС являются частичными,т.е. результат их применения не всегда определен.Поэтому построение по данной функции -М?,) систем рекуррентных соотношений в общем случае приводит к выражению,операндами которого служат СРС.Непосредственное продолжение процесса построения новых систем для этого выражения невозможно.Можно попытаться продолжить построение СРС ( увеличив тем самым экономию вычислений ) .выполнив предварительно некоторые эквивалентные преобразования выражения. Определению набора преобразований выражений,связанных с СРС,проведение которых позволяет продвинуть дальше процесс построения новых систем и получить при этом по возможности большую экономию вычислений,посвящена вторая глава диссертации.
Всевозможные эквивалентные преобразования выражений,связанных с СРС,разбиваются на две группы: IJ преобразования,результат выполнения которых не зависит от конкретного вида функ-
ций Ф (г),,.., fk(г),входящих в имеющиеся системы,а зависит только от типов систем и их глубин (т.е. преобразования, которые проводятся в предположении произвольности этих функций^ ; 2) преобразования,результат выполнения которых существенно зависит от наборов таких функций,входящих во все имеющиеся системы. В 1-3 обсуждаются преобразования первой группы,в 4 -второй.
В I дается формальная постановка задачи построения такого преобразования данного выражения,операндами которого служат -V-системы и X-системы,которое приводит к наибольшей экономии вычислений.Затем определяется набор элементарных преобразований, который по существу является набором некоторых базовых операций над CFC.B 2 показано,как исходя из набора элементарных преобразований и преобразований,использующих свойства коммутативности- и ассоциативности сложения и умножения,построить по данному выражению преобразование,приводящее его к. наиболее экономному виду.
В 3 показано,как получить преобразование с аналогичным свойством,исходя из набора элементарных преобразований и преобразований, использующих свойство дистрибутивности умножения относительно сложения.Искомое преобразование строится поэтапно,и на каждом этапе решаются задачи,требующие перебора многих вариантов.Во всех случаях,за счет использования свойств. СРС,полного перебора удалось избежать ( доказаны соответствующие теоремы ) . На одном, этапе построения число рассматриваемых вариантов сведено от ft/ (Л. - количество пар скобок в данном выражении j к 2 ( в худшем случае \ и доказана возможность применения бектрекинга, что, вообще говоря,позволяет сократить перебор.На остальных этапах задача построения искомого преобразования решается вообще без перебора.В конце 3 предложенные методы пос-
троения преобразований распространены на выражения,операндами которых служат не только простейшие СРС,но и смешанные системы.
Преобразования второй группы,рассмотренные в 4,основаны на поиске в выражении совпадающих СРС или систем с совпадающими подсистемами и на распознавании эквивалентности некоторых подвыражений ( или СРС) нулю или единице.Центральное место здесь занимает выбор метода сравнения систем рекуррентных соотношений, т.к. при их сравнении возникает задача распознавания функциональной эквивалентности выражений.Предложено решение этой задачи,не выходящее за рамки рассмотренных методов построения СРС.Выделен класс выражений,в котором эта задача предложенным методом решается полностью.
В 5 продолжено обсуждение вопросов^рассмотренных в 5 первой главы.В частности,рассматривается задача сводимости СРС общего вида {і] к смешанной системе вида (Щ) .Предлагается способ решения этой задачи,не выходящий за рамки методов построения СРС.Затем рассматривается случай нескольких вычислительных формул.Если некоторым переменным, стоящим в этих формулах в левых частях операторов присваивания,сопоставлены системы вида
,то можно рассматривать преобразования,состоящие в замене вхождений этих переменных в правые части присваиваний на соответствующие им СРС.После таких замен,вообще говоря,можно продолжить процесс, построения новых систем и получить дополнительную экономию вычислений.
В третьей главе обсуждаются некоторые вопросы реализации методов,рассмотренных в первых двух главах,и описывается структура реализующей эти методы Паскаль-программы.В I обсуждаются используемые в программе типы данных.В 2 описываются принципы построения программы и основные используемые процедуры и функ-ции.Кроме того,приводятся результаты применения описанной прог-
раммы к задаче сопоставления систем рекуррентных соотношений формулам,задающим вычисление значения определенного интеграла методом прямоугольников для различных подынтегральных функций.
Основные результаты работы представлены в [ 15 \ и состоят в следующем.
Разработан алгебраический аппарат сопоставления итерационным вычислительным формулам систем рекуррентных соотношений.С помощью этого аппарата получен способ экономной организации вычислений в циклических программах,позволяющий на каждом шаге цикла учитывать результаты предыдущих шагов.Разработан программный комплекс построения систем рекуррентных соотношений и последующей генерации экономных циклических программ.
Полученные результаты могут использоваться при создании систем оптимизации программ.Кроме того,их можно использовать для приведения получаемых с помощью систем аналитических преобразований ( ШОСЕ-Х .MACSYMA) вычислительных формул к виду,определяющему экономный способ вычислений по этим формулам в цикле.
Автор пользуется возможностью выразить свою признательность Сергею Александровичу Абрамову за постоянное внимание и помощь в работе.
Построение систем рекуррентных соотношений
В этом параграфе описываются отдельные приемы построения новых СРС по уже имеющимся,а также общий метод построения систем рекуррентных соотношений непосредственно по виду данной функции.В конце параграфа будет определено расширение класса смешанных СРС.
Пусть функция -f-І Л) определяется системой рекуррентных соотношении Эту систему можно переписать в виде где ftto- ft) № Ч}(ЩН%&) "Р". /=44,..., -1 . Эти действия изменяют область определения функции f Г?, і) и определяют сдвиг данной системы на один шаг вперед.Аналогично можно определить сдвиг системы (і, 5) на г шагов вперед для произвольного положительного целого ь .Возможность применения к системам рекуррентных соотношений операции сдвига позволяет считать,что у всех рассматриваемых ниже систем соответствующие значения W. ш{{. X) совпадают.Кроме того,заметим,что после выполнения сдвига системы на t шагов вперед значение J(?3M.+) совпадает со значением первой компоненты ( 6?) "сдвинутой" СРС. Если дана система рекуррентных соотношений (І. 5") ,то есть СРС,полученная из исходной Jf(2 i) сдвигом ее на один шаг назад.Заметим,что сдвиг СРС назад не всегда определен.
Определим теперь на множестве простейших СРС функционал Гл ,так что 1/\ (-fl?,l))= К ,если функция - определяется системой глубины К .
Пусть функции fcO и 4.(2,1) определяются с помощью + -систем а функции //"2,1) и (?,(.) - с помощью X-систем Рассмотрим некоторые способы построения новых СРС по уже имеющимся. При этом будем получать соотношения,связывающие глубины данных систем с глубинами вновь полученных, і) Функция h[2,l) г (2,0 fyfeO определяется 4- -системой (і. Э) k ,i):W.+} .l)i ),..,i,(?)]5 .„.,„., в которой i)j(Z)«ft( )+ Tj )J=0A"., ( ,4) и йЫ при /=жік( ,К )+і,..., Кя ,а К Иіах , ) 2j Функция k(Z,l) = (2,1)- fy(?/i) определяется -ь-системой (t. Є) ,в которой 0/ = j Sb Jj (2) j=0,i,...,»un ,K ) и 3) Функция k(29h)- W2,0 Ife) ,где Jffe) не зависит от l , определяется + -системой (1-) tB которой = и 4) Функция к г,і)= ї.(г,і)х г,У определяется -Ь-системой (1. 3) ,в которой = + Ко и Здесь ( ) - число сочетаний из 4 по U . 5) Функция R(2,t) = 4д?,) Т ,где J -целое неотрицательное, определяется 4-системой (і. 9) ,в которой t = oX(f »а ції") при =0,І,..., К определяются при последовательном применении формул предыдущего пункта к функциям fy(?,t) и f"Z, і) , /2,0 і 3. и (г,1) и т.д. 6) Функция определяется 4 -системой (і. е), в которой Kk=fy и l)j(2)=A-(fyfe)) ,j 0,ir..9 &k .
Заметим,что любую функцию (г) ,не зависящую от і ,можно рассматривать как систему рекуррентных соотношений глубины О . Поэтому из рассмотренных выше случаев построения СРС следуют такие соотношения: 7) Функция k(,l) = f (?,L) $/?»0 определяется x -системой в которой i) )= z) ,J= ... tV( K3) н )=( KV при 4=шь(Ц,ц)+1,...7Кь »а fcfc.= Wtf(fy,Kg) . 8) Функция Kf?,c) = -ff?,0/SfeO определяется х -системой (i.U),в которой l)j(? -(2)/ ) npH v..; K( ,Kg) и Используем определения двух последних пунктов и сформулируем еще одно полезное свойство X -систем,которое будет использоваться позднее.
При этом для вычисления очередного значения к(%,1) с помощью смешанной системы необходимо выполнить ,() операций сложения и одно умножение,вместо Jtle) умножений,необходимых при вычислении того же значения по формулам,задаваемым системой (1. 5) . Еще одним примером смешанной системы может служить СРС для функции k(3,t)=}(fe) (2,(.) ,где \[(ї) не зависит от I ,а М Х) из (і. %) .Функция Ш,с) определяется в этом случае системой к(гДИ ,4д(«Ш;0,и ,х, ),---, У (г)}.
Методы построения новых смешанных систем по данным реализуются на основе применения методов построения простейших СРС. Например,если функции f(Z9i) и $(-2,0 определяются системами 8(2.0-. (Кх, у/ф, ж-к,+,y/m ДО ),..., ft\ft) 5 ,то функция fo(z t)s f(?,i)x #Ґ?Д) определяется системой k(z,i)-. , ), +1,+, Й,Шг),..., ft Ф ї .где к = К/ Л. Vif"2)- V(2) V/(?) ,a-f-подсистема к ,с) определяет функ-цию -fif O g/ i) ( здесь-ft(г,і) ,і(ї,і) - подсистемы порядка 1 систем /(2,L) и 5(2-,t) соответственно").
Заметим,что не всегда при построении новых систем мы получаем СРС вида (і. Л) .Пусть снова %&Л) (0М Лс(г)»- Тк fe)lf и Ю1 ,В этом случае функция ri / \ і = 1 из (і. 1Ь J уже не может быть определена с помощью системы вида (1.. j .Эффект экономии вычислений в этом случае зависит от того, насколько вычисление значения 9( w проще,чем непосредственное вычисление k(?7i) .Рассмотрим пример.Пусть требуется вычислить значения функции иШ-(( Л\) при І=0,{,..., ІЛ. .Функция (0=1 определяется + -системой Ді) {0}+, О, і, 2. .Функция kfі) - (Iі) f определяется системой вида (і. 13)
Реорганизация циклов в программах с помощью построения систем рекуррентных соотношений
Запись вида (і.іо) можно рассматривать как систему рекуррентных соотношений общего вида (і. {) ,т.е. считать, что набор значений 2t при 6= ,.-.,я,... определяется с помощью СРС и эту СРС формально сопоставить переменной 2± .
Рассмотрим теперь методы реорганизации циклов с несколькими операторами присваивания в теле цикла.Пусть по-прежнему і меняется от їй. до VL .В простейшем случае тело цикла имеет вид (і. Н) г»-. = («,0; где Т:- ?и+1 у, Z &") .Здесь,как и в случае тела цикла вида (і. lh) »по каждому выражению F;(2,i) /- і,-.-, строятся системы рекуррентных соотношений и с их помощью организуется новый цикл.Т.е. в этом случае метод реорганизации состоит в многократном повторении метода для случая (іЛЬ) .Остается справедливым и замечание, об отображении CPG для -/:(2,0 на массив. Если какое-нибудь присваивание в (д. 5 і) имеет вид : = Х(2:2, I j ,то к реорганизации привлекается и метод, использовавшийся в случае тела цикла вида Ц. і 9) .
Более сложным является случай,когда некоторые функции «// , J = i,—,W зависят еще и от переменных х ,..., ,где 1 ir4 и і..., 1 tf"j U ,т.е. тело цикла имеет вид. где 1 tfj/ U ,/= ,-," ,P= - j и все ,P5 ,...,- j различны. Вообще говоря в этом случае можно было бы ограничиться простейшей реорганизацией,являющейся обобщением метода для цикла с те лом вида (1.1) .Т.е. по каждому выражению (2 ,..., ) построить СРС для подвыражении этого выражения,не зависящих от ї (5-І ,...,2: , .При этом (і.&&) заменится на где g (2, L) , k = і,.. v u j-1,-,( к - системы рекуррентных соотношений.Затем с помощью систем из (і.ДЗ) организовать новый цикл,аналогичный приведенному на стр. ЦЦ .Однако следует заметить, что такая простейшая реорганизация может либо вообще не привести к экономии вычислении,либо дать, экономию меньшую той, на которую можно рассчитывать при более детальном рассмотрении выражений (і. ДЗ) .Например,если исходный цикл имеет вид ОС: - - k j jn 1:-0 sbeg і ub.jU к do SeqiVL ОСi-cос + t ; %:-= осі"5 eW 1 то упомянутая "неполная" реорганизация приведет к циклу с точно такими же операторами присваивания и с тем же объемом вычисле-ний.Цикл вида -fОТ. i -O Z± і uwkl ід do ІЩІЖ ОС: = І к Ч : - ОС f 3 ЄЛьд[ после "неполной" реорганизации сведется к предыдущему циклу.Если же заметить,что -f-систему { 0}+, 0, к ) .определяющую функцию U , можно формально приписать переменной ОС ta затем подставить эту систему вместо ОС в правую часть оператора = % f"S , то в этой правой части можно продолжить построение СРС.Выражение - 47 0 3 будет определяться при этом + -системой [0,+909к ,к ,6Jt J и исходный цикл заменится на 0С:= О; ai:= к; р= 0; #J:= к f 3; у := хИЗ; Аефл ос— oc + oct; y-- y + Xij
Аналогичный результат можно получить ж для первого из циклов со стр. б ,если заметить,что подвыражение I выражения Oc+fo определяется 4. -системой {0}+} It} и по виду выражения ОС: = ОС + { 0,+-, 1 переменной ОС можно приписать -ь -систему {0,+-, k, k J, в которой 9с" обозначает то значение,которое переменная ОС имела перед входом в цикл.
Итак,чтобы выполнить реорганизацию цикла более качественно, необходимо из выражении,стоящих в правых, частях в (4. 2ъ) выбрать такие выражения Д . ,которые можно подставлять в оставшиеся выражения At, вместо їг ,и после таких подстановок попытаться продолжить построение систем рекуррентных соотношении
Следует заметить, что даже если после такой подстановки удается продолжить, построение СРС,результирующий способ организации цикла не всегда оказывается наилучшим.Например,после реорганизации цикла проведенной с помощью построения СРС и выполнения подстановок, получится цикл,в котором вместо одного умножения,как в исходном цикле,используется ^ сложения.Будет ли в этом случае новый цикл экономичнее исходного зависит от того,насколько медленне операции сложения выполняется операция умножения. Методы выбора из совокупности всех возможных подстановок набора подстановок,приводящего к наилучшему в некотором смысле результату ,будут обсуждаться во второй главе.Здесь же будет решаться задача выбора всех таких операторов присваивания из (4.2 2. ) ( ив (і. 2Z") ~) , подстановка правых частей которых, в оставшиеся после выбора операторы может привести к построению новых систем рекуррентных соотношений.
Преобразования,использующие свойства коммутативности и ассоциативности
До сих пор мы рассматривали произвольные тройки Р, X, / но теперь нужно вспомнить,что выражения,получающиеся после построения систем рекуррентных соотношений,таковы,что в них невозможно построение новых СРС.Это значит,что к определяемым этими выражениями тройкам Р, X, Y У невозможно применение преобразований Y4 » Уа и Y »а применение преобразования Jf4 ограничено. Под невозможностью применения преобразования У здесь понимается то,что в выражении Р не находится соответствующего подвыражения,т.е. выполнение Jj\ не изменяет исходной тройки. Поэтому будем привлекать для работы с такими выражениями преобразования еще двух типов: преобразования,использующие свойства коммутативности и ассоциативности сложения и умножения,которые состоят в перестановке некоторых членов выражения Р ,и преобразования, использующие свойство дистрибутивности умножения относительно сложения,которые состоят в раскрытии некоторых скобок в выражении Р .Необходимо определить такую суперпозицию этих преобразований и элементарных преобразований,которая максимально уменьшала бы суммарный вес тройки 4. Р, X, Y / .
Рассмотрим такую тройку Р, X?Y) ,что к ней невозможно непосредственное применение ни одного из преобразований у. , Ul,...,fy ,и попытаемся так переставить члены выражения Р используя свойства коммутативности и ассоциативности сложения и умножения,чтобы к полученной тройке 4,9 , Х,ї можно было бы применять преобразования У. , 1 = 1,...,// возможно большее число раз.
Пусть QL обозначает одно из множеств X или Y ,а й. -одно из множеств {+,-] или { /} .Определим преобразование ( Р,ХЛ ) = Р ,Х,У ,представляющее собой такую перестановку членов выражения Р ,что Р эквивалентно Р и в Р появляются максимально возможные по размерам подвыражения,состоящие только из переменных из Q. и знаков операции из & .Каждое из этих подвыражений в Р можно будет затем свернуть до минимальных размеров подвыражения,состоящего из одной переменной,с помощью одного из преобразований У і , If а. или Уз .Например, если P=Cd+ 1( 3.+ - 2)+ 1/ + 3"" 5- .то после выполнения преобразования С " будет 9 = (+ 9 -9 )+&((з - з)+&) + #з Применение к Р X,Y преобразования Yj дает 49", Х 3 Y У » где Р"= 0С% + (3+ ) + » У-і » 9 - новые переменные,а Л+(с{ )= + + +4+ +3-УИАХ&Л)- W(4VJ) O .
Будем обозначать дерево,задающее выражение Р через Тр ,а выражение,состоящее только из переменных из О. и знаков операций из О. через 3)оД Q) .Для нумерации таких выражений будем использовать верхний индекс.Алгоритм,реализующий преобразование CQ_ основан на следующем очевидном утверждении: две переменные tyL и fy из Q. ,входящие в выражение г ,могут попасть в результате применения к Р?Х, Y преобразований,использующих свой ства коммутативности и ассоциативности,в одно подвыражение % ( 0 в том и только в том случае,когда единственный в7 путь между 0 и fya содержит в своих внутренних узлах только знаки операций из (X .
Вместо исследования путей между каждыми Q,, и СЬ« из fl. (і ф }\ »входящими в Р ,в отдельности,алгоритм за один обход дерева Тр в концевом порядке рассматривает сразу все пути в Тр .Будем обозначать операции из #. знаком ф .Кроме выражений Di(Q) алгоритм имеет дело с подвыражениями,которые не обладают свойством состоять только из переменных из б и знаков операций из & .Будем называть такие подвыражения неподходящими и обозначать их буквой Н .Пусть А обозначает некоторый узел дерева Т р ,тогда через P(2U обозначим выражение,задаваемое поддеревом с корнем в X .
Для каждого концевого узла IX действия,выполняемые алгоритмом, заключаются в объявлении Р(3() либо неподходящим подвыражением,если 9( Gi ,либо новым %( Q) ,если PI QG-Q . Заметим,что для любого концевого узла "Л выражение есть просто отдельная переменная.
Основные процедуры и функции
Для внутреннего представления систем рекуррентных соотношений и работы с СРС в программе определен тип данных с именем RKi? (от fUc«b fcwi fcdfxliovi Syltewi ) .На выбор структуры данных типа Ro повлияли следующие соображения.Системы рекуррентных соотношений приписываются узлам бинарного дерева, задающего исходное выражение.Любая СРС вида [L. А.) определяется набором функций и набором знаков операций Оц ,...,0 .Каждая из функций ty;(2) i-Q,Lr" K -компонента СРС - определяется некоторым выражением,которое,в свою очередь,задается бинарным деревом.Кроме того,любая из функций У і (?) , І-0,{7„.,К (или некоторые подвыражения задающего ее выражения ) может определяться системой рекуррентных соотношений по некоторой переменной - (4-"-3) .Итак, исходное выражение задается деревом,узлам которого приписываются СРС. Система рекуррентных соотношений есть список компонент -У:(i) , J = i,.. K ,каждая из которых,в свою очередь задается деревом, узлам которого тоже могут быть приписаны СРС,и т.д.Это и определяет используемую структуру данных.На рисунке I приведено полное описание типа 23 .В этом описании определено сразу четыре типа данных: переменная типа RRtS будет иметь значением ссылку на некоторую компоненту системы рекуррентных соотношений; переменная типа PTR - ссылку на узел некоторого дерева; переменная типа СОИР представляет собой запись,определяющую некоторую компоненту СРС; переменная типа /V0.DF представляет собой запись,определяющую некоторый узел дерева.
Из приведенного на рисунке I описания видно,что каждая система рекуррентных соотношений задается списком своих компонент. Каждая компонента СРС может иметь дополнительные поля записи: в поле 3)ЕРТН записывается значение глубины данной СРС; в поле KI/VJ) - тип данной системы (+ , X или f для простейших и смешанных систем, 0 - для систем общего вида ) ; в поле Л/Дпг записывается имя переменной,по которой построе на данная система; в поле STAZ1 - начальное значение этой переменной. Все компоненты любой СРС имеют такие поля записи: /VF XT - ссылка на следующую компоненту и ГА/1 Т - ссылка на корень дерева,задающего соответствующую функцию Ц : (?) .
Любой узел дерева ( переменная типа 1\[0Ы: ) имеет поля LL И. KL ,указывающие на левое и правое поддеревья данного узла; YST - ссылка на приписанную узлу систему рекуррентных соотношений; поле SIG-A/ ,имеющее значение і ш& ,если узлу приписана СРС и значение J cJ. . в противном случае; поле X/V/F содержащее имя переменной,число или знак операции (имя функции J расположенные в этом узле.
Рассмотрим пример. Функция &1 +1 , і = ,... определяв тся у -системой {О, Х,й3й, О? J .Пусть переменная U типа #RS указывает на эту систему во внутреннем представлении ( внутреннее представление этой СРС показано на рисунке 2 Переменная U4#NEXT будет иметь значением ссылку на под систему порядка 1 исходной СРС - {і,х, (Я, Q } ;переменная Uf.A/XTf. FXTt.lA/ГТ - ссыжу на корень дерева,задаю щего выражение d f из третьей компоненты исходной СРС зна чением (7 f. ІД/TTt. ГА/F будет строка Д .
Из всего сказанного выше видно,что системы рекуррентных соотношений и выражения представляются в описываемой программе фактически одинаковыми структурами.Это позволяет ( как уже отмечалось в Гл. I ) применять для обработки выражений и СРС общие методы.При этом большинство процедур работы с СРС ( выражениями ) имеют естественное рекурсивное описание.
Описанный в этом параграфе тип № предназначен для отображения смешанных систем рекуррентных соотношений, т. е. систем вида (і»й) .Но он может быть легко приспособлен для отображения СРС общего вида и систем вида (і, 16) . Причем это можно сделать не за счет изменения описания типа,а договорившись о стандартном способе представления таких систем с помощью типа
