Some approaches to the control and transformation of algorithms over the analysis of the data which are specified
The approaches to the control of a correctness of algorithms, over the analysis of the data which are specified also approaches to optimization of consecutive algorithms as a result of transformation of streams of the data are offered.Problems in programming 2008; 4: 84-93
Gespeichert in:
| Datum: | 2026 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2026
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1018 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| _version_ | 1868747441726029824 |
|---|---|
| author | Akulovsky, V.G. |
| author_facet | Akulovsky, V.G. |
| author_institution_txt_mv | [
{
"author": "V.G. Akulovsky",
"institution": "Academy of Customs Service of Ukraine"
}
] |
| author_sort | Akulovsky, V.G. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2026-06-22T16:37:55Z |
| description | The approaches to the control of a correctness of algorithms, over the analysis of the data which are specified also approaches to optimization of consecutive algorithms as a result of transformation of streams of the data are offered.Problems in programming 2008; 4: 84-93 |
| first_indexed | 2026-06-23T01:00:38Z |
| format | Article |
| fulltext |
Інструментальні засоби і середовища програмування
© В.Г. Акуловский, 2008
84 ISSN 1727-4907. Проблеми програмування. 2008. № 4
УДК 519.683
В.Г. Акуловский
НЕКОТОРЫЕ ПОДХОДЫ К КОНТРОЛЮ И ПРЕОБРАЗОВАНИЮ
АЛГОРИТМОВ НА ОСНОВЕ АНАЛИЗА СПЕЦИФИЦИРУЕМЫХ
ДАННЫХ
Предложены подходы к контролю корректности алгоритмов на основе анализа специфицируемых дан-
ных и подходы к оптимизации последовательных алгоритмов в результате преобразования потоков
данных.
Роль данных в процессе разработки
алгоритмов и программ чрезвычайно вы-
сока, что подтверждается, например, сле-
дующей цитатой [1]: “Хотя операции и
данные, эти активные и пассивные про-
граммные компоненты, играют совер-
шенно различные роли в каждой конкрет-
ной программе, совершенно невозможно
рассматривать одни в отрыве от других”.
Необходимость совместной разработки
потоков управления и данных давно осоз-
нана программистским сообществом. Это
осознание нашло свое выражение в боль-
шинстве методологий программирования,
в которых используются специальные
средства для описания данных. В боль-
шинстве случаев, однако, это описание,
выполненное в графической форме, пред-
ставляет собой отдельный документ в па-
кете документов, сопровождающих разра-
ботку. Это, очевидно, может служить ис-
точником ошибок, связанных с неадекват-
ностью различных документов, что осо-
бенно вероятно при большом их объеме.
В данной работе будем рассматри-
вать совместно (в рамках единого фор-
мального аппарата) потоки управления и
данных и на основании этого подхода ре-
шать некоторые аспекты задач построения,
контроля корректности и преобразования
алгоритмов. Для этого воспользуемся рас-
ширенной алгеброй алгоритмов (САА-Р)
[2], которая является одним из направ-
лений развития известной алгебры алго-
ритмов Глушкова [3], и результатами, по-
лученными в [4], где выполнена формали-
зация взаимосвязи операторов и данных и
предусмотрена возможность специфика-
ции данных для каждого оператора.
Используемый формальный аппарат
представляет собой систему алгоритмиче-
ских алгебр – ΩΩΩΩ,L,U , где U – множе-
ство операторов, L – множество логиче-
ских условий, Ω – сигнатура операций,
состоящая из логических операций – 1ΩΩΩΩ ,
принимающих значения на множестве L и
операций – 2ΩΩΩΩ , принимающих значения
на множестве операторов U . Операции
множества 2ΩΩΩΩ это * – композиция (после-
довательное выполнение операторов),
3
α
– дизъюнкция (разветвление вычислитель-
ного процесса по трем направлениям),
α − итерация (цикл, соответствует про-
граммной конструкции WHILE) и их про-
изводные.
Известно, что основным подходом к
разработке алгоритмов является его де-
композиция, осуществляемая с пониже-
нием уровня абстракции на каждом оче-
редном этапе разработки. Этот подход
реализован в виде метода структурного
проектирования программ (МСПП) [5],
формальной основой которого является
алгебра алгоритмов.
Поскольку САА-Р, являющаяся
средством, определяющим потоки управ-
ления, расширена за счет введения в рас-
смотрение данных, то в рамках МСПП
будем анализировать возможности по-
строения алгоритма с учетом общих
свойств данных, обрабатываемых этим
алгоритмом. Под контролем корректности
алгоритма будем понимать контроль огра-
ничений, налагаемых на специфицируемые
данные.
В связи с тем, что в данной работе
мы коснемся только некоторых аспектов и
Інструментальні засоби і середовища програмування
85
этапов разработки алгоритмов, будем при
его построении использовать только одну
из возможных операций САА-Р – компо-
зицию, подразумевая, что любой оператор,
образующий алгоритм, может представ-
лять собой и/или содержать любые опера-
ций САА-Р.
1. Проектирование структуры и кон-
троль корректности алгоритма
Прежде, чем рассматривать струк-
туру алгоритмов, определим основные ис-
пользуемые далее понятия.
Самым общим случаем оператора
алгебры будем считать алгоритм решения
задачи (в дальнейшем алгоритм), который
определим таким образом.
Определение 1. Произвольным
алгоритмом назовем оператор U∈ΑΑΑΑ , ко-
торый запишем в виде
)Δ()Δ( ′′′ ΑΑΑΑ , (1)
где ∆∆∆∆′ – спецификация данных, образую-
щих область определения, ∆∆∆∆ ′′ –
спецификация данных, образующих об-
ласть значений оператора, ∆∆∆∆∆∆∆∆∆∆∆∆ ′′∪′= –
множество всех данных, доступных алго-
ритму, которое является его информаци-
онным множеством. Область определения
будем называть входными, а область зна-
чений выходными данными. Будем гово-
рить, что в результате выполнения алго-
ритма, решается некоторая задача, а вы-
числитель переходит из состояния ∆∆∆∆′ в
состояние ∆∆∆∆ ′′ .
Поскольку вычислитель не в со-
стоянии выполнить переход из состояния
∆∆∆∆′ в состояние ∆∆∆∆ ′′ за один “шаг”, то его
(этот переход) необходимо реализовать в
виде некоторого количества элементар-
ных, выполняемых вычислителем “шагов”,
т.е. записать алгоритм в виде программы
на некотором языке программирования.
Для получения программы, адек-
ватной исходному алгоритму, необходимо
осуществлять его поэтапную (поуровне-
вую) декомпозицию, т.е. необходимо
представить его в виде уровней со множе-
ством связанных и согласованных компо-
нентов (модулей) на каждом из них. При
чём степень абстрактности (детализации)
на каждом следующем уровне декомпози-
ции необходимо понижать (повышать).
В качестве вышеупомянутых ком-
понент будем использовать операторы
САА-Р, которые в данном случае опреде-
лим следующим образом.
Определение 2. Операторы, с по-
мощью которых строится алгоритм, это
операторы вида:
U)D(A)D( ∈′ , (2)
у которых ∆∆∆∆∈D – область определения
(входные данные), а ∆∆∆∆∈′D – область его
значений (выходные данные). Эти опера-
торы обрабатывают некоторое подмноже-
ство входных данных ∆∆∆∆⊂D , изменяют их
и порождают новые данные, формируя та-
ким образом подмножество выходных
данных ∆∆∆∆⊂′D . Для множеств D иD ′ вы-
полнимо любое из следующих соотноше-
ний: ,DD,DD ⊆′′⊆ ∅=′∩ DD .
С целью повышения строгости из-
ложения приведем следующую аксиому.
Аксиома 1. Любой алгоритм и лю-
бой входящий в него оператор (за исклю-
чением элементарных) может быть пред-
ставлен в виде композиции (последова-
тельности) двух (или более) операторов
)D
~
(A)D
~
(*)D̂(A)D̂()D(D)A( ′′′′′=′ , для кото-
рых выполняются такие соотношения:
D
~
D̂D ∪= , D
~
D̂D ′∪′=′ .
Очевидно, существование подоб-
ной аксиомы подразумевалось при созда-
нии различных методов и методологий
программирования, основанных на де-
композиции алгоритмов. Однако, на-
сколько известно автору, в явном виде она
не формулировалась.
Запись оператора в форме, приве-
денной в аксиоме 1, будем называть ре-
гулярной схемой (РС). Оператор, стоящий
справа от знака равенства – исходным, а
операторы, расположенные слева – произ-
водными.
В соответствии с аксиомой 1, и
расширяя возможности МСПП, будем
согласованно декомпозировать операторы
и обрабатываемые ими данные. В резуль-
тате каждого шага декомпозиции получим
новый уровень алгоритма, представляю-
щий собой множество регулярных схем
(РС), каждая из которых описывает один
Інструментальні засоби і середовища програмування
86
из операторов предыдущего уровня. Таким
образом, алгоритм будет представлять
собой суперпозицию операторов.
Алгоритм (1) будем называть нуле-
вым уровнем декомпозиции и будем пола-
гать, что на этом уровне специфицированы
глобальные входные и выходные данные.
При рассмотрении процесса деком-
позиции алгоритма будем анализировать
свойства специфицируемых данных и
формулировать ограничения на их исполь-
зование.
В общем виде (для любого уровня
декомпозиции) любой оператор (2) пред-
ставляет собой РС вида:
),(1)(*...*)()(*
*...*)
1
(1
1
)
1
( )(
1 i
n
Di
n
Ai
n
Di
j
DAi
j
D
iDiAiD)D(AD
i
j
i
m
i
m
i
m
′+′
′+=′
+
(3)
где верхний индекс соответствует номеру
уровня, а нижний идентифицирует опера-
тор внутри РС и обрабатываемые им дан-
ные. Ограничение на обрабатываемые
данные в соответствии с аксиомой 1 для
этого уровня запишем в виде
i
n
D...i
j
D...i
1
D D i
m ∪∪∪∪= , (4)
i
n
D...i
j
D...i
1
D D i
m ′∪∪′∪∪′=′ . (5)
Анализируя данные на выходе не-
которого оператора, можно заметить, что
некоторые из них – промежуточные, т.е. не
влияют на результат решения задачи, спе-
цифицируемой в рамках данной РС, а по-
требуются на следующем шаге декомпози-
ции. И естественным является желание
отложить их спецификацию (уменьшить
объем специфицируемых данных) до того
этапа разработки, на котором эти данные
будут востребованы. Исполнению этого
препятствуют жесткие ограничения ак-
сиомы 1. Для ослабления упомянутого
ограничения разобьем выходные данные
на два подмножества i
i
Dпромi
i
D D i
i ∪′′=′ и
i
i
D ′′ будем называть выходными, а
i
i
Dпром – промежуточными данными.
Для этого случая РС (3) перепишем в
виде
),пром,(1)(*
*...*)пром,()(*...
...*)
1
пром,
1
(1
1
)
1
( )(
1
i
n
Di
n
Di
n
Ai
n
D
i
i
Di
i
DAi
i
D
iDiDiAiD)D(AD
i
i
i
m
i
m
i
m
′′+
′′
′′+=′
+
а ограничение (5) примет вид
i
n
i
j
i
1
i
m D...D...D D ′′∪′′∪′′=′ ∪∪ . (6)
В результате количество специфи-
цируемых для исходного оператора дан-
ных сократится без потерь в полноте спе-
цификации.
Далее определим понятия глобаль-
ных и локальных данных, которые обо-
значим соответственно i
j
лi
j
гл D иD .
Будем полагать, что i
j
глD доступны всем
операторам РС и в выражении (3) специ-
фицированы именно глобальные данные.
Локальные данные i
j
лD локализованы в
рамках каждого оператора, входящего в
РС. На введенные типы данных нало-
жено ограничение
∅=∩ i
j
лi
j
гл D D , (7)
для любых i и j.
Когда на некотором i+1-ом уровне
декомпозиции специфицируются локаль-
ные данные, то выражение (3) необхо-
димо записать в виде
)(1)1л,*(...
(8)...*)()1л,*(
*...*)
1
(1
1
)1
1
л,
1
( )(
гл
1гл
гл
i
n
Di
n
Ai
n
Di
n
D
i
j
DAi
j
Di
j
D
iDiAiDiD)D(AD
гл
глi
j
глi
m
i
m
i
m
′++
′+
′++=′
+
и для данного случая имеет место сле-
дующее ограничение:
∅=++∩+ ∩∩∩ 1i
nDл.1i
jDл1i
1Dл ..... . (9)
Інструментальні засоби і середовища програмування
87
На следующем i+2-ом уровне оператор (8)
будет записан в виде
),1(2)2л,1*(...
...*)1()2л,1*(...
...*)1
1
(2
1
)2
1
л,1
1
(
)()1л,(
гл
2гл
гл
1гл
+′+++
+′++
+′+++=
=′+
+
+
i
n
Di
n
Ai
n
Di
n
D
i
j
DAi
j
Di
j
D
iDiAiDiD
i
j
DAi
j
Di
j
D
гл
глi
j
гл
глi
j
где 1i
j
Di
j
D1i
j
D лглгл +∪=+ , т. е. локальные
на i+1-ом уровне данные рассматриваются
как глобальные на i+2 уровне и для
1i
j
Dгл + выполняется соотношение (4).
Поскольку дальнейшее рассмотре-
ние будет вестись в рамках одной РС, а их
сочетания рассматриваться не будут, упро-
стим систему обозначений, отказавшись от
указания глобальности и локальности дан-
ных и лишней индексации, в тех случаях,
когда в ней нет необходимости.
Для продолжения декомпозиции ал-
горитма будем детализовать спецификации
входных и выходных данных, а РС запи-
шем в виде
)()(*...*)()(*
*...*)
1
(
1
)( )( 1
k
D
k
A
k
D
j
DA
j
D
DAD)DA(D
j ′′
′=′
Представим входные данные в виде
i
D
i
DD присх
i ∪= , где
i
Dисх – исход-
ные, а
i
Dпр – производные данные,
на которые накладывается ограничение
вида:
∅=∩ i
пр
i
исх DD (10)
и которые в исходном состоянии могут
быть как определены (инициализированы),
так и находиться в неопределенном (не-
инициализированном) состоянии. В пос–
леднем случае такие неопределенные
данные должны быть определены в про-
цессе выполнения алгоритма.
i
Dпр - множество производных дан-
ных, которые изменяются в процессе вы-
полнения алгоритма.
Уточняя структуру исходных дан-
ных
i
Dисх , представим его в виде двух
подмножеств
i
D
i
D
i
D иницconstисх ∪= , где
i
Dconst – множество неизменяемых
данных, которые инициируются до начала
выполнения алгоритма и в дальнейшем
остаются неизменными, и все они исполь-
зуются (должны использоваться) в каче-
стве исходных (входных) данных, т.е.
;......
......
1
1
k
D
i
DD
n
D
i
DD constconstconst
∪∪∪∪⊆
⊆∪∪∪∪
i
Dиниц – однократно инициализиру-
ются в процессе выполнения алгоритма и в
дальнейшем остаются неизменными, и все
они используются (должны использо-
ваться) в качестве исходных (входных)
данных, т.е.
.......
......
1
1
иниц
k
D
i
DD
n
D
i
DD инициниц
∪∪∪∪⊆
⊆∪∪∪∪
.
Множество выходных данных пред-
ставим в виде объединения следующих
множеств:
i
DDD иниц
i
пр
i ∪=′ .
Далее введем вспомогательные
множества:
i
вв D – вводимые данные (посту-
пающие с устройств ввода);
i
выв D – выводимые (на внешние
устройства) данные.
Эти множества обладают такими
свойствами:
i
D
i
DD приниц
i
вв ∪⊂ ,
i
D
i
DD i
выв ′∪⊆ .
Учитывая появление этих типов
данных на множестве U выделим два под-
множества операторов, элементами кото-
рых являются U)D(R)(УВВ i
вв
i ∈ – опера-
торы ввода, где УВВ – спецификация уст-
ройства ввода и UWD ii ∈УВыв)()(выв –
операторы вывода, где УВыв – специфи-
кация устройства вывода.
Інструментальні засоби і середовища програмування
88
Теперь на основании приведенных
свойств введем ограничения на использо-
вание построенных множеств.
Для множества
i
Dconst имеют место
такие ограничения:
∅=∩
i
DD const
i
вв , (11)
т.е. вводимые данные не изменяют
констант;
∅=′∪∪′∪∪′∩
∩∪∪∪∪
k
D
i
DD
n
D
i
DD constconstconst
......
......
1
1
,
(12)
т. е. константы не могут выступать в каче-
стве выходных данных.
Для
i
Dиниц имеют место следующие
ограничения:
)D(A)D( ii ′∃ и только один, для
которого выполняется соотношение:
i
иниц D
i
D ′⊆ ; (13)
)D(R)(УВВ i
вв
i∃ и только один, для кото-
рого выполняется соотношение:
i
иницвв D
i
D ⊆ , (14)
т.е., в случаях (13, 14) данные инициали-
зируются однократно.
Для
i
Dпр имеют место следующие
ограничения:
)D(A)D( ii ′∃ по крайней мере один,
для которого выполняется соотношение
i
пр D
i
D ′⊆ (15)
и он предшествует любому другому опе-
ратору для которого выполняется соотно-
шение i
пр D
i
D ⊆ , т.е. использова-
нию данных должна предшествовать их
инициализация.
Приведенные ограничения нахо-
дятся в очевидных соотношениях, некото-
рые из них приведем в качестве примера.
Если
i
DD вв
i
иниц ⊆ , то ограничение
(13) становится не актуальным, а
если
i
DD i
иниц ′⊆ , то не актуально ограниче-
ние (14).
Если
i
DD иниц
i
вв ⊂ , то
∅≠∩
i
DD пр
i
вв .
Если ∅≠∩
i
DD иниц
i
вв , то ограниче-
ние (13) выполняется для множества
i
ввинициниц D/
i
D
i
D̂ = .
Если
i
DD вв
i
пр ⊆ , то ограничение
(15) становится не актуальным.
Если
i
DD пр
i
вв ⊆ , то
∅=∩
i
DD иниц
i
вв .
Если ∅≠∩
i
DD пр
i
вв , то ограниче-
ние (15) выполняется для множества
i
ввпрпр D/
i
D
i
D̂ = и т.д.
В первом разделе работы рассмот-
рена возможность на некоторых этапах
разработки согласовывать процесс деком-
позиции операторов, образующих алго-
ритм, с декомпозицией специфицирован-
ных для этих операторов данных.
В процессе рассмотрения предло-
жены некоторые варианты детализации
данных и выявлены ограничения на их
использование. В случае спецификации
предложенных типов данных на требуе-
мом уровне декомпозиции открывается
возможность проверки соответствия алго-
ритма сформулированным ограничениям
и, таким образом, контроля его корректно-
сти. При этом на начальных этапах контро-
лируются ограничения (4–7, 9), а на после-
дующих, после детализации данных, огра-
ничения (10–15) с учетом связывающих их
соотношений. Заметим, что контроль мо-
жет быть осуществлен как в ручном, так и
в автоматизированном режиме.
2. Преобразование алгоритмов
Структура алгоритма (последова-
тельность выполнения операторов) в су-
щественной мере определяется последова-
тельностью обработки данных и должна
учитывать тип разрабатываемой про-
граммной системы. В данном случае, имея
в виду последовательные алгоритмы, рас-
смотрим потоки управления и определим
потоки данных в алгоритмах.
Будем полагать, что потоки управ-
ления, как вышеотмечено, организуются
операциями САА-Р (в рассматриваемом
случае операцией композиция), и пару
операторов
Інструментальні засоби і середовища програмування
89
)
1i
D(A)
1i
D(*)
i
D(
i
A)D( 1ii +′+′ + , будем
называть непосредственно, а
)
k
D(
k
A)
k
D(*...*)
j
D(A)
j
D(*... j ′′ , где
k > j опосредованно связанными по
управлению.
Понятие поток данных, определим
следующим образом.
Определение 3. Поток данных – это
такое множество данных D , которое дос-
тупно (специфицировано на входе) неко-
торому оператору iA и оно же после обра-
ботки этим оператором (специфицировано
на его выходе) становится доступно неко-
торому оператору jA (i < j) и т. д., т. е.
множество данных D трансформируется в
процессе обработки последовательностью
операторов, в рамках РС. Будем говорить,
что данные с выхода предшествующего
оператора подаются на вход последую-
щего и/или последующих операторов.
Заметим, что поток данных в после-
довательном алгоритме носит виртуаль-
ный характер, однако такая абстракция
оказывается весьма удобной при совмест-
ном рассмотрении потоков управления и
обрабатываемых этим потоком данных.
Требование к потокам данных в по-
следовательных алгоритмах, удовлетворе-
ние которого обеспечит более высокое
качество, а именно более высокий уровень
понятности и отлаживаемости алгоритма
(программы), сформулируем следующим
образом.
Количество потоков данных на лю-
бом уровне декомпозиции и в любой РС
должно быть минимальным. Очевидно, что
оптимальным, но крайне редко реализуе-
мым, является алгоритм с единственным
потоком данных.
В этом разделе будем решать задачу
преобразования РС, с целью удовлетво-
рения сформулированного требования и
докажем возможность такого преобразо-
вания при некоторых ограничениях. Для
решения этой задачи, воспользовавшись
результатами, полученными в [4], и разви-
вая их, введем понятие независимых по
данным и связанных данными операторов.
Будем различать “прямые” и “об-
ратные” связи по данным и прямую связь
определим так.
Определение 4. В регулярной схе-
ме вида
)()(*...*)()(*
*...*)
1
(
1
)( )( 1
k
D
k
A
k
D
j
DA
j
D
DAD)DA(D
j ′′
′=′
операторы )
j
D(A)
j
D( и)
i
D(
i
A)D( ji ′′ ,
где i < j прямо связаны по данным (в
дальнейшем прямо связаны), если они не-
посредственно или опосредованно свя-
заны по управлению и для них выполня-
ется следующее соотношение:
∅≠∩′ ji DD , т. е. область значений
оператора )
i
D(
i
A)D( i ′ пересекается с
областью определения оператора
)
j
D(A)
j
D( j ′ . При наличии такой связи
оператор )
i
D(
i
A)D( i ′ всегда должен
предшествовать оператору )
j
D(A)
j
D( j ′ .
Под длиной прямых связей (рас-
стоянием между прямо связанными опера-
торами) будем понимать количество опе-
раторов, разделяющих связанные опера-
торы и, таким образом, длина связи, кото-
рую обозначим d, вычисляется по формуле
d = j – i – 1.
Особого рассмотрения заслуживает
случай, когда длина связи d = 0, т. е. слу-
чай, когда операторы непосредственно
связаны по управлению. Для этого случая
введем следующее определение.
Определение 5. Любые два опера-
тора )
j
D(A)
j
D( и)
i
D(
i
A)D( ji ′′ назо-
вем непосредственно связанными по
данным (в дальнейшем непосредственно
связанными), если ∅≠∩′ ji DD , а
расстояние между ними равно нулю, т. е.
j = i + 1. Непосредственная связь опреде-
ляет жестко заданную последовательность
обработки данных и эта последователь-
ность выполнения операторов не может
быть изменена.
Інструментальні засоби і середовища програмування
90
Теперь определим обратную связь.
Определение 6. Между любыми
операторами
)
j
D(A)
j
D( и)
i
D(
i
A)D( ji ′′ присутст-
вуют обратные связи, трех видов, опре-
деляемые следующими соотношениями:
1) ∅≠∩
j
DD i , 2) ∅≠′∩
j
DD i ,
3) ∅≠′∩′
j
D
i
D , которые могут
присутствовать в любом сочетании.
На этом основании введем ещё не-
сколько производных понятий, которыми
воспользуемся в дальнейшем.
Определение 7. Многосвязным
назовем оператор, который прямо связан
(см. определение 4) с несколькими дру-
гими операторами, при наличии или в от-
сутствии непосредственной связи
(см. определение 5).
Определение 8. Независимыми по
данным (в дальнейшем независимыми)
назовем любые два непосредственно свя-
занных по управлению оператора
)D̂(B)D̂(*)DA()D( ′′ , если для них выпол-
няются следующие ограничения:
∅=∩ D̂D , ∅=′∩ D̂D , ∅=∩′ D̂D ,
∅=′∩′ D̂D . Очевидно, что для них вы-
полняется тождественное соотношение:
)DA()D(*)D̂(B)D̂()D̂(B)D̂(*)DA()D( ′′=′′ .
Определение 9. Полностью неза-
висимым назовем оператор, если он неза-
висим от любого оператора входящего в
РС, и таким образом он может распола-
гаться в любом месте РС.
Прежде чем рассматривать воз-
можные преобразования алгоритмов, вве-
дем ещё одну аксиому, по аналогии ак-
сиомы 1.
Аксиома 2. Любая пара операторов
непосредственно связанная по управлению
(операцией композиции) может рассмат-
риваться, как новый опера-
тор ))
~~
*ˆˆ D(D)A(D(A)D()D(A)D( ′=′′′′′ , для
которых выполняются соотношения
D
~
D̂D ∪= и D
~
D̂D ′∪′=′ .
Приведенные в работе аксиомы –
базовые и универсальные средства преоб-
разования алгоритмов, так как позволяют
создавать новые операторы за счет раз-
биения и объединения существующих. В
частности, возможно сокращение количе-
ства прямых связей в многосвязных опе-
раторах (см. определение 7) за счет раз-
биения такого оператора на несколько
других операторов с меньшим числом
прямых связей. Однако возможность из-
менения порядка следования операторов в
них не предусмотрена.
Для того, что бы с целью преобра-
зования алгоритмов иметь возможность
менять порядок следования операторов в
РС, рассмотрим непосредственно свя-
занные операторы и ослабим жесткое ог-
раничение, заданное определением 5. Для
этого рассмотрим возможные случаи пре-
образования операторов
)D̂(B)D̂(*)DA()D( ′′ , (16)
когда для них выполняются следующие
соотношения.
1. Рассмотрим общий слу-
чай непосредственной связи, когда вы-
полняется DD̂D
)
=∩′ , т. е. область значе-
ний оператора )DA()D( ′ пересекается с
областью определения оператора
)D̂(B)D̂( ′ . Для даного случая выполним
такую последовательность действий.
Оператор )DA()D( ′ представим (в
соответствии с аксиомой 1) в виде двух
операторов
)D(A)D(*)D(A)D()DA()D( 222111 ′′=′ , где
∅=∩′ 21 DD , ∅≠∩′ D̂D2 . В свою оче-
редь оператор )D̂(B)D̂( ′ представим в
виде )D̂(B)D̂(*)D̂(B)D̂()D̂(B)D̂( 222111 ′′=′ ,
таким образом, что ∅=∩′ 21 D̂D̂ ,
∅≠′∩ 2D1D̂ . В результате преобразова-
ния получены два непосредственно не
связанных оператора )D(A)D( 111 ′ ,
)D̂(B)D̂( 222 ′ и два непосредственно
связанных оператора )D(A)D( 222 ′ ,
)D̂(B)D̂( 111 ′ . Объединив последние, в
соответствии с аксиомой 2, получим три
непосредственно не связанных оператора,
т. е.
)ˆ()ˆ(*)
~
()
~
(*
*)()()ˆ()ˆ(*)(
222
111
DBDDABD
DADDBD)DA(D
′′
′=′′
,
(17)
Інструментальні засоби і середовища програмування
91
для которых выполняется ∅=∩′ D
~
D1 и
∅=∩′ 2D̂D
~
.
Далее рассмотрим частные случаи
непосредственной связи операторов, вы-
полняя аналогичные преобразования.
2. Когда DD̂ ′⊂ , последова-
тельность операторов (16) преобразуем с
виду
),()(*)(
)ˆ()ˆ(*)(
222 DBD)DAB(D
DBD)DA(D
′′′′′′=
=′′
(18)
где ∅=∩′′′ 2DD .
3. В случае, когда D̂D ⊂′ , последо-
вательность операторов (16) преобразуем
к виду:
),
~
()
~
(*)(
)ˆ()ˆ(*)(
111 DABD)D(AD
DBD)DA(D
′′
=′′
(19)
где ∅=∩′ D
~
D1 .
4. Когда DD̂ ′= , (20)
преобразование с точки зрения непосред-
ственной связи невозможно. В
результате нами рассмотренной возмож-
ности выделения непосредственно не свя-
занных операторов, проанализируем воз-
можные обратные связи между операто-
рами )D̂(B)D̂(*)DA()D( ′′ непосредственно
связанными по управлению и непосредст-
венно не связанными по данным. Для
этого рассмотрим все возможные варианты
всех видов обратных связей (см. опреде-
ление 6):
1. D̂D = 2. D̂D ′= 3. D̂D ′=′
D̂D ⊂ D̂D ′⊂ D̂D ′⊂′
DD̂ ⊂ D̂D
~ ⊂′ DD̂ ′⊂′
∅=∩ D̂D ∅=′∩ D̂D ∅=′∩′ D̂D
Из приведенных соотношений легко
увидеть, что во всех случаях и во всех
возможных сочетаниях этих случаев (за
исключением одного) операторы полно-
стью или частично совместно (в два этапа)
обрабатывают данные. Иначе, два опера-
тора решают единую задачу (связанные
задачи) обработки данных.
Исходя из вышеизложенного, сле-
дует вывод.
Последовательность двух операто-
ров, имеющая обратные (обратную) и не
имеющая непосредственную связь некор-
ректна (по крайней мере, неэффективна),
так как в этом случае необоснованно “раз-
рывается” поток данных (см. определение
3). В единственном случае отсутствие не-
посредственной связи оправдано, когда
выполняются три условия ∅=∩ D̂D ,
∅=′∩ D̂D , ∅=′∩′ D̂D , в результате
выполнения которых в соответствии с оп-
ределением 8 получаем независимые опе-
раторы.
Учитывая этот вывод очевидно, что
рассмотренные случаи преобразования
операторов (17–19), с целью устранения
непосредственной связи, имеет практиче-
ский смысл только в том случае, когда в
результате такого преобразования полу-
чены независимые операторы. То есть на
преобразования (17–19), накладывается
достаточно жесткое ограничение, при
удовлетворении которого, однако, можно
выбирать произвольную
последовательность выполнения этих
операторов. Заметим, что в случае (20)
пара операторов очевидно должна быть
преобразована в один.
Уточняя выше сформулированное
требование к последовательному алго-
ритму, можно сказать, с учетом приведен-
ных определений, что в РС должно быть
минимальное количество прямых связей.
Докажем возможность таких преобразова-
ний РС, в результате которых число пря-
мых связей будет уменьшено.
Теорема. В любой регулярной
схеме алгоритма, состоящей из трех или
более операторов, связанных
непосредственными и прямыми связями,
количество прямых связей может быть
сокращено за счет их преобразования в
непосредственные связи.
Доказательство. Рассмотрим
тройку операторов
)D̂(C)D̂(*)D(B)D()*DA()D( ′′′
))
, со всеми
возможными в такой тройке прямыми и
непосредственными связями. Для нагляд-
ности и краткости изложения представим
эти связи и возможные результаты преоб-
разования этой последовательности опе-
Інструментальні засоби і середовища програмування
92
раторов в таблице, с указанием использо-
ванных случаев преобразования. При этом
будем использовать упрощенную систему
обозначений, где прямые стрелки указы-
вают непосредственные связи как по
управлению, так и по данным, дугами
прямые связи, а “*” – непосредственные
связи по управлению. Опустим так же
спецификации данных.
Таблица
а AB → C
б A1 *AB → C (16)
в B2* AB → C (15)
1
A → B
* C
г A1 * B2 * AB → C (14)
а A → BC
б A → BC * B1 (16)
В A → BC *C2 (15)
2
A * B
→ C
Г A → BC * B1 * C2 (14)
А A → BC
Б AB → C
В A1 * AB → C (16)
Г A → BC * B1 (16)
д B2 * AB → C (15)
е A → BC * C2 (15)
ж A1 * B2 * AB → C (14)
3
A → B
→ C
з A → BC * B1 * C2 (14)
Из приведенной таблицы видно,
что для каждого возможного случая связи
между операторами в результате исполь-
зования аксиомы 2 и соотношений (17–19)
(в случае, когда такие преобразования
возможны, и вышеприведенное ограни-
чение удовлетворяется) получены ре-
зультаты преобразований, в которых пря-
мые связи преобразованы в непосредст-
венные и, таким образом число прямых
связей сокращено. Отметим, что в случае
получения в результате преобразования
полностью независимого оператора (см.
определение 9), приведенные соотноше-
ния так же выполняются.
Возьмём случай, когда количество
операторов в РС больше трёх и/или новые
операторы получены в результате преоб-
разований, в частности, в результате раз-
биения многосвязных операторов. В этом
случае при условии выполнения требова-
ния по наличию непосредственных и пря-
мых связей, все возможные сочетания,
приведены в таблице, всегда можно вы-
брать тройку операторов, к которым
применимы какие-либо из предлагаемых
преобразований. В результате реализации
выбранных способов преобразования ко-
личество прямых связей будет сокращено
(заменено непосредственными связями).
Теорема, таким образом, доказана.
Описанный в данной работе под-
ход, который намечает пути и возможно-
сти преобразования алгоритма, не предла-
гает конкретных решений. В частности
разбиение, объединение и построение но-
вых операторов, а так же выбор способов
преобразования их последовательностей,
существенно зависит от решаемой алго-
ритмом задачи и требует творческого под-
хода.
Заключение
В предлагаемой работе предложен
подход к построению и контролю алго-
ритмов на основании анализа, и детализа-
ции специфицируемых данных. В частно-
сти, сформулированы свойства и ограни-
чения на используемые данные, проверка
которых и является средством контроля.
Полнота предлагаемой формы контроля
зависит от полноты набора ограничений на
обработку данных и дальнейшая детализа-
ция данных, очевидно, позволит расши-
рить представленный набор.
Отметим, что в данной работе не
рассмотрена ситуация, когда глобальные
или локальные данные одного из уровней
декомпозиции могут быть востребованы на
другом уровне. И хотя такая ситуация яв-
ляется нежелательной, что отмечалось
многими авторами (например [1]) и её
следует избегать, тем не менее такая мето-
дологическая проблема существует. Рас-
смотрение этой самостоятельной задачи
автор намерен осуществить в дальнейшем.
Інструментальні засоби і середовища програмування
93
Во втором разделе определено по-
нятие потоков данных в последователь-
ных алгоритмах. Определены различные
виды связей в операторах, образующих РС,
и предложен подход к преобразованию
алгоритмов на основе введенных аксиом и
преобразования непосредственно связан-
ных операторов. Доказана возможность
сокращения количества прямых связей в
последовательных алгоритмах.
Дальнейшее развитие данного
подхода может состоять в анализе других
типов связей и построении методов
преобразования алгоритмов на основе
такого анализа.
Перспективным представляется ис-
пользование потоков данных при построе-
нии и преобразовании параллельных алго-
ритмов. Однако, с этими алгоритмами дело
обстоит существенно сложнее, так как
требуемая степень их параллелизма опре-
деляется не только решаемой задачей, а
возможностями, ограничениями аппарат-
ной и операционной среды.
На основании результатов, полу-
ченных в данной работе можно сформули-
ровать только некоторые соображения. В
частности, в том случае, когда в процессе
разработки получен полностью независи-
мый оператор (см. определение 9), то он
естественно может выполняться парал-
лельно (псевдопараллельно) с любым дру-
гим оператором РС, которой он принадле-
жит, и в этом случае не требуются допол-
нительные усилия для распараллеливания
алгоритма. Независимый оператор может
выполняться параллельно с соседним, но
при этом потребуется их синхронизовать
по управлению. Для связанных операторов
параллельное выполнение сопряжено с
синхронизацией по совместно обрабаты-
ваемым данным. Несмотря на то, что за-
дача разработки и преобразования парал-
лельных алгоритмов в данной работе не
решалась, тем не менее, с точки зрения
автора, предложенный подход с использо-
ванием потоков данных является перспек-
тивным для решения названной задачи. И
это является ещё одним направлением раз-
вития полученных результатов.
1. Турский В. Методология программирова-
ния. – М.: Мир, 1981. 264 с.
2. Акуловский В.Г. Расширенная алгебра
алгоритмов//Проблеми програмування.-
2007. – № 3. С. 3–15.
3. Андон Ф.И., Дорошенко А.Е., Цейт-
лин Г.Е., Яценко Е.А. Алгеброалгорит-
мические модели и методы параллельного
программирования. – Киев: Академпері-
одика, 2007. – 634 с.
4. Акуловский В.Г. Формализация взаимосвя-
зей операторов и данных в рамках
расширенной алгебры алгоритмов //
Кибернетика и системный анализ. – 2008.
– № 6.
5. Цейтлин Г.Е., Бакулин А.В. Многоуровне-
вые структурированные проекты про-
грамм и их обоснование // Кибернетика и
системный анализ. – 1991. – № 5. –
С. 98–107.
Получено 03.10.2008
Об авторе:
Акуловский Валерий Григорьевич,
кандидат технических наук, доцент ка-
федры информационных систем и техно-
логий
Тел. 8 050 941 0566;
e-mail: valeryakulovskiy@rambler.ru
Место работы автора:
Академия таможенной службы Украины.
49000, Днепропетровск,
ул. Дзержинского 2\4.
Тел/Факс: (056) 745 5596, (0562) 471791.
e-mail: academy@amsu.dp.u
|
| id | pp_isofts_kiev_ua-article-1018 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2026-06-23T01:00:38Z |
| publishDate | 2026 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/55/e1096d5208d2610fec398d447187ef55.pdf |
| spelling | pp_isofts_kiev_ua-article-10182026-06-22T16:37:55Z Some approaches to the control and transformation of algorithms over the analysis of the data which are specified Некоторые подходы к контролю и преобразованию алгоритмов на основе анализа специфицируемых данных Деякі підходи до контролю й перетворення алгоритмів на основі аналізу даних, що специфікуються Akulovsky, V.G. UDC 519.683 УДК 519.683 УДК 519.683 The approaches to the control of a correctness of algorithms, over the analysis of the data which are specified also approaches to optimization of consecutive algorithms as a result of transformation of streams of the data are offered.Problems in programming 2008; 4: 84-93 Предложены подходы к контролю корректности алгоритмов на основе анализа специфицируемых данных и подходы к оптимизации последовательных алгоритмов в результате преобразования потоков данных.Problems in programming 2008; 4: 84-93 Запропоновано підходи до контролю коректності алгоритмів на підставі аналізу даних, що специфікуються і підходи до оптимізації послідовних алгоритмів у результаті перетворення потоків даних.Problems in programming 2008; 4: 84-93 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2026-06-22 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1018 PROBLEMS IN PROGRAMMING; No 4 (2008); 84-93 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2008); 84-93 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2008); 84-93 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1018/1086 Copyright (c) 2026 PROBLEMS IN PROGRAMMING |
| spellingShingle | UDC 519.683 Akulovsky, V.G. Some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| title | Some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| title_alt | Некоторые подходы к контролю и преобразованию алгоритмов на основе анализа специфицируемых данных Деякі підходи до контролю й перетворення алгоритмів на основі аналізу даних, що специфікуються |
| title_full | Some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| title_fullStr | Some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| title_full_unstemmed | Some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| title_short | Some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| title_sort | some approaches to the control and transformation of algorithms over the analysis of the data which are specified |
| topic | UDC 519.683 |
| topic_facet | UDC 519.683 УДК 519.683 УДК 519.683 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/1018 |
| work_keys_str_mv | AT akulovskyvg someapproachestothecontrolandtransformationofalgorithmsovertheanalysisofthedatawhicharespecified AT akulovskyvg nekotoryepodhodykkontrolûipreobrazovaniûalgoritmovnaosnoveanalizaspecificiruemyhdannyh AT akulovskyvg deâkípídhodidokontrolûjperetvorennâalgoritmívnaosnovíanalízudanihŝospecifíkuûtʹsâ |