Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.10.2024

Просмотров: 90

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

среди них представляют работа С. С. Лаврова [48], в которой рассматривается глобальная экономия памяти для операторных схем программ, и работа Т. Мерилл [56], в которой рассматри­ вается система эквивалентных преобразований в двух указанных аспектах.

Имеются различные варианты решения проблемы экономии памяти. В общем случае экономия памяти будет достигаться толь­ ко тогда, когда имеется возможность сопоставления одной ячейки

памяти нескольким

объектам программы — совмещения

объектов

в программе.

 

 

Согласно теории

глобальной экономии памяти любой

допусти­

мый вариант совмещения величин получается в результате реше­

ния

известной

комбинаторной задачи — раскраски

вершин графа

несовместимостей, который строится по

операторной

схеме

про­

граммы.

Граф

несовместимостей

имеет

R

вершин,

где

R — ~Zrj.

Каждой величине Xj операторной схемы

сопоставляется

г,- — пол­

ный подграф

графа несовместимостей (где г,- число

попарно

смеж­

ных друг с другом вершин).

 

 

 

 

 

 

 

Пусть величинам х и у сопоставлены

подграфы G(x) и G(y).

Если

х и у нельзя совместить друг

с другом,

то все

вершины из

G(x)

и

G(y)

попарно соединяются

друг

с другом

ребрами. Если

х и у совместимы, то между вершинами

подграфов

G(x)

и

G(y)

не проводится ни одного ребра.

 

 

 

 

 

 

 

Соответствие между раскраской графа несовместимостей и ва­

риантом

совмещений величин определяется

следующим

образом:

все компоненты величин, соответствующие вершины которых окра­

шены одной краской, совмещаются друг с другом, отсюда

глобаль­

ная экономия памяти требует решения

трех

задач:

 

 

 

 

1.

Построение

операторной схемы.

 

 

 

 

 

 

2.

Построение

графа несовместимостей по операторной схеме.

 

3.

Раскраска

графа

несовместимостей.

 

 

 

 

 

В построении операторной схемы важное место занимает опре­

деление аргументов и результатов каждого

оператора

оператор­

ной схемы.

 

 

 

 

 

 

 

 

 

 

 

 

Определение аргументов и результатов операторов происходит

по

следующим

правилам/

 

 

 

 

 

 

 

 

1. Величина х является результатом оператора Л, если число

вхождений

х в

операторную схему

не

равно

числу

вхождений х

в оператор А и х появляется в Л в качестве результата

какой-либо

команды.

 

х

 

 

 

 

оператора А,

 

 

 

х

2.

Вершина

является

аргументом

если

впервые

появляется

в

Л не

в

качестве

результата.

 

 

 

 

Важным

вопросом

экономии

памяти

является

 

построение

графа несовместимостей по заданной операторной схеме.

 

 

Согласно теории величины х и у несовместимы,

если

имеют

место

зацепления

областей их действия

D(x)

и D(y).

Областью

зацепления

величины х

называется

компонента связанности носи-

96

теля множества всех маршрутов величины х в операторной схеме. Две области действия D(x) и D(y) зацеплены тогда и только

тогда, когда не пусто множество

 

# ( * ) П (H(y)U

 

В{у))[}Н{у)

П

(//(*)

U

В(х)},

 

 

где Н(х)

— множество

операторов,

являющихся

началом

хотя

бы

В(х)

одного маршрута величины х;

 

 

 

 

 

— множество

операторов,

являющихся внутренними

опе­

 

раторами хотя бы одного маршрута величины х.

 

Множество В(х) строится как пересечение

двух

множествЕ(х)

и Ь(х),

где Е(х) — множество всех операторов,

достижимых

при

движении по операторной схеме вдоль

стрелок,

 

отправляясь от

любого оператора, вырабатывающего х, a L(x)

— множество всех

операторов, достижимых

при движении

по схеме

против

стрелок,

отправляясь

от любого

оператора,

воспринимающего х

(движе­

ние обрывается при достижении оператора,

вырабатывающегох).

Раскраска

вершин

графа — сложная

комбинаторная

задача.

Задача построения алгоритма раскраски, который давал бы мини­

мальные

раскраски за приемлемое число элементарных действий,

в общем

случае считается неразрешимой.

Наиболее оптимальным подходом к решению задачи раскраски вершин графа несовместимости является следующий.

Массивы разбиваются на небольшие группы так, что веса мас­ сивов, попавших в одну группу, имеют одинаковые или близкие друг к другу значения. Веса разных групп резко отличаются друг от друга. Необходимо тщательно организовать совмещение вели­

чин одинакового веса. Для

величин же разного

веса

экономия

памяти

будет

достигаться

путем соединения

массивов

меньшего

веса в

массив

с

большим

весом.

 

 

 

Преобразование

программ, представленных

в

виде

так назы­

ваемых вычислительных цепей, позволяет минимизировать не толь­ ко объем требуемой памяти, но и время реализации. Вычислитель­ ная цепь реализуется линейной программой, не содержащей раз­ ветвлений, переходов и модификации адресов. Она представляет собой последовательность входных, выходных и вычислительных утверждений. Каждое утверждение имеет номер.

Входное утверждение представляет собой последовательность наименования входной переменной, ориентированной направо стрелки, и наименования ячейки памяти (указатель хранения). Например, входное утверждение

12)х—+М3

имеет номер 12, входную переменную х и указатель хранения М3. Выходное утверждение содержит наименование ячейки памяти (указатель выборки), ориентированную направо стрелку и наиме­

