Некоторые аспекты формализации архитектурного этапа разработки алгоритмов
Предложен подход к формализации некоторых аспектов архитектурного этапа разработки алгоритмов, в рамках которого решаются задачи представления алгоритма в виде совокупности подсистем, спецификации данных, обрабатываемых подсистемами, и спецификации информационных связей между подсистемами.----------...
Saved in:
| Date: | 2009 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/4382 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2009. — № 2. — С. 3-11. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860268707338518528 |
|---|---|
| author | Акуловский, В.Г. |
| author_facet | Акуловский, В.Г. |
| citation_txt | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2009. — № 2. — С. 3-11. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| description | Предложен подход к формализации некоторых аспектов архитектурного этапа разработки алгоритмов, в рамках которого решаются задачи представления алгоритма в виде совокупности подсистем, спецификации данных, обрабатываемых подсистемами, и спецификации информационных связей между подсистемами.-------------------
Запропоновано підхід до формалізації деяких аспектів архітектурного етапу розробки алго-ритмів, у рамках якого вирішуються задачі представлення алгоритму у вигляді сукупності підсистем, специфікації даних, які оброблюються підсистемами, і специфікації інформаційних зв'язків між підсистемами.-----------
The approach to formalization of some aspects of an architectural development cycle of algorithms within the framework of which solve the tasks of representation of algorithm as connection of sub-systems, specification of the data process able by subsystems, and the specification of information subsystems’ connections.
|
| first_indexed | 2025-12-07T19:04:01Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
3
УДК 519.683
В.Г. Акуловский
НЕКОТОРЫЕ АСПЕКТЫ ФОРМАЛИЗАЦИИ
АРХИТЕКТУРНОГО ЭТАПА РАЗРАБОТКИ АЛГОРИТМОВ
Предложен подход к формализации некоторых аспектов архитектурного этапа разработки алгоритмов,
в рамках которого решаются задачи представления алгоритма в виде совокупности подсистем, специ-
фикации данных, обрабатываемых подсистемами, и спецификации информационных связей между
подсистемами.
Введение
Этап архитектурного проектирова-
ния в процесс разработки алгоритмов иг-
рает ключевую роль так как от качества
его реализации в существенной мере зави-
сят все последующие этапы и, в конечном
счете, качество программного продукта.
На этом этапе решаются две основные
взаимосвязанные задачи [1]:
1) определяется состав подсистем,
образующих алгоритм, и специфицируют-
ся обрабатываемые и продуцируемые
этими подсистемами данные;
2) специфицируются взаимосвязи
между этими подсистемами.
При этом уровень формализации
данного этапа проектирования явно недос-
таточен. В большинстве случаев проекти-
рование ведется с использованием графи-
ческих средств (граф - схемы, диаграммы и
т.п.), при этом информационные связи
внутри алгоритма оформляются в виде от-
дельного документа. Наличие нескольких
документов, отражающих различные ас-
пекты проекта, может служить источником
ошибок, связанных с несоответствиями в
этих документах.
Цель данной работы – решение
двух названных задач в рамках единого
формального аппарата. Кроме этого, наря-
ду с требованием к процессу проектирова-
ния алгоритмов, заключающемся в необ-
ходимости обеспечения соответствия из-
вестным принципам: формальности, абст-
рактности, иерархической упорядоченно-
сти и т.д., приведем ограничение, контроль
удовлетворения которого входит в состав
решаемых задач.
Ограничение. Все специфициро-
ванные в алгоритме данные должны быть
использованы, а все используемые – спе-
цифицированы.
В качестве формального аппарата,
для проектирования алгоритмов на упомя-
нутом этапе, выберем расширенную алгеб-
ру алгоритмов (САА-Р) [2], которая явля-
ется расширением известной алгебры ал-
горитмов Глушкова [3, 4]. А в качестве ме-
тода разработки – метод структурного
проектирования программ (МСПП) [5, 6],
основанный на декомпозиции алгоритмов
и базирующийся на выбранном формаль-
ном аппарате. Отметим, что использование
МСПП, позволяет следовать вышеприве-
денным принципам.
Решение задачи формализации
взаимодействия операторов и данных в
рамках САА-Р, выполненное в [7], послу-
жило предпосылкой к данной работе.
Таким образом, будем решать за-
дачи, характерные для выбранного этапа
разработки алгоритмов, повышая уровень
его формализации за счет использования
алгебраического аппарата и обеспечивая
удовлетворение вышеприведенного огра-
ничения.
Исходные определения и исполь-
зуемая терминология
Многие из приведенных далее оп-
ределений были ранее даны в работах
[7, 8], однако в данном случае они будут
формулироваться в соответствии со спе-
цификой решаемой задачи.
Используемый формальный аппарат
представляет собой систему алгоритмиче-
ских алгебр – Ω,, LU , где U – множест-
во операторов, L – множество логических
условий, Ω – сигнатура операций, со-
© В.Г. Акуловский, 2009
ISSN 1727-4907. Проблеми програмування. 2009. № 2
Теоретичні та методологічні основи програмування
4
стоящая из логических операций – 1Ω ,
принимающих значения на множестве L, и
операций – 2Ω , принимающих значения
на множестве операторов U .
Операторы определим следующим
образом.
Определение 1. Операторы, с по-
мощью которых строится алгоритм:
UDAD ∈′)()( ,
где D – входные данные (область опреде-
ления), D′ – выходные данные (область
значений). Эти операторы, обрабатывая
входные данные D , изменяют их (или не-
которое их подмножество) и порождают
новые данные, формируя таким образом
множество выходных данныхD′ .
Отметим, что запись оператора в
виде )()( DAD ′ позволяет специфициро-
вать обрабатываемые этим оператором
данные.
Из множества операций САА-Р в
данном случае воспользуемся единствен-
ной операцией композиции, которую (с
учетом определения 1) определим так.
Определение 2. Операция компо-
зиции (обозначается символом “*”) двух
операторов )()(*)()( BBAA DBDDAD ′′ озна-
чает, что оператор )()( AA DAD ′ предшест-
вует оператору )()( BB DBD ′ , а оператор
)()( BB DBD ′ следует за оператором
)()( AA DAD ′ , т. е. последовательно выпол-
няются сначала оператор )()( AA DAD ′ , а
затем оператор )()( BB DBD ′ .
Основной подход к процессу про-
ектирования в рамках МСПП состоит в де-
композиции операторов, т. е. в представ-
лении их в виде регулярных схем (РС), ко-
торые с учетом определений 1 и 2 введем
следующим образом.
Определение 3. Регулярной схемой
(РС) будем называть выражение вида
)()(*...*)()(*...
...*)()(*)()( )( 222111
nnniii DADDAD
DADDAD)D(D
′′
′′=′Α
(где нижний индекс – порядковый номер
оператора), в котором операторы
ni AAAA ,...,,...,, 21 выполняются последова-
тельно и их суммарная функциональ-
ность адекватна функциональности опе-
ратора A . Оператор )D(D ′Α)( будем на-
зывать исходным, а любой оператор
)()( iii DAD ′ – результирующим. Специфи-
цированные для исходных и результи-
рующих операторов данные удовлетво-
ряют следующим соотношениям:
U
n
j
jDD
1=
= и U
n
j
jDD
1=
′=′ .
Как уже отмечалось, одной из задач,
решаемых на рассматриваемом этапе раз-
работки, является спецификация инфор-
мационных связей. Учитывая особенности
этой задачи, абстрагируясь от того, что
данные заносятся в память и читаются из
неё, будем в процессе изложения говорить,
что данные поступают на вход (появляют-
ся на входе) оператора, появляются на его
выходе и передаются с выхода одного опе-
ратора на вход другого. Будем полагать,
что данные передаются от некоторого
оператора к одному или нескольким сле-
дующим за данным оператором, т. е. пе-
редаются в соответствии с определениями
2 и 3 слева направо.
Чтобы осуществить требуемую
спецификацию связей, определим понятие
связанных операторов.
Определение 4. Операторы
)()( iii DAD ′ и )()( jjj DAD ′ (где i<j), входящие
в РС
)()(*...*)()(*...*)()( )( 111 kkkjjj DADDADDAD)DA(D ′′′=′ ,
связаны, если для них выполняется соот-
ношение: ∅≠∩′ ji DD , т. е. некоторое
подмножество выходных данных опера-
тора )()( iii DAD ′ поступает на вход опера-
тора )()( jjj DAD ′ . Будем говорить, что
множество данных jiji DDD ∩′=
r
связыва-
ет операторы iA и jA (на что указывают
используемые индексы) и эти данные ji D
r
будем называть связывающими.
Из определения 4 следует, что свя-
зывающие данные образуют информаци-
онные связи в РС.
Теоретичні та методологічні основи програмування
5
Разработка алгоритма
Будем исходить из того, что на эта-
пах, предшествовавших архитектурному
этапу проектирования алгоритма, разрабо-
таны спецификации решаемой задачи. В
результате чего мы располагаем специфи-
кациями исходных Dисх , результирующих
Dрез данных и перечнем функций, преоб-
разующих первые во вторые.
Названные данные определим сле-
дующим образом.
Определение 5. Исходные – это
определенные (инициализированные),
т. е. имеющие некоторые начальные зна-
чения данных, или данные, вводимые с
внешних устройств (клавиатуры, магнит-
ных дисков, аналого-цифровых преобра-
зователей и т.д.).
Определение 6. Результирующие
– это данные, являющиеся результатом
работы программной системы, отобра-
жаемые (например, на экране дисплея)
и/или сохраняемые на внешних устройст-
вах.
Очевидно, что практически в любом
алгоритме, помимо вышеопределенных,
присутствуют и другие данные, которые
назовем промежуточными и определим
следующим образом.
Определение 7. Промежуточные –
это данные, отсутствующие в специфика-
ции задачи, но необходимые для преобра-
зования исходных данных в результирую-
щие, так как они являются носителями
промежуточных результатов, получаемых
на пути от исходных к результирующим
данным.
Поскольку среди используемых ал-
горитмом данных различают глобальные и
локальные, определим их следующим об-
разом.
Определение 8. Локальными будем
называть данные, доступные только внут-
ри результирующих операторов, входя-
щих в РС, вне которых они не доступны и
не специфицированы.
Определение 9. Глобальными бу-
дем называть данные, специфицированные
для исходного оператора и доступные всем
результирующим операторам, входящим в
РС. При декомпозиции результирующих
операторов, локализованные в них данные
играют роль глобальных на следующем
уровне декомпозиции. Глобальные (и
только глобальные) данные на выходах
операторов являются (в соответствии с оп-
ределениями 3, 4, 8) связывающими.
После определения обрабатывае-
мых алгоритмом данных уместно опреде-
лить понятие алгоритм.
Определение 10. Алгоритмом на-
зовем первый и единственный оператор на
нулевом уровне декомпозиции, записан-
ный в виде )D(DD резисх 0
1
0
1
0
1
0
1 ),,( Α (верхний
индекс номер уровня декомпозиции, а
нижний порядковый номер оператора в
РС), преобразующий посредством проме-
жуточных данных 0
1D исходные данные
0
1Dисх в результирующие 0
1Dрез . Причем
множество глобальных (см. определение
9) данных 0
1D – это спецификация всех
(на входе и выходе) промежуточных дан-
ных, обрабатываемых результирующими
операторами.
Предложенную в определении 10
смысловую нагрузку индексы будут нести
с некоторыми дополнениями в процессе
всего дальнейшего изложения.
Используя определения 3, 5 – 7, 10,
выполним первый шаг декомпозиции ал-
горитма, с учетом того, что алгоритм не
содержит на входе и выходе связующих
данных, так как является единственным
оператором на нулевом уровне декомпо-
зиции. При этом все образующие его опе-
раторы, в соответствии с определением 4,
такие данные имеют (могут иметь при на-
личии информационных связей между
ними).
Запишем РС в виде:
).(),(*...
...*),(),(*...
...*),(),(*
*),(),(
),(
1111
11111
1
2
1
2
1
2
1
2
1
2
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
n
рез
nn
исх
n
ii
рез
ii
исх
i
резисх
резисх
резисх
DADD
DDADD
DDADD
DDADD
)D(DD
′
′
′=
=Α
(1)
Теоретичні та методологічні основи програмування
6
Отметим, что особенности в рас-
положении индексов для всех промежу-
точных данных 1Dj ′ (пример для j-го ре-
зультирующего оператора) будут исполь-
зованы и понятны из дальнейшего изло-
жения.
Рассмотрим свойства, которыми об-
ладает построенная на первом шаге деком-
позиции РС и используемые в ней дан-
ные. Причем, результирующие операторы
в контексте данной работы в дальнейшем
изложении будем называть подсистемами.
Из определений 3, 9 и 10 следует,
что РС (1) представляет собой совокуп-
ность подсистем, образующих алгоритм,
причем эта совокупность реализует все
функции по преобразованию всех исход-
ных данных во все результирующие, а
данные, специфицированные для алгорит-
ма являются глобальными для всех обра-
зующих его подсистем. При этом, первая
подсистема не содержит на входе, а по-
следняя (n-ая) – на выходе связывающих
данных, так как первой не предшествует,
а за последней не следует ни одной под-
системы.
Для исходных, результирующих и
промежуточных данных (в соответствии с
определением 3) имеют место следующие
свойства:
1
10
1 U
n
i
i
исхисх DD
=
= , (2)
1
10
1 U
n
i
i
резрез DD
=
= , (3)
UU
1
1
1
1
10
1
−
==
′∪=
n
i
i
n
i
i DDD , (4)
т. е. все исходные, результирующие и
промежуточные данные распределяются
между подсистемами, образующими
алгоритм.
Наличие у алгоритма на первом
шаге декомпозиции свойств 2 – 4 позво-
ляют удовлетворить ограничение, сфор-
мулированное во введении.
Реализовав первый шаг декомпози-
ции и рассмотрев свойства данных, ха-
рактерных для этого шага, перейдем к
решению второй задачи – спецификации
связей между подсистемами.
В общем случае каждая подсисте-
ма, входящая в РС, может быть связана со
всеми следующими за ней и всеми пред-
шествующими ей подсистемами. То есть,
у любой подсистемы множество выход-
ных данных содержит данные, связы-
вающие её со всеми следующими за ней
подсистемами, а множество входных дан-
ных включает в себя данные, связываю-
щие её со всеми предшествующими ей
подсистемами.
Такой общий случай и будем рас-
сматривать, предварительно дополнив
систему обозначений (с учетом обозначе-
ний, использованных в определении 4)
следующим образом. Связывающие дан-
ные на входе подсистемы будем обозна-
чать 1
jk D
s
, а на выходе – 1
pl D
r
, причем ле-
вый нижний индекс – порядковый номер
подсистемы в РС будем называть адресом
источника, а правый нижний индекс –
адресом приемника данных. Заметим, что
для реализации такой системы обозначе-
ний в (1) было использовано соответст-
вующее расположение индексов.
Перепишем РС (1) с учётом вве-
денных обозначений:
)(),...,,,..,,,,(*...
.*),...,,(),...,,,(*.
...*),...,,...,,(),,,(*
*),...,,...,,,(),(
),(
111
1
11
2
1
1
11
11
1
111
1
1
1
11
1
2
1
2
1
32
1
2
1
2
1
21
1
2
1
2
1
1
1
1
1
31
1
21
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
n
рез
nnnnjnnn
исх
n
njjjj
рез
jjjji
исх
i
nj
резисх
nj
резисх
резисх
DADDDDDD
DDDADDDD
DDDDADDD
DDDDDADD
)D(DD
ssss
rrss
rrrs
rrrr
−
+−
=
=Α
(5)
?
Теоретичні та методологічні основи програмування
7
В построенной РС не только спе-
цифицированы данные, но и все “источ-
ники” и “приемники” данных поставлены в
однозначное соответствие, т. е. любому
1
pl D
r
соответствует 1
pl D
s
, и, таким образом,
выполняется
UUUU
sr 1
1 2
1
1 2
−
= =
−
= =
=
n
l
n
k
i
kl
n
l
n
k
i
kl DD . (6)
Данная РС сохраняет свойства (2) и
(3) в неизменном виде, а свойство (4)
трансформируется к виду:
UUU
r1
1 21
10
1
−
= ==
∪=
n
l
n
k
i
kl
n
p
p DDD . (7)
В связи с наличием этих свойств,
ограничение удовлетворяются и в данном
случае.
Переходя ко второму шагу проек-
тирования, рассмотрим особенности ис-
пользования локальных данных. На пер-
вом шаге разработки мы не включали в
спецификацию локальные данные по двум
причинам. Во-первых, в соответствии с
определением 8 они доступны только
внутри результирующих операторов и,
учитывая это, не влияют на процесс раз-
работки на первом уровне декомпозиции.
Во-вторых, их включение в специфика-
цию вступило бы в противоречие с огра-
ничением.
Рассмотрение второго шага начнем
с декомпозиции i-й подсистемы из (1),
которую запишем в виде РС, где на входе
исходной подсистемы специфицируем ло-
кальные данные:
).,(),(*...
...*),(),(*...
...*),(),(*
*),(),(
),(),,(
22222
22222
2
2
2
2
2
2
2
2
2
2
2
1
2
1
2
1
2
1
2
1
111111
DDADD
DDADD
DDADD
DDADD
DDADDD
kkkkk
jjjjj
iiii
л
ii
резисх
резисх
резисх
резисх
резисх
′
′
′
′=
=′
(8)
Отметим, что локальные на первом
уровне декомпозиции данные 1
i
лD в соот-
ветствии с определением 9 для второго
уровня уже играют роль глобальных, то
есть для любого 2
jD (j пробегает значения
от 1 до k ) выполняется 112
i
л
ij DDD ∪⊆ и
множество данных 1
i
лD в качестве гло-
бального распределяется между всеми
подсистемами, входящими в РС.
Полученная после спецификации
локальных данных РС сохраняет свойства
(2) и (3), которые для данного уровня за-
писываются в виде:
1
21
U
k
j
j
исх
i
исх DD
=
= , (9)
1
21
U
k
j
j
рез
i
рез DD
=
= . (10)
Кроме этих свойств РС (8), в связи с ис-
пользованием локальных данных, облада-
ет следующими свойствами:
1
21л1
U
k
j
jii DDD
=
=∪ , (11)
U
k
j
ji DD
1
21
=
′=′ , (12)
из которых следует свойство аналогичное
(4)
)(
1
2211л1
U
k
j
jjjii DDDDD
=
′∪=′∪∪ , (13)
и, таким образом, ограничение выполня-
ется и в данном случае.
Применив такой подход ко всем
подсистемам первого уровня, получим
совокупность РС, которую будем назы-
вать слоем алгоритма. При рассмотрении
совокупности результирующие подсисте-
мы, образующие первый слой алгоритма,
будем использовать сквозную нумерацию
операторов внутри слоя, и в этом случае
нижний индекс будет определять порядко-
вый номер оператора в рассматриваемом
слое.
Теоретичні та методологічні основи програмування
8
Учитывая вышеизложенное, первый слой алгоритма запишем в виде:
),(),(*...
...*),(),(*...
...*),(),(*
*),(),( ),(),,(
22222
22222
2
2
2
2
2
21
2
2
2
2
2
1
2
1
2
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
11111
DDADD
DDADD
DDADD
DDADDDDADDD
kk
рез
kk
исх
k
jj
рез
jj
исх
j
резисх
резисхл резисх
′
′
′
′=′
),(),(*...
...*),(),(*...
...*),(),(*
*),(),( ),(),,(
22222
22222
2
2
2
2
2
2
2
2
2
2
2
1
2
1
2
1
2
1
2
1
1
2
1
2
1
2
1
2
1
2
1
2
22222
11111
11111
11111
DDADD
DDADD
DDADD
DDADDDDADDD
kkkk
исх
k
jkjkjkjk
исх
jk
kkkk
исх
k
kkkk
исх
k
л
рез
рез
рез
резрезисх
′
′
′
′=′
+++++
+++++
+++++
(14)
……………………………………………………………………………….
),(),(*...
...*),(),(*...
...*),(),(*
*),(),( ),(),,(
22222
22222
2
2
2
2
2
2
2
2
2
2
2
1
2
1
2
1
2
1
2
1
111111
11111
11111
11111
DDADD
DDADD
DDADD
DDADDDDADDD
ii
рез
ii
исх
i
ii
рез
ii
исх
i
ii
рез
ii
исх
i
i
рез
ii
исх
i
резисх
kkkkk
jkjkjkjkjk
kkkkk
kkkkkiiii
л
ii
′
′
′
′=′
+++++
+++++
+++++
−−−−−
−−−−−
−−−−
……………………………………………………………………………….
),(),(*...
...*),(),(*...
...*),(),(*
*),(),( ),(),,(
2222
22222
2
2
2
2
2
2
2
2
2
2
2
1
2
1
2
1
2
1
2
1
111111
11111
11111
11111
n
рез
nn
исх
n
nn
рез
nn
исх
n
nn
рез
nn
исх
n
nn
рез
nn
исх
n
резисх
kkkk
jkjkjkjkjk
kkkkk
kkkkknnnn
л
nn
DADD
DDADD
DDADD
DDADDDDADDD
′
′
′=′
+++++
+++++
+++++
−−−−−
−−−−−
−−−−−
где n – количество исходных операторов
и, соответственно, количество РС;
nk – общее количество подсистем, обра-
зующих слой.
Обобщим свойства (9) – (13) на
случай слоя алгоритма:
1
2
1
1
UU
nk
j
j
исх
n
i
i
исх DD
==
= , (15)
UU
nk
j
j
рез
n
i
i
рез DD
1
2
1
1
==
= , (16)
UU
nk
j
j
n
i
i
л
i DDD
1
2
1
11 )(
==
=∪ , (17)
UU
nk
j
j
n
i
i DD
1
2
1
1
==
′=′ (18)
)( )(
1
221
1
11
UU
k
j
jji
n
i
i
л
i DDDDD
==
′∪=′∪∪ (19)
и, исходя из полученных свойств, сделаем
вывод о том, что ограничение выполняет-
ся и для слоя алгоритма.
Теперь перейдем к спецификации
информационных связей в построенном
слое алгоритма, для чего перепишем вы-
ражение (14) в виде, аналогичном (5).
Теоретичні та методологічні основи програмування
9
),...,,...,,(),,...,,..,,(*...
...*),...,,...,,...,,(),,...,,..,,(*...
...*),,...,,...,,...,,...,,,(),,(*
*),,...,,...,,...,,...,,,(),(
),(),,(
222
1
2222
1
2
2
2
1
2
2222
1
2
121
2
2
2
12
2
2
2
2
2
2
2
42
2
32
2
2
2
2
2
2
2
212
2
1
2
11
2
1
2
1
2
1
2
31
2
21
2
1
2
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
111111111111
1
1
1
ni
ni
nni
nni
kkkkkkk
рез
kk
исх
kkkkk
kjkjkjjjj
резi
j
i
j
исхi
jj
i
j
i
j
i
j
kkkkj
резисхi
kkkkj
резисх
резлисх
DDDDADDDDD
DDDDDADDDDD
DDDDDDDDADDD
DDDDDDDDADD
DDADDD
rrrsss
rrrrsss
rrrrrrrs
rrrrrrr
+−
+−
−
−=
=′
),...,,...,,...,,,(),,...,,,(*...
...*),...,,...,,(),,...,,,(*...
...*),...,,...,,(),,...,,,(*
*),...,,...,,(),,...,,,(
),(),,(
2222
2
2
1
2222
1
2
2
2
1
2
222
1
2222
1
2
2
2
1
2
2
2
2
2
2
32
2
2
2
2
2
2
2
21
2
22
2
21
2
2
2
1
2
1
2
21
2
1
2
1
2
1
2
1
2
12
2
11
2
1
1
2
1
2
1
2
1
2
1
2
1
2
2222222222222222
111111111111
111111111111
111111111111
ni
резисх
ni
ni
исх
ni
kkkkjkkkkkkkkkkkkkk
kjkkjkjkjkjk
рез
jkjk
исх
jkjkjkjkjk
kkkkkkk
рез
kkkkkkk
kkkkkkk
рез
kk
исх
kkkkk
резлисх
DDDDDDADDDDD
DDDDADDDDD
DDDDADDDDD
DDDDADDDDD
DDADDD
rrrrrsss
rrrsss
rrrsss
rrrsss
+++−
+++++++++−++++
++++++++++++
+++++++++++=
=′
……………………………………………………………………………………………
),...,,...,,...,,...,,(),,...,,,(*...
...*),...,,(),,...,,,(*...
...*),...,,(),,...,,,(*
*),...,,...,,(),,...,,,(
),(),,(
2222
2
2
1
2
1
2
2
2
1
2
1
2
1
2222
1
2
2
2
1
2
2
2
2
32
2
2
2
2
2
2
2
21
2
22
2
21
2
2
2
1
2
1
2
21
2
1
2
1
2
1
2
1
2
12
2
11
2
1
111111
1
11111111111
11111111111
111111111111
niniiiiiiii
рез
ii
исх
iiiii
niiii
рез
ii
исх
iiiii
niiii
рез
ii
исх
iiiii
niiiiii
рез
ii
исх
iiiii
резисх
kkkkjkkkkkk
i
k
i
k
i
kkkkk
i
k
kkjkjkjkjkjkjkjkjkjkjk
kkkkkkkkkkkk
kkkkkkkkkkkkkk
iiii
л
ii
DDDDDDADDDDD
DDDADDDDD
DDDADDDDD
DDDDADDDDD
DDADDD
rrrrrsss
rrsss
rrsss
rrrsss
−
−−−−−−−−−−−
−−−−−−−−−−−
−−−−−−−−−−−−
+++−
++++++++−++++
+++++++++++
+++++++++++=
=′
………………………………………………………………………………………
)(),,...,,,(*...
...*),...,,(),,...,,(*...
...*),...,,(),,...,,,(*
*),...,,(),,...,,,(
),(),,(
2222
1
2
2
2
1
2
22
1
2222
1
2
1
2
2
2
2
32
2
2
2
2
2
2
2
21
2
22
2
21
2
2
2
1
2
21
2
1
2
1
2
1
2
1
2
12
2
11
2
1
111111
1111111111
11111111111
11111111111
n
рез
nn
исх
nnnnn
nnnnn
рез
nn
исх
nnnn
nnnnn
рез
nn
исх
nnnnn
nnnnn
рез
nn
исх
nnnnn
резисх
kkkkkkkk
kjkjkjkjkjkjkjkjkjkjk
kkkkkkkkkkkk
kkkkkkkkkkkk
i
n
i
n
i
n
i
n
лi
n
i
n
DADDDDD
DDDADDDD
DDDADDDDD
DDDADDDDD
DDADDD
sss
rrss
rrsss
rrsss
−
++++++++−+++
+++++++++++
++++++++++
−−−−−−
−−−−−−−−−−
−−−−−−−−−−−
−−−−−−−−−−−
=
=′
Для данного случая свойства
(15),(16) сохраняются неизменными, а ос-
тальные свойства обобщим на случай слоя
со специфицированными информацион-
ными связями.
Свойство (6) приобретает вид
UUUU
sr 11
1 21 2
−−
= == =
=
n nn n k
l
k
p
i
pl
k
l
k
p
i
pl DD ,
а свойства (17 – (19) трансформируются к
виду:
,)(
1
1 21
2
1
11
UUUU
s−
= ===
∪=∪
n nn k
l
k
p
i
pl
k
j
j
n
i
i
л
i DDDD
,
1
1 21
1
UUU
r−
= ==
=′
n nk
l
k
p
i
pl
n
i
i DD
)( )(
1 1 2
21
1
11
1
U UUU
rn
i
k
l
k
p
i
plji
n
i
i
л
i
n n
DDDDD
= = ==
−
∪=′∪∪ .
Для локальных данных в первом
слое алгоритма в рамках всех РС выпол-
няются соотношения, которые запишем
для случая i-й РС:
U U
r1
1 2
1
1 1
−
+= +=− −
⊆
i
i
i
i
k
kl
k
kp
i
pli
л DD
или в соответствии с (6)
Теоретичні та методологічні основи програмування
10
U U
s1
1 2
1
1 1
−
+= +=− −
⊆
i
i
i
i
k
kl
k
kp
i
pli
л DD ,
т. е. в соответствии с определениями 8 и 9
локальные данные играют роль глобаль-
ных только в рамках одной (i-й в данном
случае) РС.
Полученные свойства позволяют
утверждать, что ограничение выполняется
для каждой РС, входящей в данный слой,
и для всего слоя алгоритма.
Заметим, что в последнем случае,
как и во всех предыдущих, первая под-
система, для которой нет предшествую-
щих, не содержит на входе, а последняя
подсистема, для которой нет последую-
щих подсистем, не содержит на выходе
связывающих данных.
Таким образом, нам удалось специ-
фицировать связи между подсистемами в
рамках первого слоя алгоритма и сформу-
лировать свойства данных в этом слое.
Очевидно, что процесс декомпо-
зиции повторяется на каждом шаге разра-
ботки, и структура второго и последую-
щих слоев будет полностью повторять
структуру первого слоя, сохраняя при
этом все вышесформулированные свойст-
ва. Различие между слоями алгоритма бу-
дет состоять только в том, что каждый
последующий слой будет “толще” преды-
дущего за счет роста числа РС.
Процесс декомпозиции на данном
этапе продолжается до того момента, когда
будут выделены все подсистемы, обра-
зующие проектируемую программную
систему. В результате такого построения
получим некоторое количество слоёв алго-
ритма, где каждый, ниже расположенный,
будет носить все менее абстрактный (более
детализованный) характер и, как вышеот-
мечено, будет достигнуто соответствие
принципам, упомянутым во введении. Еще
раз так же отметим, что сформулированное
во введении ограничение в рамках данного
подхода удовлетворяется при выполнении
всех шагов архитектурного этапа разра-
ботки алгоритмов.
При рассмотрении данного этапа
мы брали самый общий случай, когда ка-
ждая подсистема, входящая в РС или слой
алгоритма, связана со всеми предшест-
вующими и всеми следующими за ней. На
практике такие случаи встречаются доста-
точно редко, т. е. обычно не все подсис-
темы связаны друг с другом и имеют ме-
сто не связанные (независимые) с други-
ми подсистемами. В связи с чем заметим,
что любое из множеств m
i
исхD , m
i
резD ,
m
iD , m
i D′ (в любом сочетании, но не все
сразу) может быть пустым и, таким обра-
зом, в конкретных разработках допустимы
многочисленные частные случаи подсис-
тем (например: )(),,( 11111 DADDD iii
л
i
исх
i ′ ,
),(),( 11111 DDADD ii
рез
ii
л
i ′ , )(),( 1111 DADD iii
л
i ′ и
т.д.), обладающих приведенными в работе
свойствами.
Заключение
Таким образом, предложен подход
к архитектурному этапу разработки алго-
ритмов, по завершению которого разра-
ботчик выявляет структурированное пред-
ставление о программной системе, т. е.
определяет состав и функции подсистем, а
так же взаимосвязи между всеми подсис-
темами.
Традиционно процесс декомпози-
ции реализуется двумя путями. При пер-
вом (от управления) – декомпозируются
операторы и в соответствии с понижением
уровня их функциональности детализуют-
ся обрабатываемые оператором данные.
При втором (от данных) – детализуются
данные и, в соответствии с полученной
степенью детализации, определяется
функциональность операторов для их об-
работки.
Подход, предложенный в данной
работе, основывается на согласованной
декомпозиции операторов и детализации
данных, что позволяет рассчитывать на
повышение качества разрабатываемого ал-
горитма. Расчет строится на том, что на
каждом шаге разработки выбирается наи-
более эффективный в данном случае спо-
соб, так как при этом может быть проана-
лизирован и учтен возможный результат
использования альтернативного варианта.
Анализ информационных связей в
алгоритмах является перспективным
Теоретичні та методологічні основи програмування
11
средством контроля корректности и пре-
образования алгоритмов. В частности,
приведенные в работе свойства данных
можно рассматривать как средство кон-
троля корректности алгоритма с точки
зрения обработки данных на всех уровнях
декомпозиции алгоритма. Применение
предложенного подхода на других этапах
разработки алгоритмов и реализация ука-
занных перспектив являются направлени-
ем дальнейших исследований.
1. Соммервилл И. Инженерия программного
обеспечения. – М.: Издательский дом
“Вильямс”, 2002. – 642 с.
2. Акуловский В.Г. Расширенная алгебра ал-
горитмов // Проблеми програмування. –
2007. – № 3. – С. 3 – 15.
3. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра. Языки. Программирование. – К.:
Наук. думка, 1978. – 319 с.
4. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е.,
Яценко Е.А. Алгеброалгоритмические мо-
дели и методы параллельного программи-
рования. – К.: Академперіодика, 2007. –
634 с.
5. Цейтлин Г.Е., Бакулин А.В. Многоуровне-
вые структурированные проекты программ
и их обоснование // Кибернетика и систем-
ный анализ. – 1991. – № 5. – С. 98 – 107.
6. Ющенко Е.Л., Цейтлин Г.Е.,Грицай
В.П., Терзян Т.К. Многоуровневое
структурное проектирование про-
грамм: Теоретические основы, инстру-
ментарий. – М.: Финансы и статисти-
ка, 1989. – 208 с.
7. Акуловский В.Г. Формализация взаимо-
связей операторов и данных в рамках
расширенной алгебры алгоритмов //
Кибернетика и системный анализ. –
2008. – № 6. – С. 32 – 37.
8. Акуловский В.Г. Некоторые подходы к
контролю и преобразованию алгорит-
мов на основе анализа специфицируе-
мых данных // Проблеми програмуван-
ня. – 2008. – № 4. – С . 84 – 93.
Получено 16.03.2009
Об авторе:
Акуловский Валерий Григорьевич,
канд.техн.наук, доцент кафедры информа-
ционных систем и технологий
e-mail: valeryakulovskiy@rambler.ru
Место работы автора:
Академия таможенной службы Украины.
49000, Днепропетровск, ул. Дзержинского
2\4. Тел/факс. канцелярия – (0562) 45 5596
e-mail :academy@amsu.dp.ua
|
| id | nasplib_isofts_kiev_ua-123456789-4382 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T19:04:01Z |
| publishDate | 2009 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Акуловский, В.Г. 2009-10-29T13:00:36Z 2009-10-29T13:00:36Z 2009 Некоторые аспекты формализации архитектурного этапа разработки алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2009. — № 2. — С. 3-11. — Бібліогр.: 8 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/4382 519.683 Предложен подход к формализации некоторых аспектов архитектурного этапа разработки алгоритмов, в рамках которого решаются задачи представления алгоритма в виде совокупности подсистем, спецификации данных, обрабатываемых подсистемами, и спецификации информационных связей между подсистемами.------------------- Запропоновано підхід до формалізації деяких аспектів архітектурного етапу розробки алго-ритмів, у рамках якого вирішуються задачі представлення алгоритму у вигляді сукупності підсистем, специфікації даних, які оброблюються підсистемами, і специфікації інформаційних зв'язків між підсистемами.----------- The approach to formalization of some aspects of an architectural development cycle of algorithms within the framework of which solve the tasks of representation of algorithm as connection of sub-systems, specification of the data process able by subsystems, and the specification of information subsystems’ connections. ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Некоторые аспекты формализации архитектурного этапа разработки алгоритмов Some aspects of formalization of an architectural development cycle of algorithms Article published earlier |
| spellingShingle | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов Акуловский, В.Г. Теоретичні та методологічні основи програмування |
| title | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов |
| title_alt | Some aspects of formalization of an architectural development cycle of algorithms |
| title_full | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов |
| title_fullStr | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов |
| title_full_unstemmed | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов |
| title_short | Некоторые аспекты формализации архитектурного этапа разработки алгоритмов |
| title_sort | некоторые аспекты формализации архитектурного этапа разработки алгоритмов |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/4382 |
| work_keys_str_mv | AT akulovskiivg nekotoryeaspektyformalizaciiarhitekturnogoétaparazrabotkialgoritmov AT akulovskiivg someaspectsofformalizationofanarchitecturaldevelopmentcycleofalgorithms |