Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 93
Скачиваний: 0
полезное время машины и увеличивает число ошибок. Для одно типных задач, не имеющих существенных различий в алгоритмах
решения, целесообразно использовать |
единый составной алго |
ритм. Такой алгоритм должен отражать |
специфику решения задач |
в различных подразделениях объекта управления и обеспечивать реализацию расчетов для целого ряда задач. Следует иметь в ви ду, что составной алгоритм получается не простым соединением алгоритмов отдельных задач, а является результатом логического объединения этих алгоритмов. Такое объединение выполняется с
использованием |
специального математического аппарата, |
кото |
|
рый будет рассмотрен Далее. |
|
|
|
Синтез алгоритмов и особенно синтез |
программ приобретает |
||
важное значение |
в современных условиях |
использования |
вычис |
лительных систем. В вычислительных системах с развитым мате матическим (программным) обеспечением для решения конкрет ных задач уже не используются готовые программы, в которых от
начала до конца представлен весь процесс обработки |
информа |
||||
ции. |
|
|
|
|
|
Программа решения |
любой задачи |
в такой |
системе |
синтези |
|
руется |
из отдельных |
программных |
модулей, |
представляющих |
|
типовые |
процессы обработки данных. |
Дополнительно программи |
|||
руется лишь та часть задачи, которая не отражена в модулях дан ной вычислительной системы. Синтез программных модулей осу
ществляется |
автоматически специальной программой |
на основа |
|
нии директив, заданных |
программистом. |
|
|
Модульный принцип |
синтеза программ позволяет |
получить |
|
программы |
более высокого качества, устранить дублирование в |
||
написании программ и тем самым снизить трудоемкость програм мирования.
Следовательно, основную задачу синтеза алгоритмов можно определить таким образом: используя формализованный аппарат преобразований алгоритмов, найти эффективный алгоритм синтеза
составных алгоритмов. |
|
|||
Представляет интерес и обратная задача — анализ |
алгоритмов, |
|||
т. е. получение из составного алгоритма эффективного |
алгоритма |
|||
для |
частного |
случая |
реализации. |
|
В |
данной |
работе |
основное внимание сосредоточено |
на форма |
лизованных методах синтеза алгоритмов и программ. Это объяс няется тем, что анализ алгоритмов и программ почти всегда мо жет быть достигнут теми же формальными средствами. Алгоритмы
же синтеза и |
анализа существенно различны. |
§ |
4. 2. МАТРИЧНЫЕ СХЕМЫ АЛГОРИТМОВ СИНТЕЗА |
Логические схемы алгоритма определяют не только порядок выполнения операторов в зависимости от значений логических условий, но и порядок выполнения самих логических условий. При решении вопросов о равносильности логических схем нас
105
интересуют только множества выполненных операторов и не инте ресует порядок их выполнения. В то же время при синтезе алго ритмов основное значение приобретает порядок выполнения опе раторов.
Таким образом, равносильные преобразования и синтез алго ритмов составляют две части одной большой проблемы теории ал горитмов — преобразования алгоритмов.
Исходя из этого целесообразно рассмотреть математический аппарат равносильных преобразований с точки зрения его приме нимости для синтеза алгоритмов. Наибольший интерес представ
ляют матричные схемы, с помощью |
которых |
решаются |
вопросы |
||||||||||||||
равносильности логических |
схем |
алгоритмов. |
|
|
|
|
|
||||||||||
|
Не будем детально останавливаться на вопросах тождествен |
||||||||||||||||
ных преобразований |
матричных схем, |
рассмотрим |
лишь |
общий |
|||||||||||||
принцип их построения и возможность |
|
применения |
для |
синтеза |
|||||||||||||
алгоритмов. |
|
|
|
|
|
|
|
|
|
Аи |
|
Ап |
|
||||
|
Пусть |
имеются некоторое множество |
операторов |
|
и |
||||||||||||
множество элементарных логических переменных ри |
|
рк. |
Вся |
||||||||||||||
кую зависимость порядка выполнения операторов |
Л ь |
|
Ап |
от |
|||||||||||||
значений |
логических |
переменных |
рх, |
|
|
рк |
можно записать в |
ви |
|||||||||
де |
матрицы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
Ах- |
|
• |
• |
Ап |
|
|
|
|
|
|
|
|
|
|
|
А0 |
|
a0i • |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
л , |
|
ахх |
• |
|
' 0>хп |
|
|
|
|
|
|
|
|
|
|
|
|
Ап |
1 |
ап\- |
• |
|
|
|
|
|
|
|
|
где |
aij = a{j |
(Рх, |
|
Рк) — логические |
функции, |
удовлетворяющие |
|||||||||||
условию: если после выполнения оператора Лг- должен |
быть вы |
||||||||||||||||
полнен |
оператор |
Aj |
при наборе А, то |
ац |
(As ) = l |
и aim |
|
(As )«=0 |
|||||||||
для |
тФ\. |
Под А0 |
понимается пустой |
оператор, |
символизирующий |
||||||||||||
начало |
процесса. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Определим основные понятия процесса выполнения и значения |
||||||||||||||||
матрицы |
следующим образом. |
|
|
|
|
|
|
|
|
|
|
||||||
|
Пусть |
задана |
матрица |
А(р{, |
|
рк), |
|
где |
ац — произвольные |
||||||||
логические |
функции |
переменных рх, |
|
рк |
и некоторая последова |
||||||||||||
тельность |
наборов значений |
переменных |
рх, |
рк: |
|
|
|
|
|||||||||
|
|
|
|
|
As |
L A S , , - • -,Asm |
,As m + 1 |
|
,• • • |
|
|
|
|
|
|||
|
Процесс выполнения матрицы определим следующим образом. |
||||||||||||||||
|
Первоначально просматриваем |
значения |
элементов a0j(7 = 1, |
|
|||||||||||||
|
п) 0-й строки при |
наборе Asi и выписываем |
один |
из тех |
опера |
||||||||||||
торов, |
например |
Ац, |
для которого «oii (Asi) = 1- |
|
|
|
|
||||||||||
|
Пусть проделаны т шагов, причем на |
m-м шаге |
был |
выписан |
|||||||||||||
оператор |
Л,- |
; тогда |
на ( т + 1 ) - м |
шаге |
просматриваем |
значения |
|||||||||||
элементов |
/ т - й строки при наборе A s m + |
1 |
и выписываем |
оператор |
|||||||||||||
106
т + 1 , для которого a i m i m + l ( A s m + 1 ) = l . Процесс обрывается, если все элементы рассматриваемой строки имеют значение 0 или если строки с нужным номером в матрице нет.
Выписанную в результате этого процесса |
строчку |
операторов |
|
Ailf Ai2, |
Aim, ... называют значением |
матрицы |
А для за |
данной последовательности наборов значений логических перемен ных.
Последовательность |
наборов |
|
|
|
|
|
||||
|
|
A S l ) A - s 2 , --- ,As m ,As m + 1 |
•••• |
|
|
|||||
назовем допустимой для матрицы А(р\, |
|
рк) |
при распределении |
|||||||
сдвигов |
А—Pi |
(1=1,2, |
|
п), |
если |
для |
этой |
последовательности |
||
найдется |
такое значение |
|
|
|
|
|
|
|||
|
|
АЦ |
, A i 2 , • • •, Aim ,Aim±i |
> • • |
|
|
||||
матрицы |
A(pi, |
рк), |
для |
любого |
т=1,2, |
не |
превосхо |
|||
дящего длины |
этого |
значения, |
набор A s m + 1 |
отличается |
от набора |
|||||
Asm значениями переменных только из |
Р\т. |
|
|
|||||||
Матрицу А(р\, |
рк) |
назовем |
матричной |
схемой, |
если для |
|||||
любой допустимой последовательности эта матрица имеет только одно значение (быть может, пустое).
Две матричные схемы А (ри |
рк) |
и В (ри |
рк) |
мы назовем |
|||
равносильными |
при данном распределении |
сдвигов |
и обозначим |
||||
А = В, если для |
любой |
последовательности наборов, |
допустимой |
||||
при этом распределении |
сдвигов |
для |
Л |
и В, их значения совпа |
|||
дают. |
|
|
схема А(ри |
рк) |
|
||
Будем говорить, что матричная |
и логическая |
||||||
схема алгоритма С (pi |
р, Ль |
Л„) |
равносильны |
при данном |
|||
распределении |
сдвигов, |
если для |
любой |
последовательности набо |
|||
ров значений переменных рх, •-, Рк, допустимой при этом распре делении сдвигов для Л или С, их значения совпадают.
Таким образом, если алгоритм представлен в виде операторной схемы Янова и задано распределение сдвигов, то можно построить эквивалентную схеме Янова матричную схему.
Янов рассматривает только формализованный способ представ
ления |
алгоритмов |
в виде матричных схем с целью |
последующего |
их использования |
при синтезе алгоритмов, однако |
самого алго |
|
ритма |
синтеза он |
не дает. Идею Янова реализует |
Карп [30]. Он |
строит алгоритм синтеза двух алгоритмов, представленных в виде блок-схемы.
Блок-схема является наиболее употребляемым средством изо бражения алгоритмов. Она представляет собой конфигурацию операционных и решающих элементов, связанных направленными дугами. Каждый операционный элемент соответствует группе операций, выполняемых последовательно в процессе реализации алгоритма. Каждый решающий элемент соответствует выбору одного из двух или более дальнейших действий.
107
Вариант выполнения алгоритма может быть определен указа нием пути через блок-схему начинающегося в данном начальном элементе и заканчивающегося в операционном элементе, у кото рого нет последующего элемента.
Соответственно любой данной блок-схеме можно построить ориентированный граф, узлы которого соответствуют каждому решающему элементу, начальному или конечному операционному элементу или любой точке на блок-схеме, в которой встречаются две и более стрелки. Граф, соответствующий блок-схеме, пока занной на рис. 17, приведен на рис. 18.
Рис. 17. Блок-схема алгоритма
|
Рис. 18. Граф представления алгоритма |
|
В |
блок-схеме приняты следующие условные обозначения: |
хи |
х2, х3, |
х4, х5, х6 — операционные элементы, соответствующие |
по |
следовательности команд, не прерываемой условной передачей уп
равления; а, |
р, у, б — решающие |
элементы, соответствующие |
ус |
|||
ловной |
передаче |
управления. |
|
|
||
В этом примере каждое решение имеет два исхода, обозначае |
||||||
мые на |
блок-схеме значками + и |
—. Соответственно этому |
граф |
|||
содержит для |
каждого |
решающего |
элемента р две дуги, обозна |
|||
чаемые |
через |
р |
и р. |
1 |
|
|
108
Матрица |
соединений |
(ciij), |
полученная |
из |
графа, |
показанного |
||||||
на рис. 18, |
имеет вид: |
|
|
|
|
|
|
|
|
|||
|
' |
0 |
*1 |
0 |
0 |
0 |
|
0 |
0 |
|
||
|
|
Pi |
0 |
Pl*2 |
0 |
0 |
|
|
0 |
0 |
|
|
|
р |
0 |
0 |
~Р2 |
0 |
|
0 |
0 |
|
|
||
|
0 |
0 |
0 |
Рзх3 |
Ръ |
|
0 |
0 |
|
|
||
|
0 |
|
0 |
0 |
0 |
0 |
Р4Х5 + Р4Х4 |
// |
|
|||
|
0 |
|
0 |
0 |
0 |
0 |
|
0 |
|
х& |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
|
о |
/ |
|
|
Элемент |
равен |
нулю, если узлы |
i |
и / |
не связаны |
дугой. |
||||||
Если |
узлы |
i |
и / связаны |
одной |
дугой |
а ь |
то |
а.ц = а\. |
Если |
узлы |
||
i и / |
связаны дугами |
аи |
а2, |
ап, |
то |
ац — а1 + а2+ ... +ап. |
Сло |
|||||
жение понимается в теоретико-множественном смысле. Диагональ
ный элемент аи равен нулю, |
если |
в данном узле отсутствуют |
петли. |
|
объединены алгоритмы А\ и |
Предположим, что должны |
быть |
А2, блок-схемы которых изображены на рис. 19, а и б.
|
|
о |
|
|
|
|
+ 5 |
*3 |
^ |
|
|
Рис. 19. Объединяемые алгоритмы |
|
|
Эти |
алгоритмы |
имеют общие операционные элементы хи х2, х3 |
||
и х$. В |
составном |
алгоритме каждый элемент |
должен встречаться |
|
только один раз. Для указания того, какой из двух вариантов при менения составного алгоритма должен быть выполнен, будет ис
пользована двоичная переменная р. Случай |
р = \ соответствует |
||||
алгоритму А\, а случай р= |
1 — алгоритму |
А2. |
|
|
|
Процедура синтеза состоит в следующем, |
|
|
|||
1.. Строим матрицы |
Мх |
и М2, каждая |
из |
которых |
содержит |
строку и столбец для |
каждого операционного |
элемента |
из А\ или |
||
109