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

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

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

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

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

Добавлен: 21.10.2024

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

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

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

78

Рис. 13г. Модуль I I I

Рис. 13е. Модуль V. Продолжение

82

Рис. 13з. Модуль V I I

86

W: =UT+1.

305

v-.=

v*3

;

W-=

Uf+3:

306

V-=

 

V-l

;

 

 

 

 

307

V-

= 1/-2

;

Uf:

=

 

U/-2;

 

t - -

 

t - 2 :

308

uf.

=

uf-t.

 

t--

=

t - t ,

(my*

(з/оу

 

Pf/J:

--3;

Pf2p=56; P[3]-= 71.

309

PN-

--83: P[S]- =306.

P[6]: =307:

 

P[7J:

=166:.PfS]

=195:

P[9p =230.

 

РПО] = 23?.

 

 

 

R [lp=8,R[2]-=37.

R[3]:

= 63-

310

я

ftp' 86.

R[5]-=92.

R[6]=315.

 

R[7]:

= /63: R/8]=192.

R[9J-= 213.

 

R[IO]

=

215.

 

 

 

0 - 311 0/ЧQl'P

= 18.

Q[2]-=57;

0/3/: =75;

 

 

 

= 88:

0/5/: = 315:,

Q[gf

 

 

 

 

 

0/7/ =

177; 0/8/•=208;

 

0/9/ =215;

 

 

 

 

 

Рис.

13н. Модуль X I I

 

 

 

Блок-схема

алгоритма

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

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

состоит

из двенадцати

модулей. Основные функции,

выполняемые

этими

модулями, следующие:

 

 

 

 

 

 

 

 

модуль

I

—реализация

первой

аксиомы;

 

 

модуль

I I

—реализация второй и третьей

аксиом;

 

модуль

I I I

— реализация четвертой и пятой

аксиом;

 

модуль

IV

—реализация

шестой аксиомы;

 

 

модуль

V

—реализация

седьмой

 

аксиомы;

 

модуль

V I

— реализация девятой аксиомы;

 

 

модуль

V I I

—реализация

десятой — пятнадцатой аксиом;

модуль

V I I I

—реализация

шестнадцатой

аксиомы;

 

модуль

IX

—реализация

семнадцатой

аксиомы;

 

87

модуль

X

—перенумерация

полускобок;

модуль

X I

—реализация восьмой аксиомы;

модуль

X I I

—управление

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

 

 

мых аксиом.

 

 

Работа

алгоритма начинается

с

нулевого блока.

В приведенном

алгоритме не

рассматриваются правила выво­

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

Для упрощения условий их применимости А. П. Ершовым предложена упрощенная аксиоматика [31], которая будет нами рассмотрена далее.

Кроме того, для упрощения правил вывода А. П. Ершов пред­ лагает использовать метод разметок [32]. Сущность его состоит в том, что в аксиоматику вводятся правила преобразования, назы­ ваемого разметкой. Применение этих правил позволяет присоеди­ нить к элементам рассматриваемого объекта некоторую информа­ цию. Повторное применение этих правил распространяет инфор­

мацию по объекту. Когда

дальнейшее

применение

правил ничего

не добавляет к разметке,

 

разметка

называется

стационарной.

При стационарной разметке

каждый

элемент объекта содержит

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

Установление целесообразности использования метода разме­ ток при практической реализации эквивалентных преобразований

требует дополнительных

исследований.

 

 

 

§ 3. 4. РАЗВИТИЕ СИСТЕМЫ ЭКВИВАЛЕНТНЫХ

 

 

ПРЕОБРАЗОВАНИЙ ЯНОВА

 

 

Рассмотрим систему

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

логиче­

ских схем

алгоритмов

Янова в

интерпретации

А. П.

Ершова

[31], так

как представление схем

на языке графов

наиболее соот­

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

Для изложения аксиоматики преобразования необходимо рас­ смотреть правила построения и основные понятия схем Янова в графовом представлении.

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

88

Помеченные

стрелки

назы­

ваются плюс-стрелками, а не­

помеченные — минус-стрелка­

ми. В графе имеется одна и

только одна вершина, не имею­

щая

выходной

стрелки,

назы­

ваемая

конечным оператором.

Каждому

распознавателю

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

логическое ус­

ловие

а — произвольная

функ­

ция алгебры-логики, завися­

щая

от к логических перемен­

ных

ри

рк.

Распознаватель

 

 

 

 

 

 

 

 

 

 

R с сопоставленным ему усло­

 

 

 

 

 

 

 

 

 

 

вием

а

обозначается

 

(Ra).

 

 

 

 

 

 

 

 

 

 

 

Каждому оператору А,

кро­

 

 

 

 

 

 

 

 

 

 

ме

конечного,

приписывается

 

 

 

 

 

 

 

 

 

некоторый набор P s { p i ,

 

рк}

 

 

 

 

 

 

 

 

 

 

логических

переменных,

назы­

Рис.

14. Операторная

 

схема

Янова

 

ваемый сдвигом

по логическим

 

 

 

 

 

 

 

 

 

 

переменным. Оператор А с при­

писанным

ему

сдвигом

обозначается

А(р).

 

 

 

 

 

 

Совокупность

сдвигов

Р\,

Рп

 

всех

операторов

А\,

 

Ап

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

Янова

называется

распределением

сдвигов,

приписанным

схеме

G.

 

 

 

— А

 

 

 

 

 

 

 

Если

для

любого

i(l^.i^.n)

Р{

 

(пустое множество), то

распределение сдвигов называется пустым, при Pi—{p\,

 

 

рп}

распределение

сдвигов

называется

универсальным.

 

 

 

 

Все операторы

одной

операторной

схемы

считаются

попарно

различными. Операторная схема Янова G с операторами

 

 

Аи...,Ап,

логическими переменными

ри

Рк

обозначается

G (Аи

 

Ап,

pi,

рк).

Пример

изображения

операторных

схем

Янова

приве­

ден на рис. 14. При изображении схем приняты следующие обозна­ чения:

о — > —входная стрелка; •—з» —плюс-стрелка;

5* —минус-стрелка;

— распознаватели;

операторы;

конечный оператор;

А ( ) —оператор с пустым сдвигом.

89

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