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