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

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

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

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

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

Добавлен: 21.10.2024

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

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

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

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

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

После того как указанным способом будут обработаны все невыходные утверждения, процесс заканчивается.

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

1)

х—>Mi

1)

х

2)

Af,—+у

2)

1-=+у

3 )

Ф,(А1,) — Ш 2

3 )

0 1 (1)

4 )

М2 —>2

4 )

3—>z

Поскольку в утверждение 1) в цепи вообще не входят указа­ тели, выбирается произвольно указатель, допустимый в качестве указателя хранения, например М{. Этот указатель вводится в схе­ му, а затем производится в соответствии с алгоритмом замена 1 на Mi всюду, где встречается число сопряжения 1:

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

Минимизированная цепь

1)

х—*А1,

1)

х—+Mi

2)

Mi—>у

2)

Af,—уу

3 )

Ф,(М,)

3 )

Ф,(Л1,)—•Л*,

4 )

3—^2

4 )

Mi-^z

Утверждение 2) представляет собой выходное утверждение и потому пропускается. Указатель Му допустим в качестве указателя хранения для утверждения 3 ) . Следовательно, Mi вводится в ка­ честве указателя хранения в 3 ) и производится соответствующая замена чисел сопряжения с номером 3. Другие невыходные утверж­ дения отсутствуют. , :

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

Исходная

цепь

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

1)

Ш

 

 

1)

w

 

2)

х

 

 

2)

х

 

3 )

У

 

 

4 )

Ф,(1,2)

А \

ф

1\

0 \

3 )

у

 

 

 

 

5)

Ф 2

(4,3)

5)

Фа

(4,3)

6)

5—>2

6)

5

—^2

• 100

После перестановки утверждений 3 ) и 4 ) получается цепь С.

Очевидно, С и С

эквивалентны, так как сохранены

связи меж­

ду прообразами и образами.

 

 

 

 

 

 

 

Перестановки

представляют

интерес

в связи

с

возможностью

уменьшения за

счет

этого

числа

указателей.

 

 

 

 

В

некоторых

случаях

анализ данной

цепи

позволяет

устано­

вить,

что объект,

представляющий

собой

результат

выполнения

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

идентичен

результату выполнения

предшествую­

щего

утверждения

S,-i

при

тех

же

входных

данных

цепи.

В этом случае говорят,

что Si

и St _i коррелированы.

Последнее

утверждение, являющееся избыточным, может быть исключено из

цепи. В следующем

примере утверждения 3 ) и 4 ) коррелированы:

 

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

 

 

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

цепь

 

 

1) W—УМХ

 

 

1)

W—УМХ

 

 

 

2) X—УМ2

 

 

2)

X—УМ2

 

 

 

3 )

Ф1(М1,М2)—УМ3

 

 

3 )

ФХ

(MVM2)—УМ3

 

 

4 )

0 1 (М,,М 2 ) — >М 4

 

 

 

 

 

 

 

5)

М3—уу

 

 

5)

Мл—>у

 

 

 

6 ) М4—yz

 

 

6 ) МГ—yz

 

 

 

 

Утверждение 4 ) может быть исключено.

 

 

 

Имеют

место два условия, при которых

пара

утверждений це­

пи

Si и Si-i

может

быть

коррелирована:

 

 

 

 

1) оба утверждения

и

являются

вычислительными

ут­

верждениями одного и того же типа

и имеют идентичную систему

прообразов;

 

 

 

 

 

 

 

 

 

 

2) оба утверждения 5г- и St _i являются

вычислительными

ут­

верждениями

и для любого i

t'-й прообраз 5г-_1 коррелирован с t-м

прообразом

Si.

 

 

 

 

 

 

 

 

не

Алгоритм

преобразования

цепи

Ct-_i в эквивалентную цепь С,-,

содержащую коррелированных

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

сводится к

сле­

дующему:

1.Образуется сопряженная цепь, соответствующая данной (указательной) цепи.

