Основы алгебры алгоритмов, базирующейся на данных
Предложена модель ЭВМ, у которой информационное множество представляет собой множество данных, образующих иерархию структур данных произвольной сложности. На основе этой модели построена система алгоритмических алгебр и рассмотрены некоторые аспекты и перспективы еѐ использования. The model of the...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут програмних систем НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/14640 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Основы алгебры алгоритмов, базирующейся на данных / В.Г. Акуловский // Пробл. програмув. — 2010. — № 2-3. — С. 89-96. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859745957284937728 |
|---|---|
| author | Акуловский, В.Г. |
| author_facet | Акуловский, В.Г. |
| citation_txt | Основы алгебры алгоритмов, базирующейся на данных / В.Г. Акуловский // Пробл. програмув. — 2010. — № 2-3. — С. 89-96. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| description | Предложена модель ЭВМ, у которой информационное множество представляет собой множество данных, образующих иерархию
структур данных произвольной сложности. На основе этой модели построена система алгоритмических алгебр и рассмотрены
некоторые аспекты и перспективы еѐ использования.
The model of the computer at which the information set represents set of the data forming hierarchy of structures of the data of any
complexity is offered. On the base of this model the system of algorithmic algebras basing the data is constructed, some which prospects of
use are considered in the report.
|
| first_indexed | 2025-12-01T21:58:52Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
89
УДК 519.681
ОСНОВЫ АЛГЕБРЫ АЛГОРИТМОВ,
БАЗИРУЮЩЕЙСЯ НА ДАННЫХ
В.Г. Акуловский
Академия таможенной службы Украины.
49000, Днепропетровск, ул. Дзержинского 2\4.
Тел/Факс: (056) 745 5596, (0562) 471 791
e-mail: academy@amsu.dp.ua
Предложена модель ЭВМ, у которой информационное множество представляет собой множество данных, образующих иерархию
структур данных произвольной сложности. На основе этой модели построена система алгоритмических алгебр и рассмотрены
некоторые аспекты и перспективы еѐ использования.
The model of the computer at which the information set represents set of the data forming hierarchy of structures of the data of any
complexity is offered. On the base of this model the system of algorithmic algebras basing the data is constructed, some which prospects of
use are considered in the report.
Введение
Известно, что абстрактная модель ЭВМ Глушкова [1, 2] представляет собой схему взаимодействия двух
автоматов управляющего У и операционного О, а множество состояний операционного автомата M – его
информационное множество. Выходные сигналы А управляющего автомата отождествляются с операторами,
которые изменяют состояние операционного автомата, а выходные сигналы операционного автомата,
представляют собой значения различных элементарных логических условий , определенных на множестве
состояний операционного автомата.
Для формализации представления алгоритмов функционирования абстрактной модели ЭВМ
В.М. Глушков предложил математический аппарат – систему алгоритмических алгебр (САА) [2, 3]. Этот
формальный аппарат нашел широкое применение и получил дальнейшее развитие в многочисленных работах
его учеников и последователей (например, [4, 5]).
Вместе с тем, в работе [3] высказана мысль (которая не нашла своего развития) о том, что при различных
дополнительных предположениях об автоматах У и О функционирование модели может интерпретироваться
по-разному.
Развивая эту мысль, будем утверждать, что модификация модели ЭВМ позволяет построить
алгебраический аппарат, возможности которого определяются выбранной моделью. И таким образом может
быть построен формальный аппарат, отвечающий некоторым сформулированным требованиям и
ориентированный на решение некоторых задач, в том числе методологических.
В качестве примеров задач такого рода упомянем следующие задачи.
В программировании известны два подхода к разработке: от данных и от управления, которые
существуют независимо и, более того, конкурируют между собой. Очевидно существуют классы программных
систем, при разработке которых один из упомянутых подходов наиболее эффективен. Однако легко
представить такие системы, для которых выбор одного из подходов будет неоднозначен, и уместным было бы
комплексное использование этих подходов.
Весьма важной и перспективной представляется задача формализации информационных связей в
алгоритмах и программах, так как в случае ее решения открываются пути к контролю корректности и
преобразованию алгоритмов и программ на основе анализа таких связей. В частности, вероятно это позволит
разрешить некоторые аспекты проблемы распараллеливания алгоритмов и программ.
Кроме того, в ряде работ Н.П. Брусенцова [6–8], наряду с критикой современных ЭВМ, показаны
преимущества трехзначной логики (по сравнению с двузначной) при решении многих задач. Более того, в этих
(и других) работах утверждается и показывается, что трехзначная логика не только вполне корректна, но
является даже более удобной и привычной для людей формой мышления.
Для построения алгебры алгоритмов, в рамках которой могут быть решены эти и другие подобные
задачи, рассмотрим модель ЭВМ, модифицированную, в соответствии с идеей, предложенной в [3]. А именно,
будем интерпретировать множество состояний операционного автомата как множество состояний
обрабатываемых алгоритмом данных.
Модель ЭВМ
Будем полагать, что автомат О содержит множество данных D, которое будем трактовать как его
информационное множество. Носителем этих данных является множество абстрактных атомарных (неделимых)
элементов памяти (в дальнейшем элементов памяти) },...,,{ 21 n . Каждому элементу i сопоставим
Теоретичні та методологічні основи програмування
90
конечное множество всех возможных значений
k
s
s ii
iI
1
и будем говорить, что множество
i
I отображается
на одноэлементное множество i . Или другими словами, что каждый элемент i может принимать любое
значение
ii
Iij . Одновременно любой элемент i может принимать одно и только одно значение из
множества
i
I .
Элементы, образующие множество , могут быть, как одинаковыми (однотипными), так и различными
(разнотипными), т. е. },...,,{ 21 n , где для p
p
i и s
s
j в первом случае выполняется
соотношение s
j
p
i
II
, а во втором – s
j
p
i
II
.
Теперь введем понятие данных, причем будем различать элементарные и простые данные.
Для того чтобы определить элементарные данные, введем множество идентификаторов DDЭ
и некоторому атомарному элементу памяти эi (где Э ) поставим в соответствие элемент Эj Dd
(в общем случае не единственный), который назовем идентификатором переменной или просто переменной.
Переменной jd поставим в соответствие множество допустимых значений
p
l
dld jj
iI
1
, такое, что
ij
II d и
будем говорить, что множество
jdI отображается на одноэлементное множество jd или, что переменная jd
принимает одно из допустимых значений
jj ddl Ii , что будем записывать в виде jdl di
j
. В том случае, когда
jj
II d , будем говорить, что для переменной jd допустимы любые значения или, что для переменной jd
множество допустимых значений не ограничено.
Для того чтобы определить простые данные, введем множество идентификаторов DDP и будем
рассматривать некоторые совокупности однотипных элементов памяти lnnn ,...,, 21 , где каждый из
элементов памяти in может принимать значения из множества всех возможных значений
k
s
s inin
iI
1
,
а совокупность элементов lnnn ,...,, 21 принимают значения из множества
ln
np
p
П
i in
II
1
. Каждой
совокупности элементов lnnn ,...,, 21 поставим в соответствие элемент П
П
j Dd (в общем случае не
единственный), который назовем идентификатором простой переменной или простой переменной. А каждому
П
jd в соответствие поставим множество допустимых значений
ln
np
m
s
spd
iI П
j
1 1
, такое, что П
id
II П
j
.
В том случае, когда П
id
II П
j
, будем говорить, что для переменной jd допустимы любые значения или, что для
переменной jd множество допустимых значений не ограничено.
Дальнейшие рассуждения будем осуществлять в предположении, что элементарные и простые данные
могут быть сгруппированы с целью построения более сложных – составных данных.
Множество семантически связанных элементарных и простых данных, образующих составные данные
первого уровня группировки запишем в виде },...,,...,,{ 21
1
nij ddddD и },...,,...,,{ 21
1 П
k
П
j
ПП
i ddddD , где 1
jD
и 1
iD – идентификаторы составных данных первого уровня группировки, а id и П
jd - идентификаторы
элементарных и простых данных, обладающие вышеописанными свойствами.
Этот процесс может быть продолжен неограниченно, что позволяет строить составные данные с
произвольным уровнем (степенью) группировки, т. е. },...,,{ 11
2
1
1
k
s
kkk
p DDDD .
С учетом вышеизложенного введем понятие структур данных.
Структуры данных на некотором уровне группировки в общем случае включают в себя семантически
связанные элементарные, простые и составные данные произвольного уровня группировки, а так же структуры
данных, полученные на предыдущих уровнях группировки.
Таким образом, множество состояний операционного автомата D – это в общем случае иерархия
структур данных произвольной степени вложенности и сложности.
Определив данные и некоторые их свойства, вернемся к модели ЭВМ.
Выходные сигналы автомата У – Д-операторы, образующие множество U, поступающие на вход
автомата O и определенные (в общем случае частично определенные) на множестве данных D .
Теоретичні та методологічні основи програмування
91
Будем говорить, что Д-оператор изменяет состояние операционного автомата, изменяя (преобразуя)
хранимые им данные из множества D. Если множество DD j является областью определения, а множество
DD j – областью значения, то некоторый Д-оператор может быть записан в виде jj DDA )( , где UA ,
DDD jj , .
В дальнейшем Д-оператор будем записывать в виде (более удобном) )()( DAD , множество данных D ,
будем называть входными, а множество D – выходными данными Д-оператора.
Д-оператор определим следующим образом.
Определение 1. Д-оператор )()( AA DAD преобразует множество входных данных DDA , которое имело
значения из множества значений II DlD , в множество выходных данных DDA , которое принимает
множество значений II DpD .
Теперь введем понятие неопределенного оператора.
Определение 2. Д-оператор )()( AA DAD будем называть неопределенным, если при lD I
A
вычислительный процесс переходит в неопределенное состояние. Такой оператор будем обозначать N .
Заметим, что под неопределенным состоянием вычислительного процесса будем понимать утрату
управления, нарушение последовательности вычислений и остановку (зацикливания) этого процесса.
Множество переменных AD (со своими значениями), специфицированных на выходе оператора
( ) ( )A AD A D , до его выполнения обозначим AD и определим понятие тождественного оператора.
Определение 3. Оператор )()( AA DAD будем называть тождественным, если для множества данных AD ,
выполняется соотношение AA DD , т. е., если оператор не изменяет данные и, таким образом, не влияет на
состояние операционного автомата. Такой оператор будем обозначать Е.
Из этого определения следует, что Д-операторы вида )()( A и )()( ADA – тождественные.
Далее будем полагать, что на множестве D определены предикаты, образующие два множествами:
множеством двузначных – P2 и множеством трехзначных – P3 предикатов, таких, что }1,0{)( 222 EDp ,
где 2 2( )p D P , },1,0{)( 333 EDp , где 3 3( )p D P , а 3 когда 3 {0,1} . Операционный автомат, вычисляя эти
предикаты, формирует на своем выходе элементарные логические условия, которые поступают на вход
управляющего автомата. Заметим, что вычисление предикатов не ведет к изменению информационного
множества D автомата O.
Завершая рассмотрение модели ЭВМ, сформулируем некоторые полученные результаты.
В рамках предлагаемой модели в качестве информационного множества автомата O выступают данные
(множество D), которые образуют структуры любой степени сложности. Введенные Д-операторы и предикаты
определенны на множестве D. Причем предикаты продуцируют как двузначные, так и трехзначные логические
условия. Логические условия и Д-операторы являются входными и выходными сигналами, которыми
обмениваются автоматы, образующие рассматриваемую модель ЭВМ. При этом Д-операторы изменяют данные
и таким образом, изменяют состояние информационного множества автомата О, а логические условия
характеризуют состояние этих данных, т. е. состояние упомянутого информационного множества.
Основы алгебры алгоритмов
Пусть <U, W, > – система алгоритмических алгебр, базирующаяся на данных (САА\Д), где U –
множество операторов; W – множество логических условий, – сигнатура операций, состоящая из логических
операций – 1, принимающих значения на множестве W и операций – 2, принимающих значения на
множестве операторов U.
На множестве W определены известные (см., например, [3]) операции дизъюнкция, конъюнкция и
отрицание.
На множестве U введем следующие операции, причем таким образом, чтобы они были всюду
определены.
Операцию р-дизъюнкции будем рассматривать в следующих вариантах, зависящих от вида
используемого предиката.
3
3 3
3
( ) если 1
[ ( )](( ) ( ) ) ( ) ( ) ( ) если 0
( ) если
A A
A A B B C C B B
C C
D A(D ), ;
p D D A(D ) D B(D D C D D B(D ), ;
D C(D ), μ;
,
где ( ) ( ) ( ) ( ) ( ) ( )A A B B C CD A D , D B D , D C D U , DDDDDDDD CCBBAA ,,,,,,
~
, 33 )
~
( PDp , 33 )
~
( Dp , W3 .
Результатом выполнения этой конструкции является выполнение одного из трех возможных операторов,
который выбирается в соответствии со значением логического условия 3 , принимающего истинные значения
трехзначной логики 3E . В качестве предиката в операторе могут выступать совокупности предикатов, тогда
продуцируемые ими логические условия связываются логическими операциями множества 1.
Теоретичні та методологічні основи програмування
92
2
2
( ) ( ) если 1;
[ ( ) (( ) ( ) ( ) ))
( ) ( ) в противном случае,
A A
A A B B
B B
D A D ,
p D ] D A D D B(D
D B D ,
где 22 )
~
( PDp , W2 .
Результатом выполнения этой конструкции является выполнение одного из двух возможных операторов,
который выбирается в соответствии со значением логического условия 2 , принимающего истинные
значения двузначной логики 2E . При этом первый из операторов выполняется при истинном значении
логического условия, а второй – во всех остальных случаях. В качестве предиката в операторе могут выступать
совокупности предикатов, тогда продуцируемые ими логические условия связываются логическими
операциями множества 1.
Частным случаем р-дизъюнкции является операция р-фильтрация (последовательная фильтрация),
которая вводится следующим образом:
2 2 2[ ( )](( ) ( 0 ) [ ( )](( ) ( )) ( ) ( ) если 1A A A A A Ap D D A D E p D D A D D A D , ,
где 22 )
~
( PDp , W2 .
Результатом выполнения этой конструкции является выполнение одного оператора при условии
истинности логического условия 2 .
Следующая операция, которую мы рассмотрим – р-итерация и введем следующим образом.
2 ( )
{( ) ( )}A Ap D
D A D – операция р-итерации состоит в вычислении предиката )
~
(2 DP и проверке
полученного логического условия 2 . Если 2 истинно, выполняется оператор ( ) ( )A AD A D , и вновь
вычисляется предикат и проверяется условие 2 . Циклический процесс, состоящий в проверке условия 2 и
выполнении оператора, осуществляется до тех пор, пока условие 12 в противном случае операция
р-итерации завершается.
Операция композиции (обозначается “*”), определим следующим образом.
Композиция операторов ( ) ( )*( ) ( )A A B BD A D D B D означает последовательное выполнение сначала
оператора ( ) ( )A AD A D и затем оператора ( ) ( )B BD B D .
Эта операция обладает следующими свойствами:
*( ) ( ) ( ) ( )* ( ) ( )A A A A A AE D A D D A D E D A D ;
*( ) ( ) ( ) ( )*A A A AN D A D D A D N N ,
где N – неопределенный, а E – тождественный операторы.
Теперь определим регулярную схему Д-операторов.
Определение 4. Представление любого Д-оператора из U через образующие элементы системы
<U, W, > называется регулярной схемой этого Д-оператора (РСД).
В рамках РСД операция композиции обладает следующими свойствами:
* * ;E ОП ОП E ОП
* * ;N ОП ОП N N
где ОП – произвольная операция из 2 , N – неопределенный, а E – тождественный операторы.
Исходя из определения 4 и приведенных свойств, будем утверждать следующее.
Утверждение. Любая операция множества 2 может рассматриваться как некоторый Д-оператор.
Доказательство. Некоторый оператор можно представить в виде
( ) ( ) ( ) ( )* ,A A B BD A D D B D ОП ,
где ОП произвольная операция. В случае если оператор ( ) ( )B BD B D тождественный, то, в соответствии со
свойством операции композиция, это выражение будет выглядеть, как ( ) ( ) * .A AD A D E ОП ОП
Следствие. Любую операцию множества 2 можно записывать (оформлять) в виде Д-оператора.
На основании доказанного утверждения введем понятие композиционной схемы Д-операторов.
Определение 5. Регулярная схема Д-оператора, в которой используется единственная операция –
композиция, а остальные операции множества 2 записаны в виде Д-операторов, называется композиционной
схемой (КС) этого Д-оператора.
Таким образом, мы заложили основы алгебраического аппарата, который позволяет представлять
алгоритмы, специфицируя при этом обрабатываемые данные. В частности, определили Д-операторы, основные
операции алгебры, регулярные схемы Д-операторов и их композиционные схемы.
Далее рассмотрим вопросы, связанные с формализацией информационных связей в алгоритмах.
Теоретичні та методологічні основи програмування
93
Информационные связи в композиционных схемах и их преобразование
В рамках композиционных схем будем решать вопросы о взаимосвязи между операторами,
образующими эти схемы. Заметим, что формализации информационных связей, контролю корректности и
преобразованию алгоритмов посвящены работы [9–11], и в данном случае мы воспользуемся результатами
полученными в этих работах.
Пусть КС представляет собой следующее выражение:
1 1 1 2 2 2( ) ( ) ( ) ( )*( ) ( )*...*( ) ( )*...*( ) ( ).i i i n n nD A D D A D D A D D A D D A D
Определим понятие информационных связей в КС.
Определение 6. Операторы )()( iii DAD и )()( jjj DAD (где i<j), входящие в КС, связаны, если для них
выполняется соотношение: ji DD , т. е. некоторое подмножество выходных данных оператора
)()( iii DAD поступает на вход оператора )()( jjj DAD . Будем говорить, что множество данных jiji DDD
( iji DD
и iji DD
) связывает операторы iA и jA (на что указывают используемые индексы) и эти
данные будем называть связывающими.
Из определения 6 следует, что данные могут передаваться от любого оператора к одному или
нескольким следующим за ним операторам, т. е. передаются слева направо и, что именно связывающие
данные образуют информационные связи в КС. При этом в общем случае, некоторый оператор может быть
связан со всеми следующими за ним и всеми предшествующими ему операторами.
Используя определение 6, специфицируем в КС информационные связи. Для этого детализуем
входные и выходные данные операторов и дополним систему обозначений следующим образом. Данные на
входе j-го оператора, связывающие его с k-м, будем обозначать jk D
(где k – “адрес источника”, j – “адрес
приемника” данных), а на выходе, связывающие его с p-м – pj D
(где j – “адрес источника”, p – “адрес
приемника” данных).
Перепишем КС с учѐтом введенных обозначений:
1 1 1 1 2 1 3 1 1 2 1 2 2 2 2 3 2 2
1 1 1 1 1
( ) ( ) ( ) ( , , ,..., ,..., )*( , , ) ( , ,..., ,..., )*...
...*( , ,.., , ,..., ) ( , ,..., ,..., )*...*( , ,.., ,..., ) ( ).
j n j n
j j l j j j j j j j j p j n n n j n n n n n
D D D A D D D D D D D A D D D D
D D D D A D D D D D D D D A D
В построенной КС не только специфицированы данные и связи между операторами, но и все
“источники” и “приемники” данных поставлены в однозначное соответствие, т. е. любому 1
pl D
соответствует
1
pl D
. Поскольку в КС, как правило, не все операторы связаны друг с другом любое из множеств 1
pl D
может
быть пустым и, соответственно, пустым будет и множество 1
pl D
.
На основе специфицированных связей будем решать задачу оптимизирующего преобразования
алгоритмов.
Рассмотрим информационные связи между операторами в КС и определим некоторые связанные с этим
понятия.
Определение 7. Множество jjjljj
л
j DDDDS
121 ,...,,,..,, назовем множеством левых связей j-го
оператора, а множество njpjjjjj
пр
j DDDDS
,...,,...,, 21 – множеством его правых связей. В связи с этим, будем
различать три типа операторов, которые назовем:
- связанные, у которых л
jS и пр
jS ;
- связанные слева (справа), у которых л
jS , а пр
jS ( пр
jS , а л
jS );
- несвязанные, у которых л
jS и пр
jS .
Множество njjjnjnj
о
j DDDDDDS
111212111 ,...,,....,,...,,,..., назовем множеством связей, охватывающих
(огибающих) j-й оператор. Количество огибающих связей оператора jA , определим как: о
j
о
j SK . Любое из
множеств lj D
( sr D
), входящих в множества
л
jS ,
пр
jS ,
о
jS , может быть пустым и в этом случае оно из
рассмотрения исключается. Из чего следует, что множества
л
jS ,
пр
jS ,
о
jS так же могут быть пустыми.
Теперь введем и определим понятие длины информационных связей.
Теоретичні та методологічні основи програмування
94
Определение 8. Длину произвольной связи между операторами iA и jA определим для случая i<j, как
ijd ji , а для случая j<i, как jid ji .
Исходя из определений 7 и 8, общую (суммарную) длину левых (правых) связей оператора kA
запишем в виде
1
1
k
p
kp
л
k dL (
n
kp
pk
пр
k dL
1
), а общую длину огибающих k-й оператор связей в виде
1
1 1
k
l
n
kr
rl
o
k dL . Во всех приведенных случаях любой из элементов ji d , входящих в приведенные выражения
(в соответствии с определением 7), может быть равен нулю.
Учитывая тот факт, что, наряду с вышерассмотренными, существуют и другие виды связей, которые в [9]
названы обратными, приведем определения локально независимых операторов.
Определение 9. Локально независимыми назовем любые два несвязанных оператора
ˆ ˆ( ) ( ) ( ) ( )D A D * D B D , если для них выполняются следующие ограничения: DD ˆ , DD ˆ ,
DD ˆ , т. е. эти операторы не имеют никаких информационных связей между собой. В результате этого,
для них выполняется тождественное соотношение: ˆ ˆ ˆ ˆ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )D A D * D B D D B D * D A D , т. е. операторы
могут перемещаться в рамках КС.
Далее, обобщая определение 9, введем понятие области независимости.
Определение 10. Областью независимости слева от оператора )()( iii DAD , входящего в КС, назовем
непрерывную последовательность операторов )()(*...*)()( 111 iiimmm DADDAD , где каждый из операторов,
входящих в эту последовательность, не связан с данным и предшествует ему, и для каждого из которых
выполняются соотношения из определения 9. В рассматриваемом (более общем) случае эти соотношения
представляют собой следующее:
i
i
mp
p DD )(
1
,
i
i
mp
p DD )(
1
,
1
( ) ,
i
p i
p m
D D
(где 1m m ). Область независимости справа от оператора )()( iii DAD определяется аналогично и формально
записывается в виде следующих соотношений:
)(
1
r
ip
pi DD ,
)(
1
r
ip
pi DD ,
)(
1
r
ip
pi DD ,
(где 1r i ). Будем говорить, что оператор )()( iii DAD обладает областью независимости, если для него
выполняются приведенные соотношения.
Исходя из определений 9 и 10, будем утверждать, что каждый оператор в своей области независимости
не имеет никаких информационных связей и может быть перемещен в рамках этой области.
На основании вышеизложенного докажем, что перемещение операторов в рамках их зоны
независимости может обеспечить сокращение длины информационных связей в КС.
Теорема. В любой КС, содержащей операторы, обладающие областями независимости, длина
информационных связей сократится в результате перемещения этих операторов в рамках их областей
независимости при выполнении следующих условий. Если некоторый оператор iA в результате перемещения
и перенумерации операторов становится j-м ( jA ), то в зависимости от его типа (см. определение 7), длина
информационных связей в КС сократится при условии выполнения следующих соотношений:
1) для несвязанных операторов, при перемещении в произвольном направлении, o
i
о
j LL ˆ , при этом
перемещение 1-го и n-го (последнего) операторов к сокращению связей не приведут;
2) для связанных слева (справа) операторов, в случае перемещения их влево (вправо), л
j
o
i
о
j LL ˆ
(
пр
j
o
i
о
j LL ˆ ), а для 1-го и n-го соответственно
про
jL 1 и
л
n
о
jL ;
3) для связанных операторов в случае перемещения влево (вправо)
л
j
o
i
пр
j
о
j LL ˆ
(
пр
j
o
i
л
j
о
j LL ˆ ).
Во всех приведенных случаях:
о
jL – длина связей, огибающих оператор jA (в новом месте
расположения), а о
iL̂ – длина этих связей в исходном месте расположения, после удаления оператора iA ,
)( л
j
пр
j – величина, на которую сократится общая длина правых (левых) связей, )( л
j
пр
j – прирост общей
длины правых (левых) связей в результате перемещения оператора в его новое место расположения.
Теоретичні та методологічні основи програмування
95
Доказательство. При перемещении операторов в их области независимости на изменение длины
связей в КС влияют три (и только три) фактора: сокращение общей длины огибающих связей в месте
удаления оператора и еѐ увеличение в месте вставки оператора, сокращение левых (правых) связей при
перемещении оператора влево (вправо), удлинение левых (правых) связей при перемещении оператора
вправо (влево). Никаким другим изменениям информационные связи не подвергаются.
Рассмотрим влияние этих факторов, причем рассмотрение первого из них разобъем на два этапа.
Первый этап. Во всех случаях, когда некоторый оператор iA извлекается из последовательности
операторов, образующих его область независимости, а операторы, входящие в КС, перенумеровываются,
длина каждой отдельной, огибающей этот оператор, связи сократится на единицу. Это следует из
определения 8 и того факта, что все индексы в диапазоне от i+1 до n уменьшатся на единицу. Суммарную
длину огибающих связей, полученную после извлечения i-го оператора, запишем в виде o
i
o
i
о
i KLL ˆ
(где o
iL – исходная длина этих связей, а o
iK – их количество).
Второй этап. Во всех случаях, когда извлеченный ранее оператор iA вставляется в последовательность
операторов, образующих его область независимости, и после перенумерации получает номер j ( jA ), каждая
отдельная исходная связь, которая после вставки оператора jA будет его охватывать, увеличится на
единицу. Это следует из определения 8 и того факта, что все индексы в диапазоне от j+1 до n–1 увеличатся
на единицу. Суммарную длину огибающих связей, полученную после вставки j-го оператора, запишем в виде
o
j
o
j
о
j KLL
~
(где o
jL
~
– исходная длина связей, а o
jK – их количество).
Исходя из изложенного, сделаем вывод, что влияние первого фактора на общую длину связей в РС
(увеличение или сокращение) зависит от количества огибающих связей в исходном и результирующих местах
расположения оператора, т. е. от выбора места, в которое будет перемещен оператор iA .
Второй фактор. В результате перемещения оператора влево (вправо) длина его левых (правых)
связей со всеми предшествующими (последующими) операторами сократится на величину перемещения, что
докажем, основываясь на определении 10, следующим образом.
При перемещении оператора iA влево на j-е место (вправо на p-е место), где j<i (p>i) длина некоторой
левой (правой) связи между операторами jA ( pA ) и kA ( lA ), где k<j (l>p), будет определяться
соотношением jiikjk ddd ( pililp ddd ). Общая длина левых (правых) связей оператора jA ( pA ) в этом
случае будет определяться соотношением
1j
im
jm
л
i
л
j dLL (
1p
im
pm
пр
i
пр
p dLL ) и она, очевидно, меньше
левых (правых) связей исходного оператора. Исходя из этого, величину, на которую сократится суммарная
длина левых (правых) связей, запишем в виде л
j
л
i
л LL (
пр
p
пр
i
пр LL ).
Третий фактор. При перемещении оператора iA влево на j-е место (вправо на p-е место), где j<i (p>i)
длина связи между операторами jA ( pA ) и rA ( sA ), где r>i (s<i) будет определяться соотношением
ijrirj ddd ( ipsisp ddd ). То есть, в обоих случаях связи удлиняются на величину перемещения. Общая
длина левых (правых) связей оператора jA ( pA ) в этом случае будет определяться соотношением
1j
im
jm
л
i
л
j dLL (
1p
im
pm
пр
i
пр
p dLL ) и она, очевидно, больше длины левых (правых) связей исходного
оператора. Исходя из этого, прирост общей длины левых (правых) связей запишем в виде
л
i
л
j
л LL
(
пр
i
пр
p
пр LL ).
Первый и последний операторы РС в соответствии с определениями 9,10 обладают следующими
свойствами. У первого 1A (последнего nA ) оператора РС множества лS1 и oS1 ( пр
nS и o
nS ) пусты и,
соответственно, 01
лL , 01
oL ( 0пр
nL , 0o
nL ).
Таким образом, первый фактор влияет на длину связей во всех случаях, но в случае независимых
операторов он является единственным, что и отражено в соотношении 1. Причем перемещение первого и
последнего операторов, в связи с приведенными свойствами 01
oL и 0o
nL (то есть ни одна связь их не
охватывает), к сокращению длины связей не приведет.
Теоретичні та методологічні основи програмування
96
Наряду с первым фактором, для связанных слева (справа) операторов в соотношении 2, учтено влияние
второго фактора, а для связанных – влияние второго и третьего в соотношении 3. При этом первый и
последний операторы не могут быть связанными в соответствии со свойствами 01
лL и 0пр
nL и, в качестве
таковых, не рассматриваются. В случае связанных слева (справа) операторов из свойства 01
oL и ( 0o
nL )
с очевидностью следует свойство 0ˆ
1
oL ( 0ˆ o
nL ), что и ведет к трансформации соотношения 2 к соответ-
ствующим частным случаям.
Поскольку в приведенных соотношениях влияние всех соответствующих факторов учтено для каждого
типа операторов, то, очевидно, выбор нового места расположения операторов (если оно существует) с учетом
этих соотношений с неизбежностью приведет к сокращению суммарной длины информационных связей в КС.
Теорема, таким образом, доказана.
Заметим, что хотя возможность перемещение операторов ограничена областями независимости и, таким
образом, исключено их взаимное влияние, на такое перемещение следует наложить ещѐ одно достаточно
сильное ограничение. Это ограничение связано с необходимостью обеспечения требуемой алгоритмом
последовательности действий, например, последовательности ввода-вывода данных, выполняемых
операторами. Однако, поскольку и пока это ограничение не формализовано, контроль за его
удовлетворением оставляем за разработчиком.
Заключение
На базе предложенной модели ЭВМ, у которой информационное множество представляет собой
множество данных, образующих иерархию структур данных произвольной сложности, построена САА\Д и
рассмотрены некоторые еѐ аспекты. Особенности этого формального аппарата позволяют рассчитывать на
решение задач приведенных во введении.
В частности, в рамках КС процесс декомпозиции операторов может осуществляться согласовано с
детализацией данных, которые, как отмечалось, представляют собой иерархию некоторых структур данных .
Такой подход позволяет учитывать как специфику обрабатываемых данных, так и специфику управления
процессом их обработки. Можно сказать, что в рамках предлагаемого формального аппарата, может быть
реализована парадигма программирования, сочетающая положительные черты проектирования алгоритмов и
программ от данных с проектированием от управления.
При этом, выразительность и компактность записи алгоритмов в известной степени обеспечивается за
счет использования трехзначной логики.
Формализация информационных связей в рамках композиционных схем позволяет осуществлять
преобразование алгоритмов.
Перспективным направлением развития рассмотренного алгебраического аппарата является
формализация потоков данных в алгоритмах и решение задач, связанных с их распараллеливанием на основе
такой формализации. Кроме того, актуальной остается задача построения методологии программирования,
основанная на использовании предложенной САА\Д.
1. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм // Кибернетика. – 1965.– № 5. – С. 1–10.
2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наук. думка, 1978.– 319 с.
3. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ: Теоретические основы,
инструментарий. – М.: Финансы и статистика, 1989.– 208 с.
4. Цейтлин Г.Е. Введение в алгоритмику. – К.: “Сфера”, 1998. – 310 с.
5. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е., Яценко Е.А. Алгеброалгоритмические модели и методы параллельного программирования.
– К.: Академперіодика, 2007.– 634 с.
6. Брусенцов Н. П. Трехзначная диалектическая логика // Программные системы и инструменты. Тематический сборник № 2. – М.:
Факультет ВМиК МГУ, 2001. – С. 36–44.
7. Брусенцов Н. П., Владимирова Ю. С. Троичное конструктное кодирование булевых выражений //Программные системы и инструменты.
Тематический сборник № 3 – М.: Факультет ВМиК МГУ, 2002 – С. 6–10.
8. Брусенцов Н. П. Микрокомпьютеры. – М.: Наука, 1985. – С. 141–170.
9. Акуловский В.Г. Некоторые подходы к контролю и преобразованию алгоритмов на основе анализа специфицируемых данных //
Проблеми програмування. – 2008. – № 4.–С. 84–93.
10. Акуловский В.Г. Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей. // Кибернетика и
системный анализ. – 2009.–№ 6.–С. 50–54.
11. Акуловский В.Г. Некоторые аспекты формализации данных и декомпозиция Д-операторов алгебры алгоритмов // Проблеми
програмування. – 2009. – № 4. – C. 3 –10.
|
| id | nasplib_isofts_kiev_ua-123456789-14640 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-01T21:58:52Z |
| publishDate | 2010 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Акуловский, В.Г. 2010-12-27T13:53:53Z 2010-12-27T13:53:53Z 2010 Основы алгебры алгоритмов, базирующейся на данных / В.Г. Акуловский // Пробл. програмув. — 2010. — № 2-3. — С. 89-96. — Бібліогр.: 11 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/14640 519.681 Предложена модель ЭВМ, у которой информационное множество представляет собой множество данных, образующих иерархию структур данных произвольной сложности. На основе этой модели построена система алгоритмических алгебр и рассмотрены некоторые аспекты и перспективы еѐ использования. The model of the computer at which the information set represents set of the data forming hierarchy of structures of the data of any complexity is offered. On the base of this model the system of algorithmic algebras basing the data is constructed, some which prospects of use are considered in the report. ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Основы алгебры алгоритмов, базирующейся на данных Bases of algebra of algorithms basing the data Article published earlier |
| spellingShingle | Основы алгебры алгоритмов, базирующейся на данных Акуловский, В.Г. Теоретичні та методологічні основи програмування |
| title | Основы алгебры алгоритмов, базирующейся на данных |
| title_alt | Bases of algebra of algorithms basing the data |
| title_full | Основы алгебры алгоритмов, базирующейся на данных |
| title_fullStr | Основы алгебры алгоритмов, базирующейся на данных |
| title_full_unstemmed | Основы алгебры алгоритмов, базирующейся на данных |
| title_short | Основы алгебры алгоритмов, базирующейся на данных |
| title_sort | основы алгебры алгоритмов, базирующейся на данных |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/14640 |
| work_keys_str_mv | AT akulovskiivg osnovyalgebryalgoritmovbaziruûŝeisânadannyh AT akulovskiivg basesofalgebraofalgorithmsbasingthedata |