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

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

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

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

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

Добавлен: 21.10.2024

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

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

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

две схемы эквивалентны, если совпадают их множества реали­ заций.

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

Рассмотрим систему аксиом и правил вывода, описывающую понятие равносильности логических схем алгоритмов при данном распределении сдвигов. Формулами рассматриваемого исчисления

будут

являться строчки вида С —В, где

С и В— выражения. В

случае,

когда С и В — логические схемы

алгоритмов, символ --

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

пределении

сдвигов.

 

 

Аксиомы

и правила вывода данного

исчисления можно

рас­

сматривать

как правила тождественных

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

схем,

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

Ниже приводится система аксиом и правил: Аксиомы

1.

О Ь Л J

 

=

OL

 

J

•

 

 

 

 

г

г

 

 

i

 

г

 

 

 

2.

1 L

С J

 

=

С.

 

 

 

 

 

 

 

i

i

 

 

 

 

 

 

 

 

3.

J

С 1 L = С. ,

 

 

 

 

 

i

 

г

 

 

 

 

 

 

 

 

4.

сф L С J = a L . p L С J J •

 

 

 

г

г

 

 

i

 

3

i' j

 

5. J

Ссф L . = J

J

C a L

pL

•

 

i

 

 

i

 

%

j

 

i

j

 

6.

a V p L = a b p L . J ..

 

 

 

 

 

i

 

 

j

 

i

j

 

 

7.

CB

= 0L

 

J

BOL

 

J CO L

J .

 

 

 

 

i

j

 

ft

 

г

j

h

8.

J

J

= J

J

•

 

 

 

 

 

 

i

j

 

i

i

 

 

 

 

 

 

9.

a L

J

= Л •

 

 

 

 

 

гг

10.

a L . C J

a L . B J . =

a

L

CaL

В J

J .

 

г

i

j

}

 

I

3

5

г

11.

a L

C J 5 J a L

=

 

a L , C j J B a L -

 

i

j

i

j

 

г

j

i

 

j

12.

J C a L

B J a L = J J C a L

В a L •

 

3

г

г

з

з

i

i

 

 

j

13.

i a L C o L B J = o L C o L B J

 

J . .

 

i

3

i

3

 

3

 

i

3

i

14.

J a L C J B a L . =

a

L

С Л

J B a L -

 

i

3

з

г

 

з

j

г

 

i

73

15. J . C J a L B a L = J ,

J C a L

В a L .

j

i

3

i

j

i

j

i

16. J . a L C i

a L = a L C J

J a L •

i

i

j

j

i

i

j

j

17. Пару полускобок L, J , входящую в одно выражение, мож-

i i

но переименовать в любую пару l _ , J , но так, чтобы не произошло

/'

коллизии полускобок. Правила

1

•С ( а ) = С ( р )

С = В ,

F(C)=D

 

2

—

•

F(B)=D

3. Если логическое условие a L подчинено р (при данном рас­

пределении сдвигов), то a L

можно заменить на a р L .

 

В приведенной системе аксиом и правил

приняты

следующие

обозначения:

 

 

 

 

 

Л, В, С —произвольные операторы;

 

 

а, р — любые формулы

исчисления высказываний;

 

0 — тождественно-ложная

формула;

 

 

1 —тождественно-истинная

формула.

 

 

Отметим, что все выводимые формулы и правила вывода, рас­

сматриваемые

как правила

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

схем, обратимы, т. е.

для каждого

выводимого преобразования выводимо

и обратное

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

 

 

 

 

§

3.3. АЛГОРИТМ

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

ЯНОВА

 

 

 

 

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

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

вывода оставляют неформализованными условия

их применения.

В данной работе предлагается один из вариантов

алгоритма экви­

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

74

Алгоритм строится с использованием аксиом Янова при выпол­ нении следующих условий:

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

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

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

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

условия минимизации

преобразуемого алгоритма. Таким

образом,

в результате работы

данного алгоритма обеспечивается

получение

алгоритма,

эквивалентного исходному, но

с меньшим числом эле­

ментарных

выражений.

 

 

 

 

В схеме

алгоритма

блоки

объединены

попарно в

соответствии

с аксиомами. При этом

один

из блоков обеспечивает

распознава­

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

Такими

парами

являются блоки

3—4, 5—6,

29—30. При

запи­

си

аксиом

приняты