2.Определяется, отличаются ли два вычислительных утверж­ дения в цепи только номером утверждения. Если так, пусть i — номер одного из них, встретившегося раньше, и / — номер другого; исключается утверждение / и всюду в цепи число сопряжения / заменяется числом сопряжения L

Этот процесс повторяется до тех пор, пока не останется корре­

лированных

вычислительных

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

3. Путем минимизации образуется

соответствующая указа­

тельная цепь.

 

 

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

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

1)

у—>М,

1)

у

2) 0 , ( A f i ) — У М 2

2)

Ф,(1)

101

3) Ф 2 ( М 2 ) ^ М 3

3) Ф 2 ( 2 )

4)

0 i (М,)—>М4

4)

Ф,(1)

- 5)

Ф 2 (М 4 ) — >М 5

5)

Ф2 (4)

6) Ф3(М3,М5)—+М6

6)

Ф3 (3,5)

7)

М6 —>z

7)

6—>2

Утверждения 2) и 4) отличаются только номером утверждения,

поэтому утверждение 4) исключается

и всюду,

где встречается

число сопряжения 4, оно заменяется числом 3.

 

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

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

цепь

О

У

1)

У

 

2)

Ф,(1)

2)

Ф,(1)

 

3)

Ф2 (2)

3)

Ф2 (2)

 

5)

Ф2 (2)

 

 

 

6)

Ф3 (3,5)

6)

Ф3 (3,3)

 

7)

6—yz

7)

6—*г

 

Утверждения 3) и 5) образуют пару утверждений, отличаю­ щихся номером. Исключается 5), и соответственно изменяются номера указателей.

В этой цепи больше нет совпадающих утверждений, поэтому минимизированная цепь имеет вид:

1)У—

2)0j(Afi)—*-Afj

3)Ф 2 ( М , ) —

6) Ф 3 (Мь МО—WW,

7) Mi —*z

§ 3. 6. ПЕРСПЕКТИВЫ ПРАКТИЧЕСКОГО ИСПОЛЬЗОВАНИЯ

ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ.

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

использование

пока

еще

не получило должного

развития, так как

с точки зрения

практики

существующие методы

эквивалентных

преобразований обладают целым рядом недостатков.

 

Так, система эквивалентных

преобразований

Янова

основана

на использовании

специальной

аксиоматики.

Даже

упрощение

этой аксиоматики,

выполненное

А. П. Ершовым,

не

облегчило

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

102

Система эквивалентных преобразований Криницкого [45]

бо­

лее приближена к практическому использованию, однако и

она

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

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

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

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

Кроме того, совмещение рабочих величин

в пределах одного

оператора совершается с

использованием

алгоритма

экономии

рабочих ячеек на линейных

участках. После

экономии

рабочих

величин на каждом операторе для них отводится один массив па­ мяти, длина которого равна максимальному числу ячеек, требуе­ мых для хранения рабочих величин в пределах одного оператора.

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

Таким образом, основные задачи теории алгоритмов, связанные с эквивалентными преобразованиями алгоритмов и программ и их практическим использованием, можно сформулировать следую­ щим образом:

развить теоретический аппарат, обеспечивающий полное реше­ ние проблемы минимизации алгоритмов и программ;

разработать алгоритм практической реализации системы экви­ валентных преобразований, используя существующий теоретиче­ ский аппарат;

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

Глава IV СИНТЕЗ А Л Г О Р И Т М О В

ИП Р О Г Р А М М

§ 4. 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

Эквивалентные преобразования

алгоритмов

находят

свое практическое применение при

синтезе

алгоритмов.

Поэтому

не случайно в работе Ю. С. Янова

[83] понятие синтеза

алгорит­

мов возникает одновременно с понятием равносильности

преобра­

зований алгоритмов.

«

 

 

 

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

Или другой пример.

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

Однако специфика работы отделов материально-технического снабжения накладывает определенные требования на решаемые в них задачи. Однотипные по назначению задачи в различных от­ делах решаются по-разному. Это различие прежде всего вызвано использованием различных по форме и содержанию исходных и результатных документов. Кроме того, порядок расчетов по раз­ ным группам материала не одинаков.

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

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

104

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