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