нование выходной переменной. Например,

2)М5—>у.

7. Заказ 4230.

97

Вычислительное утверждение образуется из наименования однозначной функции п аргументов ( n ^ l ) , ориентированной на­ право стрелки, и наименования ячейки памяти (указатель хране­ ния). Аргументы функции носят название указателей выборки вы­ числительного утверждения. Пример вычислительного утвержде­ ния:

3) Умн. (Mi, Mi) — > М 3 .

Два вычислительных утверждения относятся к одному и тому Же типу, если они содержат одну и ту же элементарную функцию и имеют одно и то же число указателей выборки.

Например,

7)

Дел (Л1ь

М 2 ) — * М 3 .

 

3)

Дел (Мг,

М7) г-+Мх

•

 

Утверждения в цепи образуют цикл в том случае, когда указа­

тели выборки данного утверждения являются

в то же время ука­

зателями хранения предшествующего утверждения цепи.

Пусть Si — не выходное

утверждение цепи

С и 5 j — не входное

утверждение С. Говорят, что S* есть прообраз

по отношению к 1-шу

указателю выборки

Sj

в том и только

в том случае, если

а) Si

встречается

в

цепи раньше, чем SJ;

 

 

б)

Mi — /-й указатель

выборки Sj

и Sj

имеет указатель хране­

ния

Mi;

 

 

 

 

 

 

 

SQ

 

в)

не

существует

такого утверждения

So,

что

встречается

между Sj и Sj в С и S0

имеет указатель хранения

Mi.

Если Sj-—

Если

Si — прообраз

Sj, то Sj называется образом Si.

прообраз

Sj, то объект,

помещаемый

в

память

посредством S,-,

есть один из объектов, выбираемых из памяти посредством

Sj.

«Предком»- А данного утверждения S цепи С называется

класс

утверждений

С,

образованных

следующим образом.

 

Во-первых,

S

есть член А,

во-вторых, любой прообраз

члена

Аесть также член А.

Утверждение в цепи С называется пустым, если оно не содер­

жится в множестве предков любого

выходного

утверждения С.

Это дает возможность установить, что

цепь не

содержит пустых

утверждений. Если этого оказывается недостаточно, то удаление всех пустых утверждений достигается путем объединения предков всех выходных утверждений и вычеркивания любого утверждения, не входящего в это объединение.

Если каждое невходное утверждение цепи имеет прообраз по отношению к каждому из указателей выборки, то цепь хорошо ор­ ганизована.

Если цепь хорошо организована, то каждое непустое и отлич­ ное от входного утверждение этой цепи имеет прообраз по отноше­ нию к каждому указателю выборки.

Цепь хорошо организована и не содержит пустых утверждений в том и только в том случае, если каждое невходное утверждение цепи имеет прообраз по отношению к каждому из его указателей

98

в ы ш е,

выборки и каждое из невходных утверждений цепи

является про­

образом

какого-либо

утверждения.

 

 

 

В дальнейшем полагается, что цепи

хорошо

организованы. Для

каждой

цепи

можно

построить так

называемую

сопряженную

цепь, которая

получается из первоначальной

путем

замены каж­

дого указателя выборки номером соответствующего прообраза и

исключения стрелок и указателей

хранения

из всех невыходных

утверждений.

 

 

 

Исходная цепь

Сопряженная цепь

1)

v—t-Mt

1)

v

2)

w^>M2

2)

w

3)

Ф , ( М Ь М2)=+Мх

3)

Ф,(1, 2)

4)

Л*,—>у

4)

3—+у

5) х=->М2

5)

х

6) Ф2(МиМ2)—>М3

6)

Ф2 (3,5)

7) M3-^z

7) 6—>2

Числа, которые в сопряженной

цепи заменяют соответствующие

указатели, называются числами сопряжения. Например, утвержде­ ние 6) в приведенном выше примере имеет числа сопряжения 3 и 5.

Поскольку указатели цепи соответствуют ячейкам оперативной памяти вычислительной машины, то существенно важно миними­ зировать число различных указателей цепи. Для этого необходи­ мо установить алгоритм перехода от данной цепи к другой, выра­ жающей ту же функцию, но использующей меньшее число различ­ ных указателей.

Существуют некоторые ограничения. Число различных указа­ телей в хорошо организованной цепи не может быть больше числа невыходных утверждений. Это следует из того, что каждое вход­ ное и каждое вычислительное утверждение включает в себя не бо­ лее одной ячейки памяти, не входящей в предшествующие утверж­

дения, что и определяет верхнюю

грань числа

указателей.

Пусть щ есть число различных

прообразов

1-го утверждения

некоторой цепи. Тогда цепь должна содержать

по крайней мере

«j различных указателей. Поэтому наибольшее

из чисел щ опре­

деляет нижнюю грань числа различных указателей цепи.

Алгоритм минимизации числа указателей цепи сводится к сле­

дующему:

 

 

 

а)

формируется

соответствующая

сопряженная

цепь;

б)

рассматриваются поочередно все невыходные

утверждения,

начиная

с первого.

 

 

 

Для

t'-ro утверждения:

 

 

1. Первая задача

состоит в выборе

указателя

хранения для

i-ro утверждения. Всякий указатель допустим в качестве указателя хранения в утверждении i, если этот указатель не используется уже в качестве указателя выборки в одном из утверждений, распо­ ложенных ниже L Если указатель, уже входящий в цепь в i или допустим в качестве указателя хранения, он выбирается

99

Смотрите также файлы