следующие

обозначения:

 

 

А — произвольный

оператор;

 

 

 

а,|3 — логические

выражения;

 

 

 

1——левая

полускобка;

 

 

 

 

 

i

 

 

 

 

 

 

 

 

 

 

 

J — п р а в а я

полускобка;

 

 

 

U, В — произвольные

фрагменты;

 

 

 

0 — ложное

значение

предиката;

 

 

 

1 —истинное

 

значение

предиката;

 

 

—Л_— пустой фрагмент, пустой оператор.

 

 

Для

ускорения

работы алгоритма эквивалентных преобразова­

ний, там

где это

возможно,

произведено

объединение аксиом.

Так,

блоки

1 и 2 представляют последовательное применение

пер­

вой и девятой аксиом. Это позволяет одной подстановкой реализо­

вать

действие двух аксиом.

 

 

 

Кроме реализации аксиом, в схеме

предусмотрены

действия,

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

компакт­

ному

виду, т. е. к виду, не содержащему

пустых

операторов Л, и

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

правых

полускобок.

Исключение пустых операторов осуществляют блоки 34 и 35,

которые

производят сдвиг фрагмента преобразуемого алгоритма

на одну

позицию влево. Началом сдвигаемого фрагмента служит

первый символ, непосредственно следующий за символом пустого

оператора,

а

конец

совпадает с концом

алгоритма.

Замена

индекса

у пары полускобок

осуществляется блоками

31 и 32. При

этом

максимальное значение индекса, имеющееся в

75

 

torn,

 

ли Й алгоритме

 

 

 

Qifij

 

 

 

