Задача - экономия - память
Cтраница 1
Задача экономии памяти ставится как задача найти среди допустимых распределений памяти для заданной операторной схемы с построенными информационными связями распределение, требующее наименьшее число величин. Допустимым считается такое распределение памяти, при котором для любой информационной связи сохраняются все реализующие ее маршруты. [1]
 |
Факторизация графа переходов. [2] |
Для каждого гамака задача экономии памяти решается отдельна в отношении его локальных величин, после чего эти гамаки 1-го ранга редуцируются в вершины - элементарные операторы по отношению к остальной схеме. В полученной схеме снова выделяются линейные компоненты и, стало быть, только что описанный двухчастный этап повторяется снова. [3]
В первой части рассматривается задача экономии памяти в операторных схемах программ. Конструкции и понятия, вошедшие в теоретическое программирование в связи с решением этой задачи, не только внесли существенный вклад в развитие предмета, но и стали основой широкого класса преобразований программ, применяемых в системах автоматизации программирования и при проверке правильности программ. Задача экономии памяти рассматривается как пример решения прикладной задачи с применением математических методов. Изложение разбито на главы, в каждой из которых анализируется один из неотъемлемых этапов полного решения прикладной задачи: содержательная постановка задачи, точная постановка и общая теория, поиски конструктивного метода решения, затем его алгоритмизация и, наконец, составление программ на алгоритмическом языке. [4]
 |
Факторизация графа переходов. [5] |
Оба способа уменьшения объема задачи экономии памяти основаны на том, что мы умеем выделять такие части программы, в которых гарантированно содержатся маршруты интересующих нас информационных связей. [6]
Теперь мы можем сказать, что задача экономии памяти в заданной схеме G ( S, X, L) состоит в нахождении среди схем G ( S, X, L) любой такой схемы, вычисляющей G, у которой X будет иметь наименьшую мощность. [7]
В указанной работе Ершовым был сделан шаг в сторону решения задачи экономии памяти для программ, содержащих массивы. [8]
Не углубляясь в проблему по существу, отметим только, что задача экономии памяти при наличии массивов заметно усложняется. [9]
Опять-таки автор может рассчитывать, что часть читателей, прочитав условие задачи экономии памяти в этой формулировке, усмотрит в пей прямую связь со знаменитой задачей теории графов - задачей о раскраске вершин графа: надо раскрасить вершины графа в наименьшее число красок так, чтобы никакая пара смежных вершин не оказалась раскрашенной одной краской. Этот факт сам по себе очень интересен, но сейчас мы не будем отвлекаться, а опять вернемся к нашему примеру. [10]
Мы, далее, нашли, какая информация о программе существенна для систематического решения этой задачи экономии памяти. Для этого нужно знать перечень операторов программы и для каждого оператора знать, какие операторы могут выполняться непосредственно за ним. Для каждого оператора нужно, кроме этого, знать, сколько он имеет аргументов и результатов и какие величины им сопоставлены. Вся эта информация задается в виде операторной схемы, которая наглядно изображается в виде графа ( мы уже использовали это слово для графа несовместимости), где вершины - прямоугольники обозначают операторы, а стрелки показывают возможный порядок перехода от одного оператора к другому. [11]
Этот небольшой экскурс в комбинаторику, каким бы поверхностным он ни был, достаточен для нас в одном: любая попытка поиска минимальной раскраски прямым перебором всех возможностей обречена на провал, если нас интересует эффективное решение задачи экономии памяти. [12]
Мимолетная ссылка на материал первой главы дает нам повод перевести дыхание после сугубо делового тона текущей главы и оценить степень нашего прогресса. Наша задача экономии памяти, какой бы скромной она ни казалась, отражает тем не менее многие типичные стороны любого математического исследования. В частности, на материале наших первых трех глав мы можем обратить внимание читателя на различие познавательной и прикладной, или, точнее, конструктивной, частей нашего исследования. [13]
 |
Факторизация графа переходов. [14] |
Этот процесс повторяется до тех пор, пока после очередной редукции схема не превратится в одну или несколько изолированных вершин. Таким образом, решение задачи экономии памяти большого объема свелось к последовательности задач, каждая из-которых может иметь существенно меньший объем вычислений. Поскольку сложность алгоритмов экономии памяти пропорциональна по крайней мере квадрату числа вершин в графе переходов, такая факторизация, хотя и приводя к решению нескольких задач вместо одной, может давать большой выигрыш во времени, хотя и за счет, быть может, несколько худшего распределения памяти. [15]
Страницы: 1 2