Повнота алгебри алгоритмів з даними
The completeness of the algorithm algebra with data is shown which is intended for coordinated design of control flow and processed data is shown. The feasibility of an implementation of a control-driven and a data-driven algorithm development using both ascending and descending design strategies is...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | rus |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/207 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозиторії
Problems in programming| id |
pp_isofts_kiev_ua-article-207 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/9d/edfc4d1378a892dcdd0ea82f148d919d.pdf |
| spelling |
pp_isofts_kiev_ua-article-2072024-04-28T11:59:06Z The completeness of the algorithm algebra with data Полнота алгебры алгоритмов с данными Повнота алгебри алгоритмів з даними Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. algorithm algebra with data; completeness of algebraic apparatus; bottom-up and top-down design strategies; control-driven and data-driven development approaches UDC 519.681 алгебра алгоритмов с данными; полнота алгебраического аппарата; восходящая и нисходящая стратегии проектирования; подходы к разработке от управления и от данных УДК 519.681 алгебра алгоритмів з даними; повнота алгебраїчного апарата, висхідна та низхідна стратегії проектування; підходи до розробки від управління та від даних УДК 519.681 The completeness of the algorithm algebra with data is shown which is intended for coordinated design of control flow and processed data is shown. The feasibility of an implementation of a control-driven and a data-driven algorithm development using both ascending and descending design strategies is also considered.Problems in programming 2016; 4: 03-13 Показана полнота алгебры алгоритмов с данными, предназначенной для согласованного проектирования потоков управления и обрабатываемых данных. Рассматривается также реализуемость разработки алгоритмов от управления и от данных с использованием как восходящей, так и нисходящей стратегий проектирования.Problems in programming 2016; 4: 03-13 Показана повнота алгебри алгоритмів з даними, яка призначена для погодженого проектування потоків управління та оброблюваних даних. Розглядається також можливість реалізації розробки алгоритмів від управління та від даних із використанням як висхідної, так і низхідної стратегій проектування.Problems in programming 2016; 4: 03-13 Інститут програмних систем НАН України 2018-07-03 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/207 10.15407/pp2016.04.003 PROBLEMS IN PROGRAMMING; No 4 (2016); 3-13 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2016); 3-13 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2016); 3-13 1727-4907 10.15407/pp2016.04 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/207/200 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:59:06Z |
| collection |
OJS |
| language |
rus |
| topic |
algorithm algebra with data completeness of algebraic apparatus bottom-up and top-down design strategies control-driven and data-driven development approaches UDC 519.681 алгебра алгоритмов с данными полнота алгебраического аппарата восходящая и нисходящая стратегии проектирования подходы к разработке от управления и от данных УДК 519.681 алгебра алгоритмів з даними; повнота алгебраїчного апарата висхідна та низхідна стратегії проектування; підходи до розробки від управління та від даних УДК 519.681 |
| spellingShingle |
algorithm algebra with data completeness of algebraic apparatus bottom-up and top-down design strategies control-driven and data-driven development approaches UDC 519.681 алгебра алгоритмов с данными полнота алгебраического аппарата восходящая и нисходящая стратегии проектирования подходы к разработке от управления и от данных УДК 519.681 алгебра алгоритмів з даними; повнота алгебраїчного апарата висхідна та низхідна стратегії проектування; підходи до розробки від управління та від даних УДК 519.681 Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. Повнота алгебри алгоритмів з даними |
| topic_facet |
algorithm algebra with data completeness of algebraic apparatus bottom-up and top-down design strategies control-driven and data-driven development approaches UDC 519.681 алгебра алгоритмов с данными полнота алгебраического аппарата восходящая и нисходящая стратегии проектирования подходы к разработке от управления и от данных УДК 519.681 алгебра алгоритмів з даними; повнота алгебраїчного апарата висхідна та низхідна стратегії проектування; підходи до розробки від управління та від даних УДК 519.681 |
| format |
Article |
| author |
Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. |
| author_facet |
Akulovskiy, V.G. Doroshenko, А.Yu. Yatsenko, O.A. |
| author_sort |
Akulovskiy, V.G. |
| title |
Повнота алгебри алгоритмів з даними |
| title_short |
Повнота алгебри алгоритмів з даними |
| title_full |
Повнота алгебри алгоритмів з даними |
| title_fullStr |
Повнота алгебри алгоритмів з даними |
| title_full_unstemmed |
Повнота алгебри алгоритмів з даними |
| title_sort |
повнота алгебри алгоритмів з даними |
| title_alt |
The completeness of the algorithm algebra with data Полнота алгебры алгоритмов с данными |
| description |
The completeness of the algorithm algebra with data is shown which is intended for coordinated design of control flow and processed data is shown. The feasibility of an implementation of a control-driven and a data-driven algorithm development using both ascending and descending design strategies is also considered.Problems in programming 2016; 4: 03-13 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/207 |
| work_keys_str_mv |
AT akulovskiyvg thecompletenessofthealgorithmalgebrawithdata AT doroshenkoayu thecompletenessofthealgorithmalgebrawithdata AT yatsenkooa thecompletenessofthealgorithmalgebrawithdata AT akulovskiyvg polnotaalgebryalgoritmovsdannymi AT doroshenkoayu polnotaalgebryalgoritmovsdannymi AT yatsenkooa polnotaalgebryalgoritmovsdannymi AT akulovskiyvg povnotaalgebrialgoritmívzdanimi AT doroshenkoayu povnotaalgebrialgoritmívzdanimi AT yatsenkooa povnotaalgebrialgoritmívzdanimi AT akulovskiyvg completenessofthealgorithmalgebrawithdata AT doroshenkoayu completenessofthealgorithmalgebrawithdata AT yatsenkooa completenessofthealgorithmalgebrawithdata |
| first_indexed |
2024-09-16T04:08:16Z |
| last_indexed |
2024-09-16T04:08:16Z |
| _version_ |
1812407891091521536 |
| fulltext |
Теоретичні та методологічні основи програмування
© В.Г. Акуловский, А.Е. Дорошенко, Е.А. Яценко, 2016
ISSN 1727-4907. Проблеми програмування. 2016. № 4 3
УДК 519.681
В.Г. Акуловский, А.Е. Дорошенко, Е.А. Яценко
ПОЛНОТА АЛГЕБРЫ АЛГОРИТМОВ С ДАННЫМИ
Показана полнота алгебры алгоритмов с данными, предназначенной для согласованного проектирова-
ния потоков управления и обрабатываемых данных. Рассматривается также реализуемость разработки
алгоритмов от управления и от данных с использованием как восходящей, так и нисходящей стратегий
проектирования.
Ключевые слова: алгебра алгоритмов с данными, полнота алгебраического аппарата, восходящая и
нисходящая стратегии проектирования, подходы к разработке от управления и от данных.
Введение
О чрезвычайной важности роли
данных в процессе разработки алгоритмов
и программ и, соответственно, о неразрыв-
ной связи программ и обрабатываемых
данных и невозможности рассматривать
одни в отрыве от других известно доста-
точно давно [1, 2]. Вместе с тем, задача
совместного и согласованного проектиро-
вания потоков управления и данных в рам-
ках существующих формальных специфи-
каций алгоритмов не рассматривается (см.
например, [3]). Для решения этой задачи
был разработан алгебраический аппарат
(алгебра алгоритмов с данными) [4].
К числу важных алгебраических
проблем относится доказательство полно-
ты алгебраического аппарата. В процессе
рассмотрения этой проблемы будем учи-
тывать, что проектирование алгоритма, как
известно, может осуществляться в рамках
восходящей и нисходящей стратегий раз-
работки, с использованием подходов к
программированию – от управления
(функционально-ориентированный под-
ход) и от данных.
Цель данной работы – доказатель-
ство возможности разработки средствами
предложенной алгебры произвольных ал-
горитмов с согласованными описаниями
потоков управления и обрабатываемых
данных на каждом шаге проектирования,
при реализации указанных стратегий и
подходов к программированию.
1. Алгебра алгоритмов с данными
Алгебра алгоритмов с данными по-
строена в результате модификации извест-
ной модели ЭВМ Глушкова [5], которая
расширена за счет введения носителя дан-
ных. Носитель данных отождествляется с
памятью и устройствами ввода-вывода, а
множество хранимых данных обозначено
ACD . Данными называется пара
З,jND ( ACDD ),
где nз ,...,зЗ 1 – кортеж последователь-
но расположенных значений, определяю-
щий в каждый момент времени текущее
состояние данных, носитель которого jN ,
однозначно идентифицируется индексом
Jj , который интерпретируется как ад-
рес, принадлежащий множеству доступ-
ных адресов J .
Введены Д-операторы )()( DXD ,
на входе и выходе которых специфициро-
ваны множества обрабатываемых этим
Д-оператором данных. Приведем опреде-
ления Д-операторов, актуальных для дан-
ной работы.
Определение 1. Д-оператор
)()( DOD обрабатывает множество дан-
ных
ACDDo и только это множество.
Процесс обработки представляет собой
некоторую конечную последовательность
элементарных действий (операций), кото-
рую будем называть функциональностью
этого Д-оператора. Функциональность
)()( DOD и множество данных oD “со-
гласованы”, если эта функциональность
необходима и достаточна для обработки
множества данных oD , а это множество
необходимо и достаточно для реализации
этой функциональности. Входные D и,
Теоретичні та методологічні основи програмування
4
изменяемые в результате выполнения
Д-оператора, выходные D данные назы-
ваются наблюдаемыми, а данные, обра-
зующие множество )(\ DDDD onn , –
ненаблюдаемым.
Предложенное определение позво-
ляет на каждом уровне детальности пред-
ставления Д-оператора рассматривать
только актуальные (наблюдаемые) для
данного уровня данные D и D и абстра-
гироваться от неактуальных (ненаблюдае-
мых) данных nnD .
Второй тип Д-оператора –
)()( PD , называемый предикатом, пред-
ставляет собой n -местную (в общем слу-
чае) логическую функцию
2: EDP , где D – график некото-
рого n -арного отношения, }0 ,1{2 E , –
двузначное логическое условие, анализи-
рующее множество данных D и проду-
цирующее логическое условие , характе-
ризующее отношение между текущими
значениями этих данных.
На множестве логических условий
определены следующее известные булевы
операции: конъюнкция ( ), дизъюнкция
( ), отрицание ( ) с известными табли-
цами истинности (см. например, [6]).
На множестве Д-операторов опре-
делены операции, из числа которых приве-
дем следующие.
Композиция Д-операторов
)
~
(
~
)
~
()()( DODDOD означает последова-
тельное выполнение сначала Д-оператора
)()( DOD , а затем Д-оператора )
~
(
~
)
~
( DOD .
Композиция предикатов, с учетом введен-
ных логических операций, записывается в
виде )()()()( PDPD , где – одна из
логических операций.
p-дизъюнкция
))()()())]((()[( 222111 DODDODPD
,0 если ),()(
1; если ),()(
222
111
DOD
DOD
в результате выполнения которой выбира-
ется один из двух возможных
Д-операторов в соответствии со значением
логического условия .
р-итерация )}())]{(()[( DODPD
осуществляет циклическое выполнение
Д-оператора )()( DOD при 1 и завер-
шается в противном случае.
Исходя из того, что элементарные
данные эD – это данные, не подлежащие
детализации, приведем определение
иерархически организованных (в даль-
нейшем, иерархических) данных.
Определение 2. Любые данные
иD – иерархические ( ии SD , где иS –
множество иерархических данных), если
они представляют собой иерархическое
множество
),...,2,1(|
, ,...,
и
21
nkiDD kiii k
,
где k – уровень иерархии, n – число
уровней иерархии, ki – номер элемента на
k -м уровне иерархии ( 11 i ). Каждый j -й
уровень иерархии представляет собой
множество данных } ,...,,{
21 jjj p
DDD , ре-
ализующих более детальное представле-
ние данных предыдущего ( 1j )-го уров-
ня. Каждая i -я спецификация j -го уровня
ji
D детализуется и на следующем ( 1j )
уровне представляет множество
},...,,{
111 21 jjj p
DDD . Последний ( k -й)
уровень иерархии представляет собой
множество элементарных данных
},...,{ ээЭ
1 pkk DDS такое, что
ЭЭ SS ,
где иЭ SS – конечное множество эле-
ментарных данных.
На множестве иерархических дан-
ных введены следующие операции.
Операция укрупнения
DDDD k },...,,{* 21 определена на множе-
стве
иS . Результатом выполнения этой
операции являются данные на более высо-
ком уровне иерархии.
Операция детализации данных
},...,,{* 21 kDDDD определена на множе-
Теоретичні та методологічні основи програмування
5
стве иS и не определена на множестве
ЭS . Результатом выполнения этой опера-
ции являются данные на более низком
уровне иерархии.
Таким образом, предложена систе-
ма алгоритмических алгебр
};,,{::=Д\САА иSLX ,
где X – множество Д-операторов, L –
множество логических условий, иS –
множество иерархических данных, –
сигнатура алгебры, включающая опера-
ции 1 , определенные на множестве X ,
операции 2 , определенные на множестве
L , и 3 , определенные на этом множестве
иS .
Проблему полноты алгебраической
системы начнем с рассмотрения возмож-
ностей декомпозиции и объединения
Д-операторов.
2. Объединение и декомпозиция
Д-операторов
Воспользовавшись результатами,
полученными в работах [7, 8], докажем,
что Д-операторы могут быть объединены и
декомпозированы. Прежде чем перейти к
доказательству, введем некоторые новые
понятия и термины, необходимые для его
осуществления.
Для описания алгоритмов исполь-
зуются регулярные схемы (РС), представ-
ляющие собой суперпозиции Д-операторов
и операций алгебры [5, 6]. Учитывая, что
на функциональность Д-операторов не
накладываются ограничения, будем рас-
сматривать операции алгебры как специ-
альный тип Д-операторов. То есть опера-
ции р-дизъюнкции
))()(*)())]((()[( 222111 DODDODPD
соответствует Д-оператор
)()( д DOD , где )( 21 DDDD ,
)( 21 DDD
(1)
а р-итерации )}())]{(()[( DODPD –
Д-оператор
)()( и DOD , где )( DDD ,
DD .
(2)
При записи алгоритмов в виде су-
перпозиции Д-операторов, включающих
введенные выше, полученные схемы бу-
дем называть композиционными (КС). В
общем случае будем говорить, что алго-
ритм описывается с помощью схемы алго-
ритма (СА).
Понятие, – состояние вычислитель-
ного процесса (ВП), введенное в рабо-
те [4], определим, учитывая специфику
данной работы, в упрощенном варианте.
Определение 3. Исходным для
Д-оператора )()( DOD состоянием ВП
называется множество данных TD
, где
TDD
, значения которых изменяются в
результате и только в результате выполне-
нием Д-оператора, в результате чего ВП
переходит в результирующе состояние TD
,
где TDD
. Композиция Д-операторов
)
~
(O
~
)
~
()()( DDDOD переводит ВП из ис-
ходного состояния TD
, где
TDD
, в со-
стояние TD
, где TDDD
~
, , и состояние
TD
, где
TDD
~
. Для любого состояния
ВП TD выполняется
TDD AC
.
Теперь остановимся на рассмотре-
нии особенностей выполнения композиции
Д-операторов )
~
(O
~
)
~
()()( DDDOD . Каж-
дый из Д-операторов, входящий в компо-
зицию, решает свою локальную задачу по
обработке локальных данных. При этом
композиция Д-операторов решает некото-
рую глобальную задачу по преобразова-
нию глобальных входных данных в вы-
ходные, характерную для данной компо-
зиции. Решение этой глобальной задачи
осуществляется как независимо каждым из
Д-операторов, так и совместно обоими
Д-операторами.
В связи с указанными особенностя-
ми выполнения композиции Д-операторов,
введем следующее определение.
Определение 4. В композиции
Д-операторов )
~
(O
~
)
~
()()( DDDOD на вхо-
де и выходе )()( DOD специфицированы
Теоретичні та методологічні основи програмування
6
ЛDDD и CBЛСБ DDDD , а
на входе и выходе )
~
(O
~
)
~
( DD –
CBЛСБ ~~~
DDDD и Л~~~
DDD ,
где D , D
~
, СБD , СБ~
D – глобальные,
ЛD , ЛD , Л~
D , Л~
D – локальные данные.
СБD и СБ~
D – собственные данные такие,
что СБ~
D не обрабатываются Д-оператором
)()( DOD , а СБD – )
~
(O
~
)
~
( DD . CBD – свя-
зывающие данные такие, что
DDD
~CB . Локальные данные обраба-
тываются только одним Д-оператором и
специфицированы только на его входе и
выходе.
Определение 4 поясним следующим
образом.
Собственные данные СБD являются
результатом выполнения только
Д-оператора )()( DXD , СБ~
D – обрабаты-
ваются только Д-оператором )
~
(X
~
)
~
( DD , а
связывающие данные СBD обрабатываются
совместно двумя Д-операторами. В част-
ных случаях, любое из множеств данных
на входе и выходе Д-операторов, но не все
сразу, могут быть пустыми.
Теперь определим понятие эквива-
лентности Д-оператора и композиций
Д-операторов.
Определение 5. Д-оператор )()( DOD
и композиция Д-операторов )()( DOD
)
~
(O
~
)
~
( DD эквивалентны, если, при равен-
стве их исходных состояний ВП
( TT DD
), результатом их выполнения
явятся равные результирующие состояния
( TT DD
). Д-оператор )()( DOD принад-
лежит к более высокому (укрупненному), а
композиция к более низкому (детальному)
уровням описания алгоритма, если на вхо-
де и выходе )()( DOD специфицированы
только глобальные данные эквивалентной
ему композиции.
Доказательство возможности объ-
единения Д-операторов предварим следу-
ющей леммой.
Лемма 1. В композиции
Д-операторов )
~
(O
~
)
~
()()( DDDOD для
собственных данные СБD и СБ~
D выпол-
няются соотношения
TDD
СБ
,
TDD
СБ~
, а ненаблюдаемые данные nnD
входят в состав данных, образующих со-
стояние ВП.
Доказательство. Из определений 1,
3, 4 известно, что ACСБСБ ,,
~
DDDD nn , а
для собственных данных выполняются со-
отношения TDDD
СБСБ ,
~
.
Поскольку, в соответствии с опре-
делением 3, для любого TD выполняется
TDD AC , то ненаблюдаемые данные nnD
входят в состав данных, образующих со-
стояния ВП ( Tnn DD ), а для СБСБ ,
~
DD ,
которые, в соответствии с определением 4,
не изменяются Д-операторами )()( DOD и
)
~
(O
~
)
~
( DD , выполняются соотношения
TDD
СБ
,
TDD
СБ~
.
Лемма доказана.
Покажем, что любая композиция
Д-операторов может быть преобразована в
новый Д-оператор.
Теорема 1. В результате объедине-
ния произвольных Д-операторов (в част-
ности, )()( д DOD , )()( и DOD ), входящих
в композицию )
~
(O
~
)
~
()()( DDDOD , будет
осуществлен переход на более высокий
(укрупненный) уровень представления ал-
горитма. Полученный в результате объ-
единения Д-оператор )()( DOD будет экви-
валентен исходной композиции, если его
входные и выходные данные такие, что
)
~
( СБDDD , где )\( ЛDDD , и
)
~
( СБ DDD , где )
~
\
~
(
~ ЛDDD . При
этом, если функциональность каждого из
исходных Д-операторов задана, а обраба-
тываемые данные с ней согласованы, то у
производного Д-оператора функциональ-
ность то же будет задана, а обрабатывае-
мые им данные с ней согласованы.
Доказательство. Запишем данные в
композиции Д-операторов )()( DOD
)
~
(O
~
)
~
( DD , в соответствии с определени-
ем 4. В результате получаем её в виде
Теоретичні та методологічні основи програмування
7
),,(),( СBЛСБЛ DDDODD
).
~
,
~
(
~
)
~
,
~
,( ЛЛСБСB DDODDD
Собственные данные СБD и СБ~
D
переместим на вход O и выход O
~
, соот-
ветственно. В результате этого, получаем
композицию Д-операторов
),(),,
~
( СBЛЛСБ DDODDD
).,
~
,
~
(O
~
)
~
,( СБЛЛСB DDDDD
Локальные и связывающие данные
переведем в разряд ненаблюдаемых
( nnDDDDDD ЛЛСBЛЛ ~
,
~
,,, ). Состоя-
ние ВП TD
, где имеют место только нена-
блюдаемые данные, исключим из рассмот-
рения. Совокупную функциональность
Д-операторов O и O
~
обозначим, как O , а
входные и выходные данные – как D и
D . В результате получаем Д-оператор
)()( DOD , где )
~
( СБDDD , )
~
( СБDDD .
Поскольку состав данных в состоя-
ниях ВП TD
и TD
, не взирая на выпол-
ненные преобразования, в соответствии с
леммой 1, не изменился, функциональ-
ность полученного Д-оператора по постро-
ению соответствует совокупной функцио-
нальности исходной композиции, а все не-
наблюдаемые данные, в соответствии с
определением 1, обрабатываются, то, по-
лученный Д-оператор, в соответствии с
определением 5, эквивалентен исходной
композиции и принадлежит к более высо-
кому (укрупненному), уровню описания
алгоритма.
Если функциональность каждого из
Д-операторов, входящих в композицию
)
~
(O
~
)
~
()()( DDDOD и обрабатывающих, в
соответствии с определением 1, данные
oD и oD
~
, задана и согласована с этими
данными, то у производного Д-оператора,
который по построению обрабатывает
множество данных ooo DDD
~
, и имеет
функциональность, совпадающую с сово-
купной функциональностью исходных,
функциональность тоже задана, а обраба-
тываемые данные с ней согласованы.
Теорема доказана.
Следствие 1. Из обобщения резуль-
тата доказанного в теореме легко увидеть,
что в результате объединения нескольких
произвольных Д-операторов, организован-
ных в произвольную последовательность,
будет получен производный Д-оператор
)()(...)()( 111 kkk DODDOD
),()( DOD
функциональность которого соответствует
совокупной функциональности исходных.
Если в каждом из исходных Д-операторов
функциональность задана и согласована с
обрабатываемыми данными, то она задана
и согласована с обрабатываемыми данны-
ми и в производном Д-операторе.
Следствие 2. Состав данных на
входе и выходе производного Д-оператора
однозначно определяется составом данных
на входах и выходах исходных
Д-операторов и в общем случае
)...( СБСБ
21 kDDDD ,
)...( СБ
1
СБ
1 kk DDDD .
Следствие 3. Композиция предика-
тов (см. определение операции компози-
ции) преобразуется в предикат
)()()()(...)()( 111 PDPDPD kkk ,
где k...1 ( – логическая опера-
ция),
DDD k )...( 1 .
Теперь покажем возможность по-
строения производных Д-операторов в ре-
зультате декомпозиции исходного. Опира-
ясь на определение 1, будем полагать, что
Д-оператор не элементарный, если его
функциональность реализуется несколь-
кими элементарными операциями.
Теорема 2. Любой не элементарный
Д-оператор )()( DOD (за исключением
)()( д DOD , )()( DOD и ) может быть де-
композирован – представлен на более де-
тальном уровне описания в виде компози-
ции Д-операторов )
~
(O
~
)
~
()()( DDDOD ,
которая будет ему эквивалентна, если на
входах и выходах производных
Теоретичні та методологічні основи програмування
8
Д-операторов специфицированы следую-
щие данные:
ЛСБ )
~
\( DDDD , ЛCBСБ DDDD ,
ЛCBСБ ~~~
DDDD , ЛСБ ~
)\(
~
DDDD .
Доказательство. Воспользовавшись
тем, что, по условию теоремы, Д-оператор
)()( DOD не элементарный, будем полагать,
что его функциональность представляет
собой два этапа, которые реализуются
Д-операторами O , O
~
, и которые связаны
операцией композиции, в соответствии с
её определением. В результате такого по-
строения получаем новое состояние ВП
TD
(см. определение 3), в котором все
данные ненаблюдаемые.
Переведем, с учетом определения 4,
ненаблюдаемые данные
nnDDDDDD CBЛЛЛЛ ,
~
,
~
,,
в разряд наблюдаемых, а полученную
композицию Д-операторов запишем в виде
),(),( CBЛЛ DDODD
)
~
,(
~
)
~
,( ЛЛCB DDODD ,
где TDDD
),( Л , TDDDD
)
~
,,( ЛCBЛ ,
TDDD
)
~
,( Л .
В общем случае в результате разби-
ения функциональности на некоторое
подмножество данных DD СБ~
будет обра-
батываться на втором этапе, а некоторое
подмножество DD СБ является результа-
том выполнения только первого этапа. Эти
подмножества, в соответствии с определе-
нием 4, – собственные данные
Д-операторов O и O
~
, соответственно.
Исходя из этого, переместим спе-
цификации этих данных таким образом,
что будет получена композиция в виде
),,(),( CBЛСБЛ DDDODD
),
~
,
~~
)
~
,
~
,( ЛЛСБCB DD(ODDD ,
где СБ~
\ DDD и СБ\
~
DDD .
Так как в полученной композиции,
в соответствии с леммой 1, состояния ВП
TD
и TD
не изменились, каждый произ-
водный Д-оператор обрабатывает свои
собственные данные, а совокупная функ-
циональность производных Д-операторов
(по построению) совпадает с функцио-
нальностью исходного, то, в соответствии
с определением 5, производная компози-
ция и исходный Д-оператор эквивалентны,
а полученная композиция принадлежит к
более низкому (детальному) уровню опи-
сания алгоритма.
Теорема доказана.
Следствие 1. Из обобщения резуль-
тата, доказанного в теореме, легко уви-
деть, что не элементарный Д-оператор
)()( DOD может быть декомпозирован, то
есть, представлен в виде произвольной по-
следовательности Д-операторов
)()(...)()()()( 111 kkk DODDODDOD ,
совокупная функциональность которой
совпадает с функциональностью исходно-
го Д-оператора.
Следствие 2. Состав входных и вы-
ходных данных производных Д-опера-
торов, для которых выполняются соотно-
шения
)...( 1 kDDD , )...( 1 kDDD
зависит от способа декомпозиции и соста-
ва входных и выходных данных исходного
Д-оператора.
Следствие 3. Предикаты декомпо-
зируются в виде
)()(...)()()()( 111 kkk PDPDPD ,
где k ...1 ( – логическая опера-
ция), )...( 1
kDDD .
Доказанные теоремы являются
обоснованием возможности реализации
восходящей и нисходящей стратегий про-
ектирования алгоритмов.
3. Полнота алгебраического
аппарата
Прежде, чем перейти к доказатель-
ству полноты алгебры, уточним некоторые
использованные выше понятия посред-
ством следующих рассуждений.
Теоретичні та методологічні основи програмування
9
Алгоритм решения некоторой зада-
чи – это некоторый Д-оператор )()( DAD ,
который обладает функциональностью
(см. определение 1), обеспечивающей ре-
шение этой задачи. При нисходящем про-
ектировании алгоритм декомпозируется до
получения некоторых элементарных
Д-операторов, а при восходящем строится,
начиная с них.
Учитывая это, определим элемен-
тарные Д-операторы.
Определение 6. Элементарными
называются Д-операторы )()( э DОD , не
подлежащие декомпозиции, функциональ-
ность которых задана и согласована с об-
рабатываемыми данными. В случае проек-
тирования от данных на входах и выходах
элементарных Д-операторов специфици-
рованы только элементарные данные
DD э
и/или DD э . Элементарные
Д-операторы образуют конечное множе-
ство XX Э , где X – множество
Д-операторов.
Кроме того, разработка осуществ-
ляется, в соответствии со спецификой ал-
горитмов, с использованием двух подхо-
дов: от управления и от данных.
При первом подходе, ориентиро-
ванном на разработку управляющих (и по-
добных) систем, последовательность под-
задач, на которые разбивается алгоритм,
зависит, обычно, от особенностей функци-
онирования объекта управления.
При втором подходе, ориентиро-
ванном на разработку информационных (и
подобных) систем, на последовательность
выполнения упомянутых подзадач суще-
ственным образом влияет структура
иерархических данных. В этом случае про-
ектирование осуществляется до достиже-
ния такого уровня представления алгорит-
ма, на котором все иерархические данные
детализованы до уровня элементарных.
Доказательство полноты алгебры
предварим следующей леммой.
Лемма 2 (о функциональной пол-
ноте алгебры данных). Произвольные
иерархические данные
ии SD могут
быть получены из наперед заданного ко-
нечного множества элементарных данных
},...,,{ ээ
2
э
1
Э
pDDDS и детализованы до
получения элементарных данных, если
множество ЭS включает элементарные
данные последнего ( k -го) уровня пред-
ставления любых иерархических данных
ии SDi .
Доказательство. Пусть задано неко-
торое конечное множество элементарных
данных },...,,{ ээ
2
э
1
Э
pDDDS и произволь-
ные иерархические данные
ии SD .
Выбрав из множества ЭS подмно-
жество ЭS , элементы которого предпо-
ложительно образуют нижний слой иерар-
хического множества иD , построим из
них с помощью операции укрупнения
ikji DDD 1
ээ },...,{* все данные ( 1k )-го
уровня иерархии. В результате получаем
множество данных },...,{ 111 skk DD . Да-
лее, действуя аналогично, будем целена-
правленно строить данные на всех выше-
лежащих уровнях до получения иD .
Если сделанные выше и на всех
этапах построения иерархических данных
предположения не реализуются, то есть
полученные на 1k ( ik D1 ) или любом
вышележащем уровне иерархии данные (в
том числе иD ) не соответствуют требуе-
мым, то возвращаемся на любой из уров-
ней для его корректировки. В случае необ-
ходимости, выбираем другое множество
элементарных данных ЭS . Поскольку, в
соответствии с определением 2 и условием
леммы, множество ЭS конечно, а множе-
ство
ЭЭ SS существует, то за конечное
число попыток множество ЭS будет
найдено, а иерархические данные иD бу-
дут получены.
Применяя операцию детализации
данных к данным иD },...,{*
111 pDDD и
на всех уровнях их иерархии, получаем, по
условию теоремы и, в соответствии с
определением 2, множество элементарных
данных ЭЭээ
2
э
1 },...,,{ SSDDD r .
Лемма доказана.
Теоретичні та методологічні основи програмування
10
Покажем возможность проектиро-
вания произвольного алгоритма )()( DAD
полагая, что он принадлежит некоторому
множеству алгоритмов A .
Теорема 3 (о функциональной пол-
ноте). В рамках САА\Д произвольный ал-
горитм A)()( DAD , может быть постро-
ен от управления, если заданное множе-
ство элементарных Д-операторов ЭX до-
статочно для реализации функционально-
сти любого алгоритма из A , а алгебра ло-
гики функционально полна. Если, при
этом, DD и
и/или DD и , алгебра
данных функционально полна, и для лю-
бых элементарных данных эээ , SDD ii в
множестве ЭX найдутся элементарные
Д-операторы )()( э DОD такие, что
DDi э
и/или DDi э , то алгоритм мо-
жет быть построен от данных. Процесс
проектирования может осуществляться с
использованием как нисходящей, так и
восходящей стратегий, и на всех его эта-
пах функциональность производных
Д-операторов будет согласована с обраба-
тываемыми данными.
Доказательство. Зададимся конеч-
ным множеством элементарных Д-опера-
торов
)}()(),...,(){( э
1
э
11
Э
nnn DОDDОDX
и конечными множествами элементарных
данных
},...,{ ээ
1
Э
sDDS , },...,{ ээ
1
Э
pDDS ,
где ЭЭЭ SSS , такими, что они соот-
ветствуют условиям теоремы.
Рассмотрим реализацию нисходя-
щей стратегии проектирования алгоритма
A)()( DAD .
Исходя из теоремы 2 и следствия 1
из неё, запишем алгоритм в виде КС
)()( DAD
),()(...)()( 111111111 kkk DODDOD
где левый нижний индекс указывает шаг
проектирования. Производные Д-опера-
торы выбираются исходя из предположе-
ния, что совокупная их функциональность
обеспечивает требуемую алгоритмом
функциональность.
В случае реализации подхода от
данных, когда, в соответствии с условием
теоремы, для алгоритма )()( DAD выпол-
няются соотношения DD и
и/или
DD и . Процесс проектирования начи-
нается с детализации иерархических дан-
ных },...,{* 1
и
pDDD , },...,{* 1
и
rDDD ,
а декомпозиция осуществляется аналогич-
но вышерассмотренному случаю, с тем
дополнением, что, с учетом следствия 2 из
теоремы 2, для любых иDDi и иDDi
выполняются соотношения pi DD 1 и
si DD 1 .
Если в результате декомпозиции
получены Д-операторы вида
)()( 1
д
11 iii DOD или )()( 1
и
11 iii DOD , то, в
соответствии с (1) и (2), они заменяются
соответствующими операциями алгебры, в
результате чего получаем РС.
Применяя описанный выше подход
ко всем производным Д-операторам, полу-
чаем более детальное описание каждого из
них в виде
)()()()( 121212111 DODDOD iii
.)()(... 222 sss DOD
Если на предыдущем шаге деком-
позиции была получена РС, то декомпози-
руются Д-операторы и предикаты, вхо-
дившие в операции алгебры. Последние, в
соответствии со следствием 3 из теоре-
мы 2, записываются в виде КС
).()(...)()()()( 2212121
ppi PDPDPD
Процесс проектирования от управ-
ления продолжается до получения сово-
купности СА, каждая из которых записы-
вается в виде
)()()()( 1
э
11111 DODDOD kkkikikik
),()(... э
pkpkpk DOD
где все производные Д-операторы элемен-
тарные.
Теоретичні та методологічні основи програмування
11
Поскольку по условию теоремы ал-
гебра данных полна, то, в соответствии с
леммой 2, в результате детализации иерар-
хических данных будет получено множе-
ство элементарных данных
ээ SS . Так
как, по условию теоремы для любых эле-
ментарных данных эээ , SDD ii выпол-
няются соотношения jki DD э и/или
ski DD э , то процесс проектирования от
данных завершится после получения ана-
логичной совокупности СА, в которой
производные Д-операторы обрабатывают
все элементарные данные из эS .
Перейдем к рассмотрению восхо-
дящей стратегии проектирования.
В соответствии со следствием 1 из
теоремы 1, построим совокупность СА,
каждая из которых записывается в виде
)()(...)()( э
1
э
11 pkpkpkkkk DODDOD
),()( 111 ikikik DOD
где элементарные Д-операторы выбирают-
ся и располагаются в некоторой последо-
вательности исходя из предположения, что
их совокупная функциональность соответ-
ствует требуемой функциональности про-
изводного Д-оператора )()( 111 ikikik DOD .
Процесс проектирования от данных
начинается с построения иерархических
данных, что для каждого случая записыва-
ется с использованием операции укрупне-
ния данных в виде DDD ji },...,{* ээ ,
DDD sr },...,{* ээ
, исходя из предположе-
ния, что производные данные D и D со-
ответствуют )( 1k -му уровню иерархии
данных. Построение совокупности СА вы-
полняется аналогично вышерассмотрен-
ному случаю с тем дополнением, что, с
учетом следствия 2 из теоремы 1 элемен-
тарные Д-операторы выбираются таким
образом, что бы для производных иерар-
хических данных D и D выполняются
соотношения ik DD 1 , ik DD 1 .
Если требуется реализовать опера-
цию алгебры, то эта операция записывает-
ся с использованием элементарных
Д-операторов и предиката. Последний (в
случае необходимости), предварительно
записывается, в соответствии со следстви-
ем 3 из теоремы 1, в виде КС
)()(...)()( э
1
э
1 skskkk PDPD
).()( 1 PDik
Полученная таким образом опера-
ция алгебры записывается, в соответствии
с (1) или (2), в виде соответствующего
Д-оператора.
Применяя описанный выше подход
ко всем производным Д-операторам, пе-
реходим на более высокий уровень опи-
сания алгоритма, на котором каждый из
Д-операторов записывается в виде
)()(...)()( 111111111 skskskkkk DODDOD
).()( 222 ikikik DOD
Процесс проектирования продолжа-
ется с использованием производных
Д-операторов аналогично и приводит к
получению все более укрупненного описа-
ния алгоритма. В случае проектирования
от управления, этот процесс завершится
построением СА
)()(...)()( 111111111 kkk DODDOD
).()( DAD
Поскольку по условию теоремы ал-
гебра данных полна, то, в соответствии с
леммой 2, в результате укрупнения иерар-
хических данных будут получены иD и
иD , а процесс проектирования от данных
завершится построением Д-оператора
)()( DAD такого, что DD и
и DD и .
Если во всех рассмотренных случа-
ях осуществить свертку СА (последова-
тельно подставить элементарные
Д-операторы во все схемы снизу вверх),
то, при условии выполнения предположе-
ний, которые делались в процессе проек-
тирования, будет получена последователь-
ность элементарных Д-операторов, сово-
купная функциональность которой по по-
строению обеспечивает решение требуе-
мой задачи, а при разработке от данных –
решение задачи с учетом структуры
иерархических данных.
Поскольку достаточно произвольно
осуществляется декомпозиция и объеди-
Теоретичні та методологічні основи програмування
12
нение Д-операторов, выбор элементарных
Д-операторов и данных, то во всех рас-
смотренных случаях возможна ситуация,
когда сделанные предположения не вы-
полнятся. В такой ситуации осуществляет-
ся корректировка полученных результатов,
начиная с любого шага проектирования.
Так как по условиям теоремы мно-
жество эX конечно и достаточно для реа-
лизации функциональности произвольного
алгоритма, а для всех элементарных дан-
ных эээ , SDD ii в множестве ЭX
найдутся Д-операторы )()( э DОD такие,
что DDi э
и/или DDi э , то во всех
рассмотренных случаях в результате ко-
нечного числа корректировок искомый ре-
зультат будет получен. При этом, посколь-
ку по условию теоремы алгебра логики
полна (доказательство полноты приведено,
например, в работе [6]), то в процессе про-
ектирования реализуемы любые логиче-
ские условия.
Таким образом, показана реализуе-
мость разработки произвольного алгорит-
ма )()( DAD от управления и от данных в
рамках как нисходящей, так и восходящей
стратегий проектирования.
При этом, в соответствии с опреде-
лением 6, функциональность элементар-
ных Д-операторов задана и согласована с
обрабатываемыми данными. В соответ-
ствии с этим и следствием 1 из теоремы 1,
при восходящем проектировании функци-
ональность каждого Д-оператора
)()( 111 ikikik DOD будет задана и согла-
сована с обрабатываемыми данными. Так
как это свойство сохранится на всех вы-
шележащих уровнях проектирования, то
функциональность получаемых на каждом
из них Д-операторов (включая )()( DAD ),
будет согласована с обрабатываемыми
данными.
Легко увидеть, что применение
следствия 1 из теоремы 1 к СА, получен-
ным в случае нисходящего проектирова-
ния, на нижнем и всех последующих уров-
нях описания алгоритма приведет к такому
же результату.
Теорема доказана.
Выводы
Показана возможность проектиро-
вания в рамках алгебры алгоритмов с дан-
ными произвольного алгоритма )()( DAD
от управления и от данных, как с исполь-
зованием нисходящей, так и восходящей
стратегий. При этом предложенная алгебра
обеспечивает в проектируемом алгоритме
согласованность потоков управления и об-
рабатываемых данных на всех этапах раз-
работки. Из доказанной теоремы 3 легко
увидеть, что рассмотренные стратегии и
подходы к проектированию могут исполь-
зоваться совместно. Возможность автома-
тизированного проектирования алгорит-
мов средствами интегрированного ин-
струментария проектирования и синтеза
программ продемонстрирована в рабо-
те [9].
1. Вирт Н. Алгоритмы + структуры данных =
программы : перев. с англ. М.: Мир,
1985. 656 с.
2. Турский В. Методология программирова-
ния: пер. с англ. – М.: Мир, 1981. 264 с.
3. Замулин А.В. Формальные методы специ-
фикации программ. – Новосибирск: Ново-
сибирский государственный университет,
1999. – 97 с.
4. Акуловский В.Г. Алгебра алгоритмов, бази-
рующаяся на данных // Кибернетика и си-
стемный анализ. – 2012. – № 2. –
С. 151–166.
5. Глушков В.М., Цейтлин Г. E., Ющенко Е.Л.
Алгебра. Языки. Программирование. 3-е
изд., перераб. и доп. – К.: Наукова думка,
1989. – 376 с.
6. Цейтлин Г.Е. Введение в алгоритмику. –
К.: Сфера, 1998. – 310 с.
7. Дорошенко А.Ю., Акуловський В.Г. Вис-
хідне проектування алгоритмів при алгеб-
роалгоритмічному підході // Вісник
Київського національного університету
імені Тараса Шевченка. Серія фізико-
математичні науки. – 2012. – Вип. 1. –
С. 167–172.
8. Дорошенко А.Е., Акуловский В.Г. Нисхо-
дящее проектирование алгоритмов в рам-
ках алгеброалгоритмического подхода //
Математичні машини і системи. – 2012. –
№ 3. – С. 97–102.
Теоретичні та методологічні основи програмування
13
9. Акуловский В.Г., Дорошенко А.Е., Яцен-
ко Е.А. Реализация средств проектирова-
ния и генерации программ на основе ал-
гебры алгоритмов с данными // Проблеми
програмування. – 2015. – № 2. –
С. 41–51.
References
1. Wirth, N. (1985) Algorithms + Data
Structures = Programs. Moscow: Mir. (in
Russian)
2. Turski, W. (1981) Methodology of
programming. Moscow: Mir. (in Russian)
3. Zamulin, A.V. (1999) Formal methods of
program specification. Novosibirsk:
Novosibirsk State University. (in Russian)
4. Akulovskiy, V.G. (2012) Data based
algorithmic algebra. Cybernetics and systems
analysis. (2). P. 151–166. (in Russian)
5. Glushkov, V.M., Tseitlin, G.E. &
Yushchenko, E.L. (1989) Algebra. Languages.
Programming. 3rd edition. Kiev: Naukova
dumka. (in Russian)
6. Tseitlin, G.E. (1998) Introduction to
algorithmics. Kiev: Sfera. (in Russian)
7. Doroshenko, A.Yu. & Akulovskiy, V.G.
(2012) The bottom-up design of algorithms at
algebra-algorithmic approach. Bulletin of
Taras Shevchenko National University of
Kyiv. Series Physics & Mathematics. (1).
P. 167–172. (in Ukrainian)
8. Doroshenko, A.Yu. & Akulovskiy, V.G.
(2012) The top-down design of algorithms at
algebra-algorithmic approach. Mathematical
machines and systems. (3). P. 97–102. (in
Russian)
9. Akulovskiy, V.G., Doroshenko, А.Yu. &
Yatsenko, O.A. (2015) Implementation of
tools for designing and generating of
programs on the basis of algebra of algorithms
with data. Problems in programming. (2).
P. 41–51. (in Russian)
Получено 21.09.2016
Об авторах:
Акуловский Валерий Григорьевич
кандидат технических наук, доцент
кафедры информационных систем и
технологий Академии таможенной
службы Украины.
Количество научных публикаций в
украинских изданиях – более 30.
Количество научных публикаций в
зарубежных изданиях – 4.
Индекс Хирша – 4.
http://orcid.org/0000-0001-6180-0763,
Дорошенко Анатолий Ефимович,
доктор физико-математических наук,
профессор, заведующий отделом теории
компьютерных вычислений Института
программных систем НАН Украины,
профессор кафедры автоматики и
управления в технических системах
НТУУ “КПИ”.
Количество научных публикаций в
украинских изданиях – более 150.
Количество научных публикаций в
зарубежных изданиях – более 30.
Индекс Хирша – 3.
http://orcid.org /0000-0002-8435-1451,
Яценко Елена Анатольевна,
кандидат физико-математических наук,
старший научный сотрудник Института
программных систем НАН Украины.
Количество научных публикаций в
украинских изданиях – 30.
Количество научных публикаций в
иностранных изданиях – 14.
http://orcid.org/0000-0002-4700-6704.
Место работы авторов:
Академия таможенной службы Украины.
49000, Днепропетровск,
ул. Дзержинского, 2/4.
E-mail: valeryakulovskiy@rambler.ru
Институт программных систем
НАН Украины. 03187, Киев,
проспект Академика Глушкова, 40.
Тел.: (044) 526 3559.
E-mail: doroshenkoanatoliy2@gmail.com,
oayat@ukr.net
|