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