(ррогмен/п

 

i

i

 

 

 

 

 

•[нет

 

 

 

 

 

 

.?

есть

 

ла в алгоритме

 

 

 

 

 

 

фрагмент

 

 

i

i

 

 

 

 

 

 

 

 

 

 

 

 

•[нет

 

 

 

 

 

 

Л

есть

 

-по В алгоритме

 

 

 

juiL

 

 

 

фрагмент <•

 

 

 

7

fen

 

1 нет

 

at

 

 

BLUJJ

ли В алгоритме

 

 

J

 

 

 

фрагмент

 

i

 

i j

 

 

 

\нет

 

 

 

 

 

 

9

Есть ли В алгоритме

 

 

 

jjl/aLBL

 

 

 

фрагмент

 

i j

 

i

 

j

 

 

 

\nern

 

 

 

 

 

 

11

Есть

 

ни в алгоритме

 

j

&LBLJ

 

 

 

фрагмент

 

 

 

с j

 

 

 

\нет

 

 

 

 

 

 

'3

ЕСТЬ

 

ли в алгорит-п. 1РП1

 

...п. .

ж

фрагмент

 

 

 

OLJmH{UOI]i

 

 

 

\нет

 

 

 

 

 

 

15

Есть

 

ли в алгоритме

 

сс L J

 

 

 

фрагмент

 

 

 

с i

 

 

 

 

 

\ нет

 

 

 

 

 

 

17

ЕСТЬ

ли В алгоритме

 

 

 

aLUJaLBJ

 

 

 

фрагмент

 

<

t

j

 

j

 

 

 

\нет

au]jgja

 

i_

19

ЕСТЬ

ли в алгоритме

 

 

 

фрагмент

 

с j

t

 

j

 

 

 

 

 

 

 

 

\нет

 

 

 

 

 

 

21

ЕСТЬ

ливалгоритме

j

 

 

JUaLBJuL

 

 

 

фрагмент

 

i i

 

j

23

 

 

•1-нет

 

jaLUaLBJ

Eегь ли В алгоритме

 

 

j

 

 

 

фрагмент

 

i

с j

 

 

 

^нет

 

 

 

 

 

 

25

Есть ли В алгоритме

 

i

j

jaLUJBaL

 

 

 

фрагмент

 

у

 

 

27

 

 

^нет

 

j

иja.i

 

gai

ЕСТЬ

ли В алгоритме

j

 

 

 

 

фрагмент

 

с

у

 

 

 

 

 

],нет

 

 

 

 

 

 

29

Есть

 

ли в алгоритме

 

 

i

aLUJJaL

 

 

 

фрагмент

 

 

i j

j

 

 

 

нет ф«

 

L

J

—

31

Нет ли В алгоритме

 

?

\

пары

полуснобон

 

j

' j

 

 

 

 

 

* не ~>

 

 

 

 

 

33

Есть

 

ли В алгоритме

 

А

 

 

 

 

 

 

Выражение

 

 

 

 

 

 

35

 

 

нет ф*-

 

 

 

 

 

 

Есть

 

ли В алгоритме

 

j

j

 

 

 

 

 

фрагмент

 

i

j

 

 

 

 

 

пнет

 

 

 

 

 

 

-37

Вывод преобразованного

алго­

 

 

ритма

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

да

да

до

до

до

до

да

до

да

до

да

да

да

да

да

да

да

да

2

Замена

 

 

 

шз А

 

 

 

 

ч

Замена

''

^/ на U

 

 

-*

в

Замена

JU/L

И

а

U

 

 

 

 

 

i

 

 

i

 

 

 

 

 

 

8

Замена aL^UJJно

 

 

 

aPLUJ

 

 

 

с

J

 

IJ

 

i

t

 

 

10

Замена

JJ

UdLfli

 

H O

JUocfiL

>

 

 

l J

 

 

 

 

 

l

L

 

12

Замена

«LPL-J

U

на

aVfil-

 

 

 

J

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

гч\ Замена

OLJBOLJUOU

mUB

 

 

 

IJ

 

 

H t

J к

 

 

16

Замена a L-J на

A

 

 

 

18

Замена

 

 

 

 

 

aLUJaLBJHaaLUtLBJJ

 

го Замена aLUJBJaL

H

0

aLUJJBccL

- *

 

 

I J

I

J

 

'

J t

J

 

22

Замена j U a L

i

B

J a

l

j

 

M0JJUc(LBaL

24

Замена J

a L U

a

L

B-! на <*L UaL BJJ

 

 

l

J

 

t

J

 

J

l

j L

 

26

Замена J«WB*LHa

 

 

ccLUJJBal

 

28

Замена J.UJccLBaL

H

a

JJUaLBaL

 

 

J

i

J

 

t

" / г

j

с

— ^

 

 

 

 

 

 

 

 

 

 

 

30

Замена aLUJJaL

 

н а

 

JaLUJaL

 

 

 

L

LJ J

 

t L J

J

 

32

Замена пары

 

 

на пару

 

. у

 

 

ПОЛуСНОООК

 

ПОЛУСНОООК j ' /

34

 

 

 

 

*

 

 

 

на

 

Сдвиг позиции

алгоритма

 

 

1 позицию

влево

 

 

 

36

Замена

V' J

на

-J -1

 

 

 

Рис. 13а. Общая схема алгоритма

перерабатываемом

алгоритме,

заменяется

меньшим

значением,

отсутствующим

в

алгоритме.

 

 

 

 

 

Перестановка любых двух правых полускобок, между которы­

ми

стоят только

правые полускобки,

производится блоками 35 и

36.

Соответствующая аксиома

может

быть

получена

как следст­

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

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

жет вызвать появление пустого фрагмента, дальнейшая

проверка

применимости

аксиом продолжается,

начиная

 

с восьмой

аксиомы.

В том случае, когда в результате применения

аксиомы

возможно

появление пустого фрагмента, осуществляется

проверка

наличия

такового.

 

 

 

 

 

 

 

При обнаружении пустых фрагментов выполняется соответст­

вующий сдвиг, после чего проверка

аксиом

продолжается,

начи­

ная с восьмой

аксиомы. Если в результате проверки аксиом

обна­

руживается, что ни одна из них не применима

к алгоритму,

про­

веряется

возможность перестановок

правых

 

полускобок.

В

том

случае,

когда

перестановки возможны, они

выполняются

и

про­

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

аксиом,

 

начиная

с первой.

Если же перестановки полускобок не производится, процесс пре­ образований заканчивается.

Рассмотрим теперь алгоритмы реализации конкретных аксиом, блок-схемы которых приведены на рис. 136—13н.

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

п— число элементов логической схемы преобразуемого алго­ ритма;

h — максимальное значение индекса полускобки

в преобразо­

ванном

алгоритме;

 

/ — текущий

номер элемента логической схемы

алгоритма;

к>1 — элементарное выражение;

v, w, а, Ъ, с, d, f, g, т, s,t,z — вспомогательные константы; P,R,Q — переключатели.

77

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