Некоторые аспекты формализации данных и декомпозиция Д-операторов
В рамках расширенной алгебры алгоритмов предложен подход к формализации данных. Рассмотрены свойства формализованных данных и некоторые аспекты декомпозиции Д-операторов. У рамках розширеної алгебри алгоритмів запропоновано підхід до формалізації даних. Розглянуто властивості формалізованих даних і...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6514 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Некоторые аспекты формализации данных и декомпозиция Д-операторов / В.Г. Акуловский // Пробл. програмув. — 2009. — № 4. — С. 03-10. — Бібліогр.: 08 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860261916911337472 |
|---|---|
| author | Акуловский, В.Г. |
| author_facet | Акуловский, В.Г. |
| citation_txt | Некоторые аспекты формализации данных и декомпозиция Д-операторов / В.Г. Акуловский // Пробл. програмув. — 2009. — № 4. — С. 03-10. — Бібліогр.: 08 назв. — рос. |
| collection | DSpace DC |
| description | В рамках расширенной алгебры алгоритмов предложен подход к формализации данных. Рассмотрены свойства формализованных данных и некоторые аспекты декомпозиции Д-операторов.
У рамках розширеної алгебри алгоритмів запропоновано підхід до формалізації даних. Розглянуто властивості формалізованих даних і деякі аспекти декомпозиції Д-операторів.
Within the framework of the expanded algebra of algorithms the approach to formalization of the data is offered. Properties of the formalized data and some aspects of decomposition of D-operators are considered.
|
| first_indexed | 2025-12-07T18:56:23Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
3
УДК 519.683
В.Г. Акуловский
НЕКОТОРЫЕ АСПЕКТЫ ФОРМАЛИЗАЦИИ ДАННЫХ И ДЕ-
КОМПОЗИЦИЯ Д-ОПЕРАТОРОВ
В рамках расширенной алгебры алгоритмов предложен подход к формализации данных. Рассмотрены
свойства формализованных данных и некоторые аспекты декомпозиции Д-операторов.
Введение
Принципиально важная роль дан-
ных в программировании давно осознана
программистским сообществом (см. на-
пример, [1]), что нашло своё выражение в
формализации данных как для компиляции
программ, так и для разработки алгорит-
мов. Учитывая, что возможности формали-
зации данных в алгоритмике реализованы
далеко не полностью. В то же время реше-
ние этой задачи позволяет рассчитывать на
формализацию некоторых аспектов де-
композиции операторов, преобразование
алгоритмов, контроль их корректности и
т.д. на достаточно ранних стадиях разра-
ботки алгоритмов.
Предпосылкой и основой для вы-
полнения данной работы послужила
мысль, высказанная в [2], о том, что в из-
вестной модели ЭВМ В.М. Глушкова [3, 4]
в качестве множества состояний операци-
онного автомата могут рассматриваться
обрабатываемые алгоритмом данные.
Некоторым аспектам формализации
данных в рамках расширенной алгебры
алгоритмов [5], в которую введено поня-
тие взаимосвязи операторов и данных [6],
рассмотрены автором в [7, 8] и ранее по-
лученные результаты в данном случае бу-
дут уточняться и развиваться.
Цель данной работы – разработка
подхода к формализации данных на этапе
декомпозиции операторов, из которых
строится алгоритм в рамках алгебры алго-
ритмов.
Формализация данных
и Д-операторов
Исходя из предпосылки, сформули-
рованной во введении, будем полагать, что
информационное множество (множества
состояний операционного автомата) пред-
ставляет собой множество данных ∆ .
Для того чтобы определить понятие
данные, будем рассматривать их с той
точки зрения, что это совокупности ячеек
памяти iD , представляющие собой мно-
жество U
k
i
iD
1=
=∆ , которые могут прини-
мать некоторые множества значения I
jD
из конечного множества значений
U
k
i
D I
i
1=
=Ψ . Исходя из этого, определим
данные таким образом.
Определение 1. Данными будем
называть такое множество ячеек памяти,
для которых выполняется соотношение
ID
jDj ~ ( ∆⊆jD , Ψ⊆I
jD ), т. е. такое мно-
жество ячеек памяти jD , которому в одно-
значное соответствие поставлено множе-
ство значений I
jD . При этом одновремен-
но любому jD во взаимно однозначное
соответствие может быть поставлено одно
и только одно множество lD I
j
. При
∅=jD , будем считать, что ∅=I
jD .
Теперь, исходя из определения 1,
введем понятие Д-оператора, который из-
меняет состояние операционного автомата.
Определение 2. Д-оператор )()( DAD ′
преобразует множество входных данных
∆⊆D , которому в однозначное соответ-
ствие было поставлено множество значе-
ний II DlD ⊆ ( lDID~ ), в множество выход-
ных данных ∆⊆′D , которому во взаимно
однозначное соответствие ставится мно-
жество значений II DpD ′′ ⊆ ( pD ID ′′~ ). Мно-
© В.Г. Акуловский, 2009
ISSN 1727-4907. Проблеми програмування. 2009. № 4
Теоретичні та методологічні основи програмування
4
жества входных D и выходных D′ дан-
ных могут быть пустыми.
Учитывая, что множества входных
и выходных данных могут быть пустыми,
Д-оператор вида )()( DA ′∅ будем называть
генерирующим, вида )()( ∅AD – неопреде-
ленным, а вида )()( ∅∅ A – тождественным.
Для дальнейшей формализации оп-
ределим структуру входных и выходных
данных Д-операторов.
Определение 3. Представим вход-
ные и выходные данные Д – оператора
)()( DAD ′ в виде следующих подмножеств:
- DDD
)
∪= ˆ , таких, что ∅=∩ DD
)ˆ
и ∅=′∩ DD
)
;
- DDD ′∪′=′ ~ˆ , таких, что
∅=′∩′ DD
~ˆ и ∅=∩′ DD
~
,
которые назовем: D
)
– исходные, D̂ , D ′ˆ –
проходные, D
~
– производные. При этом,
DDDD ′==′∩ ˆˆ . Любое из подмножеств,
образующих множества D и D′ (как и са-
ми эти множества) может быть пустым.
Из определения следуют приве-
денные далее свойства Д-операторов.
Исходные данные не появляются на
выходе Д-оператора и, таким образом, не
изменяются, производные данные не яв-
ляются входными, а продуцируются Д-
оператором и входят в состав выходных, а
множества проходных данных DD ⊆ˆ и
DD ′⊆′ˆ представляют собой одно мно-
жество ячеек памяти, по-разному обозна-
ченное на входе и выходе Д-оператора. То
есть, эти данные, присутствующие на вхо-
де, изменяются, после чего входят в состав
выходных. Для множеств D и D′ допус-
тимо любое из следующих соотношений:
DD ′⊂ , DD ⊂′ , DD ′= ,
∅=′∩ DD , ∅≠′∩ DD .
Исходя из того, что множества
входных и выходных данных могут быть
пустыми и могут пересекаться, приведем
следующие возможные варианты Д-
оператора:
)
~
()( DADDD ′→∅=′∩
)
; (1)
);
~
()(, DADDD ′∅→∅=∅=′∩
)
(2)
)ˆ()ˆ( DADDD ′→′= ; (3)
)ˆ()ˆ,( DADDDD ′→′⊃
)
; (4)
)ˆ,
~
()ˆ( DDADDD ′′→′⊂ ; (5)
)ˆ,
~
()ˆ,( DDADDDD ′′→∅≠′∩
)
. (6)
Для того чтобы определить общий
случай тождественного Д-оператора, вве-
дем понятие неидентичных и идентичных
данных.
Определение 4. Множества данных
iD и jD неидентичны ( ji DD >< ), если
ID
iDi ~ и ID
jDj ~ такие, что ji DD ≠ или/и
II
ji DD ≠ . И множества данных iD и jD
идентичны ( ji DD <> ), если ID
iDi ~ и
ID
jDj ~ такие, что ji DD = и II
ji DD = . В ча-
стном случае, когда ∅== ji DD , они также
идентичны.
То есть, множества данных неиден-
тичны, если это различные множества яче-
ек памяти или, если одно и то же множест-
во ячеек принимает различные значения.
Данные идентичны, если одно и то же
множество ячеек принимает одинаковые
значения.
Исходя из определения 2 – 4, вве-
дем понятие тождественного Д-оператора,
обозначив D
~
– множество производных
данных до выполнения оператора )()( DAD ′ ,
а D′~
– то же множество данных после его
выполнения.
Определение 5. Тождественным
назовем Д-оператор )()( DAD ′ , если для мно-
жеств, образующих выходные данные
D ′ этого оператора, выполняется одно из
следующих пар соотношений:
DD ˆˆ <>′ и DD
~~ <>′ ;
DD ˆˆ <>′ и ∅=′D
~
;
∅==′ DD ˆˆ и DD
~~ <>′ ;
∅==′ DD ˆˆ и ∅=′D
~
.
То есть, множество проходных
данных на входе Д-оператора идентично
множеству проходных данных на его вы-
ходе, а множество производных данных
пусто или не изменяется в результате вы-
Теоретичні та методологічні основи програмування
5
полнения Д-оператора. Проще говоря, Д-
оператор тождественный, если он не изме-
няет обрабатываемых данных. В соответ-
ствии с определением 5, тождественным
является и Д-оператор )()( ∅∅ A , что согла-
суется с определением 2.
Докажем, что в рамках предлагае-
мого подхода Д-оператор и обрабатывае-
мые им данные обладают некоторыми
важными свойствами.
Теорема 1. Д-оператор )()( DAD ′ ,
если он нетождественный, либо преобра-
зует (изменяет) проходные данные, то есть
DD ′>< ˆˆ , либо продуцирует на своем выхо-
де производные данные, т. е. DD
~~ ><′ , либо
выполняет оба действия одновременно.
Доказательство построим от про-
тивного и рассмотрим три возможных слу-
чая, вытекающие из приведенных вариан-
тов Д-оператора (1) – (6).
Первый случай, когда Д-оператор
продуцирует производные данные, а про-
ходные данные отсутствуют ∅=′= DD ˆˆ ,
имеет место, когда выполняются соотно-
шения (1) и (2). Предположив, что Д-
оператор не генерирует производных дан-
ных, т. е. DD
~~ <>′ , то, в соответствии с оп-
ределением 5, получим тождественный Д-
оператор, что противоречит условиям тео-
ремы. Таким образом, Д-оператор в дан-
ном случае продуцирует производные
данные, т. е. DD
~~ ><′ .
Второй случай, когда Д-оператор
не продуцирует производных данных
∅=′D
~
, а обрабатывает только проходные
данные, имеет место, когда выполняются
соотношения (3) и (4). Предположив, что
проходные данные не изменяются, т. е.
DD ′<> ˆˆ , в соответствии с определением 5,
получим тождественный Д-оператор, что
противоречит условиям теоремы. Таким
образом, Д-оператор в данном случае из-
меняет проходные данные, т. е. DD ′>< ˆˆ .
Третий случай, когда Д-оператором
продуцируются производные, а на входе и
выходе присутствуют проходные данные,
имеет место, когда выполняются соотно-
шения (5) и (6).
Предположим, что не изменяются
ни проходные, ни производные данные,
т. е., предположим, что выполняются со-
отношения DD ˆˆ ′<> и DD
~~ <>′ . В этом
случае, в соответствии с определением 5,
получим тождественный Д-оператор, что
противоречит условиям теоремы. Д-
оператор не будет тождественным в слу-
чае, когда выполняется DD ˆˆ ′>< и/или
DD
~~ ><′ , т. е., изменяются проходные
или/и производные данные.
Теорема доказана.
Исходя из доказанной теоремы,
уместно сделать следующее существенное
замечание.
Различия в обозначении множества
проходных данных D̂ на входе и D′ˆ на
выходе Д-оператора, использованное в оп-
ределении 3, обуславливается тем, что они
неидентичны, если Д-оператор нетождест-
венный.
Определив данные, Д-операторы и
некоторые их свойства, перейдем к рас-
смотрению декомпозиции Д-операторов.
Декомпозиция Д-операторов
Начнем с определения операции
композиции, входящей в сигнатуру опера-
ций алгебры алгоритмов.
Определение 6. Композиция Д-
операторов )()(*)()( CCBB DCDDBD ′′ озна-
чает последовательное выполнение сна-
чала Д-оператора )()( BB DBD ′ , а затем Д-
оператора )()( CC DCD ′ . То есть
).())()((
)()(*)()(
BCCBB
CCBB
DDCDDBD
DCDDBD
′∪′∪′=
=′′
Поскольку основным подходом к
разработке алгоритмов является декомпо-
зиция образующих его операторов, введем,
основываясь на определении 6, следую-
щую аксиому.
Аксиома. Любой Д-оператор, за
исключением элементарных, может быть
представлен в виде композиции двух дру-
гих Д-операторов
)()(*)()( )()( CCBBAA DCDDBDDAD ′′=′ ,
Теоретичні та методологічні основи програмування
6
которые в общем случае обладают сле-
дующими свойствами:
AB DD ⊆ , AC DD ′⊆′ ,
∅≠∩ AC DD , ∅≠′∩′ AB DD .
Д-оператор )()( AA DAD ′ будем назы-
вать исходным, а )()( BB DBD ′ и )()( CC DCD ′ –
производными.
Трактовка декомпозиции Д-
операторов, данная в этой аксиоме, допус-
тимая на некотором (достаточно высоком)
уровне абстракции, не позволяет детали-
зовать рассмотрение этой принципиально
важной операции, так как не учитывается
то факт, что производные Д-операторы
совместно решают одну общую для них
задачу, адекватную задаче, решаемой ис-
ходным Д-оператором.
Перечислим те аспекты декомпо-
зиции, которые необходимо реализовать
для того, чтобы учесть упомянутый факт:
1) производные Д-операторы ис-
пользуют (могут использовать) общие
входные данные AD ;
2) выходные данные исходного
Д-оператора AD′ – результат последова-
тельного выполнения результирующих Д-
операторов, т. е. они оба продуцируют
(могут продуцировать) эти данные;
3) второй Д-оператор продолжает
обработку данных (или некоторого их
подмножества), начатую первым Д-
оператором;
4) для обработки данных в подав-
ляющем большинстве алгоритмов исполь-
зуются вспомогательные данные, кото-
рые, не являясь ни входными, ни выход-
ными, служат для преобразования первых
во вторые.
Для того чтобы учесть приведенные
аспекты декомпозиции Д-операторов, за-
пишем выражение из аксиомы в соответ-
ствии со структурой данных, предложен-
ной в определении 3, и определим свойст-
ва обрабатываемых данных, исходя из их
свойств, сформулированных в упомяну-
тых определении и аксиоме.
Определение 7. Данные в выраже-
нии вида
)
~
,ˆ()ˆ,(*)
~
,ˆ()ˆ,(
)
~ˆ()ˆ,(
CCCCBBBB
AAAA
DDCDDDDBDD
DDADD
′′′′=
=′′
))
)
обладают следующими свойствами:
CBA DDD
)))
∪= , AB DD ˆˆ ⊆ , ∅≠∩ AC DD ˆˆ ,
∅≠′∩′ AB DD ˆˆ , AC DD ˆˆ ′⊆′ , ∅≠′∩′ AB DD
~~
,
AC DD ′⊆′ ~~
.
Теперь рассмотрим последовательно
перечисленные аспекты декомпозиции Д-
операторов и определим состав и свойства
данных, которые позволят реализовать
операцию декомпозиции с учетом пере-
численных аспектов.
Для того чтобы учесть первый ас-
пект декомпозиции, определим (детализу-
ем) состав и свойства входных данных Д-
операторов с учетом состава и свойств
данных, введенных в определении 7.
Определение 8. Входные данные
Д-оператора )
~ˆ()ˆ,( AAAA DDADD ′′
)
представ-
ляют собой объединение следующих под-
множеств:
CACBABAA DDDD
))))
∪∪= , ,
CACBABAA DDDD ˆˆˆˆ
, ∪∪= ,
где
BBA DD
))
⊆ , BBA DD ˆˆ ⊆ , CCA DD
))
⊆ ,
CCA DD ˆˆ ⊆ , CCBAB DDD
)))
⊆⊇ , ,
CCBAB DDD ˆˆˆ
, ⊆⊇ .
Из определения следует, что
CBABAB DDD ,
)))
∪= , CBABAB DDD ,
ˆˆˆ ∪= ,
CACBAC DDD
)))
∪= , , CACBAC DDD ˆˆˆ
, ∪= , (7)
а данные CA D
)
и CA D̂ поступают на вход
Д-оператора )()( CC DCD ′ , минуя Д-
оператор )()( BB DBD ′ . Принадлежность
данных к некоторому множеству вход-
ных данных в определении отражена со-
ответствующими индексами.
Таким образом, в общем случае
входные данные исходного Д-оператора
как распределяются между производными
Д-операторами, так и присутствуют на
входе обоих Д-операторов. Поскольку
Теоретичні та методологічні основи програмування
7
любое из подмножеств, образующих
множество входных данных, может быть
пустым, то очевидно, что входные данные
исходного Д-оператора, как исходные AD
)
,
так и проходные AD̂ , могут использовать-
ся как двумя производными Д-
операторами, так и любым одним из них.
Заметим, что множества проход-
ных данных CACBABA DDD ˆ,ˆ,ˆ
, , на входе Д-
операторов, в соответствии с определени-
ем 3, присутствуют и на их выходе. Учи-
тывая это, проходные данные BA D̂ на вы-
ходе Д-оператора )()( BB DBD ′ обозначим
AB D′ˆ , а проходные CA D̂ данные на выходе
Д-оператора )()( CC DCD ′ – AC D′ˆ . Обозначе-
ние для проходных данных CBAD ,
ˆ будет
введено далее.
Для того чтобы учесть второй ас-
пект декомпозиции, определим состав и
свойства данных на выходе Д-оператора
)()( BB DBD ′ .
Определение 9. На выходе Д-
оператора )()( BB DBD ′ из множества про-
изводных данных выделит подмножество
BAB DD ′⊇′ ~~
такое, что AAB DD
~~ ′⊆′ и
∅=∩′ CAB DD
~
. Множество проходных
данных AB D′ˆ , такое, что AAB DD ′⊆′ ˆˆ и
∅=∩′ CAB DD̂ .
То есть, определенные данные по-
ступают с выхода Д-оператора )()( BB DBD ′
на выход исходного Д-оператора, минуя
Д-оператор )()( CC DCD ′ .
Поскольку ∅≠′CD , так как в про-
тивном случае Д-оператор )()( CC DCD ′ бу-
дет неопределенным (см. определение 2),
то из определения 9 следует, что выход-
ные данные Д-оператора )()( AA DAD ′ со-
стоят из выходных данных CD′ Д-
оператора )()( CC DCD ′ , которые дополня-
ются некоторыми подмножествами вы-
ходных данных Д-оператора )()( BB DBD ′ ,
т. е.
ABABCA DDDD ′∪′∪′=′ ~ˆ . (8)
Для того чтобы учесть третий ас-
пект декомпозиции введем понятие ин-
формационной связи (в дальнейшем связи)
между Д-операторами.
Определение 10. Д-операторы
)()(*)()( CCBB DCDDBD ′′ связаны, если для них
выполняется соотношение: ∅≠∩′ CB DD .
Таким образом, в организации свя-
зи участвует некоторое подмножество
выходных данных Д-оператора
)()( BB DBD ′ , которое поступает на вход Д-
оператора )()( CC DCD ′ , что позволяет ему
продолжить их обработку.
При этом будем говорить, что дан-
ные передаются с выхода предшествую-
щего Д-оператора на вход следующего. И
будем полагать, что данные изменяются
только в результате выполнения Д-
операторов, а в процессе передачи остают-
ся неизменными. То есть, данные на вы-
ходе Д-оператора идентичны одноимен-
ным данным на входе следующего Д-
оператора.
Теперь определим, в соответствии
с определениями 10 состав и свойства
данных, связывающих Д-операторы
)()( BB DBD ′ и )()( CC DCD ′ . При этом будем
учитывать, что в качестве таких данных
могут выступать как проходные, так и
производные данные.
Определение 11. Множество про-
ходных данных CBA D ,
ˆ , которое на выходе
и входе Д-операторов )()( BB DBD ′ и
)()( CC DCD ′ обозначим CBA D ,
ˆ ′ , а на выходе
последнего CBA D ,
ˆ ′′ такое, что для него вы-
полняется соотношение
),ˆˆ()ˆˆ(
)ˆˆ()ˆˆ(
,,
,,
CCBACCBA
BCBABCBA
DDDD
DDDD
′⊆′′=⊆=
=′⊆′=⊆
т. е., данные, образующие это множество,
играют роль связывающих, а множества
CBACBACBA DDD ,,,
ˆ,ˆ,ˆ ′′′ , являются одним мно-
жеством, по-разному обозначенным на
входах и выходах Д-операторов. В общем
случае эти множества неидентичны, т. е.
CBACBACBA DDD ,,,
ˆˆˆ ′′><′>< . На выходе
Теоретичні та методологічні основи програмування
8
Д-оператора )()( BB DBD ′ выделим под-
множество производных данных CB D̂
~
та-
кое, что CCBCBB DDDD ˆ~̂~̂~ ⊆=⊇′ , которое на
выходе Д-оператора )()( CC DCD ′ обозна-
чим CB D′~̂
, и которое обладает следующи-
ми свойствами:
∅=′∩ ABCB DD
~~̂
, ∅=′∩ CBACB DD ,
ˆ~̂
,
∅=′∩ CACB DD ˆ~̂
.
Таким образом, данные, получен-
ные на выходе Д-оператора )()( BB DBD ′ ,
могут быть подвержены дальнейшей об-
работке, т. е., обработка данных множест-
ва CBA D ,
ˆ начатая Д-оператором
)()( BB DBD ′ и множества данных CB D̂
~
,
продуцируемого этим Д-оператором, про-
должается Д-оператором )()( CC DCD ′ .
Исходя из определений 9 и 11, за-
пишем состав выходных данных Д-
оператора )()( CC DCD ′ в виде
CCBACBCAC DDDDD ′∪′′∪′∪′=′ ~ˆ~̂ˆ
, , (9)
а исходя из соотношений (8) и (9) – состав
выходных данных Д-оператора )()( AA DAD ′
в виде
CCBACBACABABA DDDDDDD ′∪′′∪′∪′∪′∪′=′ ~ˆ~̂ˆ~ˆ
, . (10)
Для реализации четвертого аспекта
декомпозиции, нам необходимы связы-
вающие данные CB D
(
такие, которые не
являлись бы входными и выходными дан-
ными исходного Д-оператора )()( AA DAD ′ .
Однако, будем утверждать, что такие дан-
ные не могут быть построены.
Утверждение. Связывающие дан-
ные BCB DD ′⊆ ~(
такие, что ∅≠∩ CCB DD
(
и ∅=∩ ACB DD
(
, ∅=′∩ ACB DD
(
, не могут
быть введены в рамках предлагаемых
формализмов, так как требуемое сочета-
ние свойств нереализуемо.
Доказательство. Множество вход-
ных данных Д-оператора )()( CC DCD ′ , в
соответствии с определениями 3, пред-
ставляет собой объединение подмножеств
CCC DDD ˆ∪=
)
, обладающих, в соответст-
вии с определением 7, следующими свой-
ствами AC DD
))
⊆ , ACC DDD ′⊆′= ˆˆˆ . Таким
образом, если ∅≠∩ CCB DD
)(
, то не вы-
полняется соотношение ∅=∩ ACB DD
(
, а
если ∅≠∩ CCB DD ˆ(
, то не выполняется
соотношение ∅=′∩ ACB DD
(
.
Возникшее противоречие вызвано
тем, что необходимые нам данные лока-
лизованы в исходном Д-операторе
)()( AA DAD ′ и не специфицированы в каче-
стве его входных и выходных данных. Та-
кой тип данных в предшествующих рас-
суждениях не рассматривался.
Следствие. Для того чтобы разре-
шить возникшее противоречие, необхо-
димо набор используемых данных допол-
нить данными нового типа - промежу-
точными.
Введем новый тип данных сле-
дующим образом.
Определение 12. Множество вход-
ных данных Д-оператора )()( CC DCD ′ за-
пишем в виде CBCCC DDDD
()
∪∪= ˆ , т. е.
дополним его множеством CB D
(
, а из мно-
жества производных данных на выходе Д-
оператора )()( BB DBD ′ выделим подмно-
жество связывающих данных CB D
(
такое,
что CCBCBB DDDD ⊆=⊇′
((~
. Множество дан-
ных CB D
(
, которые назовем промежуточ-
ными, обладает следующими свойствами:
∅=∩ CCB DD ˆ(
, ∅=∩ CCB DD
)(
,
∅=′∩ CCB DD
(
, ∅=′∩ ABCB DD
~(
,
∅=∩ CBCB DD
~̂(
.
Теперь, исходя из определения 12,
докажем, что построенные данные обла-
дают свойствами необходимыми для про-
межуточных данных.
Теорема 2. Для промежуточных
данных CD
(
выполняются соотношения
∅=∩ ACB DD
(
и ∅=′∩ ACB DD
(
, то есть
они не являются входными и выходными
данными исходного Д-оператора.
Доказательство.
Теоретичні та методологічні основи програмування
9
Чтобы доказать, что промежуточ-
ные данные CB D
(
не пересекаются с вы-
ходными данными AD′ Д-оператора
)()( AA DAD ′ рассмотрим состав выходных
данных ABABCA DDDD ′∪′∪′=′ ~ˆ , приведенный
в (8). Из определения 12 следует, что
∅=′∩ CCB DD
(
и ∅=′∩ ABCB DD
~(
, а из опреде-
ления 9, что ∅=∩′ CAB DD̂ . Но CCB DD ⊆
(
и,
таким образом, ∅=′∩ ABCB DD ˆ(
. Поскольку
множество CB D
(
не пересекается, ни с од-
ним подмножеством, образующим множе-
ство AD′ , то соотношение ∅=′∩ ACB DD
(
выполняется.
Чтобы доказать, что промежуточ-
ные данные CB D
(
не пересекаются с вход-
ными данными AD′ Д-оператора
)()( AA DAD ′ рассмотрим состав этих дан-
ных, приведенный в определении 8,
CACBABAA DDDD
))))
∪∪= , ,
CACBABAA DDDD ˆˆˆˆ
, ∪∪= .
Из определения 12 известно, что
∅=∩ CCB DD
)(
откуда, с учетом (7) следу-
ет, что ∅=∩ CACB DD
)(
и ∅=∩ CBACB DD ,
)(
.
Известно также, что BCB DD ′⊆ ~(
, но
∅=∩′ BB DD
~
(см. определение 3) откуда, с
учетом (7) следует, что ∅=∩ BACB DD
)(
и,
таким образом, ∅=∩ ACB DD
)(
.
Из соотношения ∅=∩′ BB DD
~
также
следует, что ∅=∩′ BB DD ˆ~
и, таким обра-
зом, учитывая (7) ∅=∩ BACB DD ˆ(
и
∅=∩ CBACB DD ,
ˆ(
. Так как ∅=∩ CCB DD ˆ(
(см.
определение 12), то ∅=∩ CACB DD ˆ(
и, та-
ким образом, ∅=∩ ACB DD ˆ(
. Из соотноше-
ния AAA DDD ˆ∪=
)
(см. определение 3) сле-
дует, что соотношение ∅=∩ ACB DD
(
вы-
полняется.
Теорема доказана.
В результате выполненных по-
строений, можем записать выражение из
определения 7 в виде
),
~
,
~̂
,ˆ,ˆ(),
~̂
,ˆ,ˆ
,,*()ˆ,
~̂
,,ˆ
,
~
()ˆ,ˆ,,(
)
~
,
~̂
,ˆ,ˆ,ˆ
,
~
()ˆ,ˆ,ˆ,,,(
,,
,,
,,
,
,,
CCBCBAACCBCBCBACA
CBACACBACBCBAB
ABCBABACBABA
CCBCBAACAB
ABCBACABACBACABA
DDDDCDDDD
DDDDDD
DBDDDD
DDDDD
DADDDDDD
′′′′′′
′′
′=
=′′′′′′
′
(
))(
))
)))
т. е. в виде, когда в декомпозиции Д-
операторов специфицированы все типы
данных, необходимые для реализации
этой операции.
Заключение
В данной работе предложен подход
к формализации данных и построена такая
структура данных, которая позволяет
учесть все перечисленные аспекты деком-
позиции операторов. При этом получены
и доказаны некоторые свойства формали-
зованных данных, которые могут быть ис-
пользованы для контроля корректности
операции декомпозиции.
Полученные результаты позволяют
обратиться к решению следующих задач:
доказательство необходимых условий кор-
ректности реализации операции декомпо-
зиции; согласование процессов декомпо-
зиции Д-операторов и детализации дан-
ных; исследование возможностей преобра-
зования алгоритмов.
Решение этих задач в рамках пред-
лагаемого формального аппарата и являет-
ся направлением дальнейших исследова-
ний.
1. Турский В. Методология программирова-
ния. – М.: Мир, 1981. – 264 с.
2. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П.,
Терзян Т.К. Многоуровневое структурное
проектирование программ: Теоретические
основы, инструментарий. – М.: Финансы и
статистика, 1989. – 208 с.
3. Глушков В.М. Теория автоматов и фор-
мальные преобразования микропрограмм //
Кибернетика, 1965. – № 5. – С. 1 – 10.
4. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра. Языки. Программирование. – К.:
Наук. думка, 1978. – 319 с.
Теоретичні та методологічні основи програмування
10
5. Акуловский В.Г. Расширенная алгебра ал-
горитмов // Проблеми програмування. –
2007. – № 3. – С. 3 – 15.
6. Акуловский В.Г. Формализация взаимосвя-
зей операторов и данных в рамках расши-
ренной алгебры алгоритмов // Кибернетика
и системный анализ. – 2008. – № 6. –
С. 170 – 182.
7. Акуловский В.Г. Некоторые подходы к кон-
тролю и преобразованию алгоритмов на
основе анализа специфицируемых данных
// Проблеми програмування. – 2008. – № 4.
– С. 84 – 93.
8. Акуловский В.Г. Некоторые аспекты фор-
мализации архитектурного этапа разработ-
ки алгоритмов // Проблеми програмування.
– 2009. – № 2. – С. 3 – 11.
Получено 12.10.2009
Об авторе:
Акуловский Валерий Григорьевич,
кандидат технических наук,
доцент кафедры информационных систем
и технологий.
e-mail: valeryakulovskiy@rambler.ru
Место работы автора:
Академия таможенной службы Украины.
49000, Днепропетровск, ул. Дзержинского
2\4. Тел/факс. канцелярия – (0562) 45 5596
e-mail :academy@amsu.dp.ua
|
| id | nasplib_isofts_kiev_ua-123456789-6514 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T18:56:23Z |
| publishDate | 2009 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Акуловский, В.Г. 2010-03-05T15:04:05Z 2010-03-05T15:04:05Z 2009 Некоторые аспекты формализации данных и декомпозиция Д-операторов / В.Г. Акуловский // Пробл. програмув. — 2009. — № 4. — С. 03-10. — Бібліогр.: 08 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/6514 519.683 В рамках расширенной алгебры алгоритмов предложен подход к формализации данных. Рассмотрены свойства формализованных данных и некоторые аспекты декомпозиции Д-операторов. У рамках розширеної алгебри алгоритмів запропоновано підхід до формалізації даних. Розглянуто властивості формалізованих даних і деякі аспекти декомпозиції Д-операторів. Within the framework of the expanded algebra of algorithms the approach to formalization of the data is offered. Properties of the formalized data and some aspects of decomposition of D-operators are considered. ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Некоторые аспекты формализации данных и декомпозиция Д-операторов Деякі аспекти формалізації даних і декомпозиція Д-операторів алгебри алгоритмів Article published earlier |
| spellingShingle | Некоторые аспекты формализации данных и декомпозиция Д-операторов Акуловский, В.Г. Теоретичні та методологічні основи програмування |
| title | Некоторые аспекты формализации данных и декомпозиция Д-операторов |
| title_alt | Деякі аспекти формалізації даних і декомпозиція Д-операторів алгебри алгоритмів |
| title_full | Некоторые аспекты формализации данных и декомпозиция Д-операторов |
| title_fullStr | Некоторые аспекты формализации данных и декомпозиция Д-операторов |
| title_full_unstemmed | Некоторые аспекты формализации данных и декомпозиция Д-операторов |
| title_short | Некоторые аспекты формализации данных и декомпозиция Д-операторов |
| title_sort | некоторые аспекты формализации данных и декомпозиция д-операторов |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6514 |
| work_keys_str_mv | AT akulovskiivg nekotoryeaspektyformalizaciidannyhidekompoziciâdoperatorov AT akulovskiivg deâkíaspektiformalízacíídanihídekompozicíâdoperatorívalgebrialgoritmív |