Cтраница 2
Только что доказанная теорема является основной в нашей общей теории. Она обосновывает весь наш подход к задаче экономии памяти. [16]
Эти слова подсказывают нам, что мы, решая задачу экономии памяти, должны просмотреть операторы программы в порядке их выполнения. Тогда ( в случае линейной программы, записанной в столбик) выше очередного просматриваемого нами оператора будут операторы уже выполнившиеся, для которых мы уже как-то распорядились выбором величин, и ниже будут команды, еще не выполнившиеся. Мы не торопимся ввести новую величину для результата очередного оператора S, а смотрим на величины, обозначающие результаты операторов, стоящих выше. Что значит, что величина и, которая была результатом оператора R, еще не освободилась. Это значит, что ниже оператора S есть еще один оператор, Т, имеющий v своим аргументом. Достаточно ли точное это определение. [17]
Одним, словом, мы должны дать теперь математическую постановку задачи экономии памяти и на базе этой постановки дать точно описанный метод ее решения, после чего мы сможем вернуться к задаче практического применения этого метода. Этому будут посвящены дальнейшие главы первой части. [18]
В то же время в предисловии им было сказано, что задача экономии памяти будет рассматриваться как пример прикладного исследования. [19]
В этой главе, оставаясь на уровне рассмотрения абстрактных объектов, мы постараемся попять, как все эти объекты могут бЕлть построены: как найти компоненты связности информационного графа, как определить множества R ( что просто) и Т ( что существенно сложнее), как, наконец, найти наилучшую раскраску графа несовместимости. Для этих построений нам нужно найти систематические процедуры, которые могут быть положены в основу практического решения задачи экономии памяти, например, на ЭВМ с помощью алгольных программ. [20]
Похоже, что мы уже исчерпали вс & полезные факты, которые нам могут дать линейные программы. Главными нашими достижениями являются открытие важности анализа информационных связей программы, а также извлечение из программы тех и только тех ее характеристик, которые нам помогают в решении задачи экономии памяти и которые изображаются в виде ее операторной схемы. После того как мы уже несколько освоились с этой находкой, давайте разберем подробнее, что такое информационная связь, как мы ее находим по заданной программе и как используем для распределения памяти. S к Т ведет цепочка операторов, и, наконец, в этой цепочке ни одни из операторов не имеет х своим результатом. Для построения информационных связей и вообще, для решения задачи экономии памяти, нам достаточно иметь операторную схему программы, в которой указаны символы операторов, их аргументы, результаты и сопоставленные им имена величин, а также порядок выполнения операторов. [21]
В первой части рассматривается задача экономии памяти в операторных схемах программ. Конструкции и понятия, вошедшие в теоретическое программирование в связи с решением этой задачи, не только внесли существенный вклад в развитие предмета, но и стали основой широкого класса преобразований программ, применяемых в системах автоматизации программирования и при проверке правильности программ. Задача экономии памяти рассматривается как пример решения прикладной задачи с применением математических методов. Изложение разбито на главы, в каждой из которых анализируется один из неотъемлемых этапов полного решения прикладной задачи: содержательная постановка задачи, точная постановка и общая теория, поиски конструктивного метода решения, затем его алгоритмизация и, наконец, составление программ на алгоритмическом языке. [22]
Книга представляет собой цикл лекций, пвппсашшх в видз беседы с читателем. Подробно рассматриваются две классические задачи теоретического программирования, решения которых и развитые на этих решениях методы привели к созданию теоретического программирования как самостоятельной математической дисциплины. Это - задача экономии памяти в схемах Лаврова и задача построения полной системы преобразований в схемах Янова. [23]
Это очень важно с точки зрения конкретной реализации процедуры экономии памяти: направленный процесс получения однозначной информации о попарной несовместимости связок отделяется от сугубо неоднозначного, комбинаторного поиска наилучшей раскраски, которая к тому же сама по себе является известной математической задачей. Заметим, что к идее раскраски вершин графа как средства экономии памяти можно прийти, как говорится, с налета, без понятия информационных связей. Рассмотрим задачу экономии памяти как желание поместить в одну ячейку памяти побольше величин так, чтобы суммарный расход памяти оказался бы наименьшим. Две величины несовместимы, если их нельзя поместить в одну ячейку памяти, и совместимы в противном случае. Это отношение несовместимости можно представить в виде графа, вершинами которого являются величины, а ребра соединяют несовместимые величины. [24]
Следуя Кантору, мы должны говорить о множестве объектов, если появляется определенная необходимость рассматривать их все вместе или хотя бы любой из них. Посмотрим, как обстоит дело у нас. У нас есть задача - для заданной операторной схемы найти наилучшее допустимое распределение памяти. Это означает, что при решении задачи экономии памяти схема фиксирована, меняется только распределение памяти. Множество допустимых распределений памяти нам нужно обязательно - среди них нам нужно выбрать минимальное по числу используемых величин. Однако у нас нет необходимости сравнивать одну операторную схему с другой, которая отличается чем бы то ни было более существенным, нежели распределение памяти, даже если она решает ту же задачу ( например, примеры 4 и 5 в глав 1) - мы сами вынесли такие сопоставления за рамки нашей теории. [25]
Похоже, что мы уже исчерпали вс & полезные факты, которые нам могут дать линейные программы. Главными нашими достижениями являются открытие важности анализа информационных связей программы, а также извлечение из программы тех и только тех ее характеристик, которые нам помогают в решении задачи экономии памяти и которые изображаются в виде ее операторной схемы. После того как мы уже несколько освоились с этой находкой, давайте разберем подробнее, что такое информационная связь, как мы ее находим по заданной программе и как используем для распределения памяти. S к Т ведет цепочка операторов, и, наконец, в этой цепочке ни одни из операторов не имеет х своим результатом. Для построения информационных связей и вообще, для решения задачи экономии памяти, нам достаточно иметь операторную схему программы, в которой указаны символы операторов, их аргументы, результаты и сопоставленные им имена величин, а также порядок выполнения операторов. [26]