Сoordinated description of algorithms within the framework of algebraic vehicle

The possibility of the concerted description of management streams is shown, data and informative connections in the process of algorithms’ development facilities of the tribasic algebraic system (algebras of algorithms with data) is shown (in most general case). The properties of the got charts of...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Akulovskiy, V.G., Doroshenko, A.Yu.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	UDC 004.42
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/690
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-690
record_format	ojs
resource_txt_mv	ppisoftskievua/ce/d6d0b7c7e9fae7ae8ea624592fb301ce.pdf
spelling	pp_isofts_kiev_ua-article-6902025-04-09T22:22:32Z Сoordinated description of algorithms within the framework of algebraic vehicle Согласованное описание алгоритмов в рамках алгебраического аппарата Akulovskiy, V.G. Doroshenko, A.Yu. UDC 004.42 УДК 004.42 The possibility of the concerted description of management streams is shown, data and informative connections in the process of algorithms’ development facilities of the tribasic algebraic system (algebras of algorithms with data) is shown (in most general case). The properties of the got charts of algorithms are rotined.Prombles in programming 2014; 2-3: 29-37 Продемонстрирована (в самом общем случае) возможность согласованного описания потоков управления, данных и информационных связей в процессе разработки алгоритмов средствами трехосновной алгебраической системы (алгебры алгоритмов с данными). Показаны свойства получаемых схем алгоритмов.Prombles in programming 2014; 2-3: 29-37 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/690 PROBLEMS IN PROGRAMMING; No 2-3 (2014); 29-37 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2014); 29-37 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2014); 29-37 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/690/742 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-04-09T22:22:32Z
collection	OJS
language	Russian
topic	UDC 004.42
spellingShingle	UDC 004.42 Akulovskiy, V.G. Doroshenko, A.Yu. Сoordinated description of algorithms within the framework of algebraic vehicle
topic_facet	UDC 004.42 УДК 004.42
format	Article
author	Akulovskiy, V.G. Doroshenko, A.Yu.
author_facet	Akulovskiy, V.G. Doroshenko, A.Yu.
author_sort	Akulovskiy, V.G.
title	Сoordinated description of algorithms within the framework of algebraic vehicle
title_short	Сoordinated description of algorithms within the framework of algebraic vehicle
title_full	Сoordinated description of algorithms within the framework of algebraic vehicle
title_fullStr	Сoordinated description of algorithms within the framework of algebraic vehicle
title_full_unstemmed	Сoordinated description of algorithms within the framework of algebraic vehicle
title_sort	сoordinated description of algorithms within the framework of algebraic vehicle
title_alt	Согласованное описание алгоритмов в рамках алгебраического аппарата
description	The possibility of the concerted description of management streams is shown, data and informative connections in the process of algorithms’ development facilities of the tribasic algebraic system (algebras of algorithms with data) is shown (in most general case). The properties of the got charts of algorithms are rotined.Prombles in programming 2014; 2-3: 29-37
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/690
work_keys_str_mv	AT akulovskiyvg soordinateddescriptionofalgorithmswithintheframeworkofalgebraicvehicle AT doroshenkoayu soordinateddescriptionofalgorithmswithintheframeworkofalgebraicvehicle AT akulovskiyvg soglasovannoeopisaniealgoritmovvramkahalgebraičeskogoapparata AT doroshenkoayu soglasovannoeopisaniealgoritmovvramkahalgebraičeskogoapparata
first_indexed	2025-07-17T09:47:49Z
last_indexed	2025-07-17T09:47:49Z
_version_	1850409862450642944
fulltext	Теоретичні та методологічні основи програмування © В.Г. Акуловский, А.Е. Дорошенко, 2014 ISSN 1727-4907. Проблеми програмування. 2014. № 2–3. Спеціальний випуск 29 УДК 004.42 СОГЛАСОВАННОЕ ОПИСАНИЕ АЛГОРИТМОВ В РАМКАХ АЛГЕБРАИЧЕСКОГО АППАРАТА В.Г. Акуловский, А.Е. Дорошенко Академия таможенной службы Украины. 49000, Днепропетровск, ул. Дзержинского 2/4. Тел/Факс: (0562) 745 5596, (0562) 47 1791 E-mail: academy@amsu.dp.uа. Інститут програмних систем НАН України, 03187, Київ, проспект Академіка Глушкова 40. Тел.: 526 3559, e-mail: doroshenkoanatoliy2@gmail.com Продемонстрирована (в самом общем случае) возможность согласованного описания потоков управления, данных и информацион- ных связей в процессе разработки алгоритмов средствами трехосновной алгебраической системы (алгебры алгоритмов с данными). Показаны свойства получаемых схем алгоритмов. The possibility of the concerted description of management streams is shown, data and informative connections in the process of algorithms’ development facilities of the tribasic algebraic system (algebras of algorithms with data) is shown (in most general case). The properties of the got charts of algorithms are rotined. Введение Поскольку алгоритм является многоаспектной сущностью, то актуальна задача такого его описания, в рамках которого отображаются основные его аспекты: потоки управления, структуры обрабатываемых данных и информационные связи. При этом на каждом этапе разработки эти аспекты должны быть согласованы между собой. Учитывая важность роли данных в процессе разработки алгоритмов [1, 2], для решения этой задачи предложен алгебраический аппарат [3–5] в который, в результате модификации известной модели ЭВМ Глуш- кова [6], “встроены” данные. Далее приведены некоторые элементы этого алгебраического аппарата необходимые решения указанной задачи. Алгебра алгоритмов с данными Упомянутый алгебраический аппарат представляет собой трехосновную алгебраическую систему САА\Д::= };,,{ DLU (алгебру алгоритмов с данными), где U – множество Д-операторов, L – множество логических условий, D – множество данных,  – базовый набор операций алгебры, включающий операции 1 , определенные на множестве U, 2 , определенные на множестве L, 3 , определенные на множестве D. В рамках алгебры данные определены следующим образом. Определение 1. Составными данными будем называть пару ЗND jA , , где nззЗ ,...,1 – кортеж значе- ний, простыми – зNd jA , , где з – значение, носитель которых jAN , однозначно идентифицируется адресом IA j  . В каждый момент времени данные хранят некоторый кортеж значений З, значение – з, определяющий текущее состояние данных. Используемые далее типы данных соответствуют традиционному для языков программирования поня- тию и будут обозначаться if , где },...,,{ 21 ki fffFf  , а F – множество возможных типов данных. Первичными структурами данных являются: составные данные (первичные записи) sD такие, что xx f k f ззЗ ,...,1 где xf – произвольный тип данных, и одномерные массивы (векторы) ifDn такие, что ii f n f ззЗ ,...,1 , где if – конкретный тип данных, n – число этих значений (размерность массива). Заметим, что вектор может интерпретироваться различным образом, например, как строка. На множестве упорядоченных первичных структур данных, которые в общем случае обозначим SD , определим операцию объединения (композиции) данных – “ * ”. В результате применения этой операции к первичным структурам данных ЗП i1DDD SS , в общем случае ЗП j11 DD...D S p S , получаем новую структуру дан- ных, называемую записью, где левый нижний индекс – указывает уровень вложенности структур. Применяя mailto:academy@amsu.dp.uа Теоретичні та методологічні основи програмування 30 операцию композиции к полученным записям ЗП j2111 DD...D ЗП s ЗП , получаем новую запись второго уровня вло- женности, в которую могут быть вложены как первичные, так и производные структуры данных. Продолжая такой процесс можем получать записи ЗП jDn с практически неограниченной вложенностью. Получаемые таким образом записи на каждом уровне вложенности могут трактоваться как кортеж семейств множеств ЗП k1 ЗП 11 ЗП j D,...,DD  nnn таких, что для любого ЗП i1 ЗП i2 DD j  nn выполняется ЗП p1 ЗП i2 DD j  nn для всех ip  . Для построения производных структур данных введем производные операции, первой из которых явля- ется операция итерации данных, полученная в результате обобщения операции композиции на n одинаковых элементов и записываемая в виде “ n{} ”. Применяя эту операцию к некоторому одномерному массиву размера 1n получаем двумерный массив ii fnfn D D }{ 1221 n,n  , к двумерному – трехмерный массив ifD 123 n,n,n и т. д., на k-ом шаге получаем iki fnf D D }{ 12k121-k n,n,...,nn,n,...,.n  k-мерный массив. Распространив операцию итерации данных на множество записей, получаем ЗПnЗП} { DD n одномерный массив записей (в дальнейшем массив записей). Применяя эту операцию к массиву записей k раз, получаем многомерный массив записей в виде ЗПnЗП kD D }{ 1k11-k n,...,nn,...,.n  . Введенная операция позволила получить производные структуры данных многомерные массивы, одно- мерные и многомерные массивы записей. Операция композиции распространенная на полученные производ- ные структуры данных, позволяет организовывать записи, включающие в свой состав простые данные, одно- мерные и многомерные массивы, одномерные и многомерные массивы записей, то есть получать структуры данных произвольной сложности вложенные на произвольную глубину. Для случая, когда необходимо описывать в виде единого целого произвольно расположенные, в частно- сти, семантически несвязанные данные, введем операцию группировки данных, которую обозначим “ ”. В результате применения этой операции к произвольным структурам данных Г i SS DDD 1  , а в общем случае Г i S p S DDD 11 ...   , получаем новые данные, называющиеся первичными группами данных. Распространив эту операцию на множество групп ГГ m Г DDD 12111 ...   получаем новую группу данных второго уровня вложенно- сти, в которую могут быть вложены как первичные, так и производные группы. Элементы группы данных могут быть, как упорядочены, так и не упорядочены, а отличие их от структур данных состоит в том, что на множестве групп данных операция композиции не определена. Последовательное применение операции группировки к группам данных Г j Г k1 Г 11 DD...D nnn    позволяет получить вложенность групп данных на практически произвольную глубину. На любом, начиная со второго уровня вложенности групп данных, они могут трактоваться как семейство множеств }D,...,D{D Г k1 Г 11 Г j  nnn таких, что для любого Г i1 Г i2 DD j  nn допустимо как Г p1 Г i2 DD j  nn , так и Г p1 Г i2 DD j  nn для всех ip  . Для детализации данных введем операции. Операция разгруппировки “  ”, применение которой к группе данных Г pn Г n Г in DDD 111 ,...,  (1) порождает группы данных предшествующего уровня вложенности. В частных случаях и в случае первичной группы данных получаем структуры данных и\или простые данные. Вторая такая операция – это операция детализации (декомпозиции) данных, обозначенная – “ ” . Применение этой операции к полученным выше структурам данных выполняется следующим образом: – из многомерного массива записей получаем k n массивов записей ЗП n n,n,...,nЗП 1 n,n,...,nn,...,n k 11-k11-kk ,..., )(* DDDЗП  ; (2) – из одномерного массива записей получаем n записей ЗП n ЗП DDD ,...,)(* 1 ЗПn  ; (3) – из записей получаем записи ЗП mn ЗП n ЗП in DDD 111 ,...,*  (4) Теоретичні та методологічні основи програмування 31 или/и любые другие структуры данных (массивы записей, массивы, простые данные). В случае первичной за- писи xx f n f dd ,...,D* 1 s i  – кортеж простых данных произвольного типа; – из многомерного массива получаем k n массивов iii fff k 11-k11-k1k n n,...,n 1 n,...,nn,...,n D,...,D )D( *  ; (5) – из одномерного массива получаем кортеж из n простых данных типа if iii f n ff dd ,...,)D(* 1 n  . (6) Приведенные операции позволяют детализовать все возможные структуры данных. В результате такой декомпозиции массивы разбиваются на образующие их компоненты. Однако необходимость осуществлять де- тализацию сложных глубоко вложенных структур данных требует дополнительных средств. Достаточно легко увидеть, что на основе введенных легко могут строиться производные операции. В частности, для групп данных операция Г pn Г sn Г in Г rn Г n Г insr DDDDDD 11111 ,...,,,,...,)(*   , (7) где Г sn Г rn Г in DDD 1111 ...    , отделяет r первых и s последних групп данных предыдущего уровня их вложен- ности. Ограничением на применение этой операции является соотношение sr  . Заметим, что при sr  опера- ции вырождаются в исходную операцию разгруппировки (см. (1)). Заметим так же, что эти операции, очевид- но, могут использоваться и в случае, когда детализуемые группы данных включают не только группы, а и лю- бые структуры данных. Для записей производными операциями детализации данных являются: ЗП in ЗП in ЗП in ppp s s DDD ,...,)(* 1 21 ,...,  , (8) где ЗП ppn ЗП ppn ЗП in jjj DDD    ...11...1 111 ... ; ЗП pn ЗП sn ЗП in ЗП rn ЗП n ЗП insr DDDDDD 11111 ,...,,,,...,)(*   , (9) где ЗП sn ЗП rn ЗП in DDD 1111 ...**  . Для массивов и массивов записей, которые в общем многомерном случае обозначим D1k n,...,n , производ- ными операциями детализации данных являются: i s ksikiks f j sspf j sspf j ssppp DDD 11 1 111121 ,...,,,...,,,...,,..., ,...,)(*  и ЗП i ssp n ЗП i ssp n ЗП i ss n ppp s kskks DDD 11 1 111121 ,...,,,...,,,...,,..., ,...,)(*  , (10) в результате выполнения которых каждый из исходных массивов распадается на s массивов таких, что ks sppp   ...21 , что является ограничением на применение этой операции. Эта операция, примененная к одномерным массивам i s siis f j pf j pf j sppp DDD ,...,)(* 1 121 ,...,  и ЗП i p n ЗП i p n ЗП i s n ppp s ss DDD ,...,)(* 1 121 ,...,  , (11) порождает s одномерных массивов, при условии, что sppp s   ...21 . Распространив производную операцию (4) на множество массивов, получаем следующий результат: i sr ki r kiki r kikik f j ssf j ssf j ssrsf j ssf j ssf j ss sr DDDDDD       11 1 11111 1 111 ,...,,...,),...,(,...,,...,,..., ,...,,,,...,)(* и (12) ,,...,,,...,)(* 11 1 11111 1 111 ,..., 1 ,..., 1 ),...,(,..., 1 ,..., 1 ,..., ЗП i ss n ЗП i ss n ЗП i ssrs n ЗП i ss n ЗП i ss n ЗП i ss nsr sr k r kk r kkk DDDDDD         при условии kssr  . Введенные операции (1)–(12) позволяют разгруппировать (перегруппировать) группы и детализовать структуры данных произвольной сложности и размера вложенные на произвольную. Производные операции, набор которых, очевидно может быть расширен, упрощают процесс детализации сложно организованных дан- ных. К логическим операциям, определенным на множестве логических условий L, отнесены известные опе- рации дизъюнкция, конъюнкция отрицание со своими таблицами истинности [6]. Теоретичні та методологічні основи програмування 32 Фундаментальным элементом описания алгоритмов, в рамках этого аппарата, являются Д-операторы )()( DXD  , обрабатывающие данные и определенные в работе [4] следующим образом. Определение 2. На входе Д-оператора )()( DXD  специфицировано множество входных данных D (в частном случае простые данные d ), обрабатывая которые он в общем случае изменяет множество выходных (специфицированных на его выходе) данных D (в частном случае простых данных d  ). Для множеств вход- ных и выходных данных таких, что D и D , может выполняться как соотношение DD (в частности, DD  и DD  ), так и DD . В первом случае, изменяются значения подмножества вход- ных данных )( DDDD  (в частности, все входные данные, если DD  ). Во втором – значения вход- ных данных остаются неизменными. Определяющей для дальнейших рассуждений является операция композиции Д-операторов опреде- ленная следующим образом. Композиция Д-операторов (операция обозначается “”) ) ~ ( ~ ) ~ ()()( DXDDXD  означает последовательное выполнение сначала Д-оператора )()( DXD  затем Д-оператора ) ~ ( ~ ) ~ ( DXD  . То есть, Д-оператор )()( DXD  непо- средственно предшествует Д-оператору ) ~ ( ~ ) ~ ( DXD  , а Д-оператор ) ~ ( ~ ) ~ ( DXD  непосредственно следует за Д- оператором )()( DXD  . Естественное обобщение этой операции записывается в виде )()(...)()(...)()( 111 sssiii DXDDXDDXD  . Кроме операции композиции сигнатура алгебры Д-операторов включает множество других операций (см. [3, 4]), которые в данной работе только упоминаются. На основе изложенного перейдем к решению поставленной задачи. Разработка алгоритмов Перед тем, как разрабатывать алгоритм, определим его. Определение 3. Алгоритмом называется Д-оператор )()( DAD  , на входе которого специфицированы все глобальные данные подлежащие обработке, а на выходе все глобальные данные, являющиеся результатом этой обработки (результирующие). Очевидно, что обрабатываемые – это определенные (инициализированные), то есть имеющие некото- рые начальные значения данные, в частности константы, или данные, вводимые с внешних устройств (клави- атуры, магнитных дисков, аналого-цифровых преобразователей и т. д. и т. п.). Результирующие – это дан- ные, являющиеся результатом работы программной системы, отображаемые (например, на экране дисплея) и/или сохраняемые на внешних устройствах. Исходя из определения и приведенных соображений, алгоритм запишем в виде )(),( РЕЗИСХ_ИСХ DADD R , где ИСХD – исходные, RDИСХ_ – вводимые исходные данные, РЕЗD – результирующие данные. При этом ИСХD или РЕЗD могут отсутствовать, а множество РЕЗD . Рассмотрение процесс разработки алгоритма начнем со следующего требования предъявляемого к этому процессу. Наряду с реализацией известных принципов (формальности, абстрактности, иерархической упоря- доченности и т. д.), в процессе разработки необходимо обеспечить, что бы все специфицированные в алгорит- ме данные были обработаны, а все обрабатываемые – специфицированы. В качестве основы для организации процесса разработки воспользуемся теоремой, доказанной в работе [7], смысл которой, если отбросить не существенные для рассматриваемого случая подробности, состоит в сле- дующем. Произвольный Д-оператор )()( DXD  может быть декомпозирован, то есть, представлен в виде эквива- лентной ему композиции двух других Д-операторов )()()()()()( DXDDXDDXD(   . Обобщение этого резуль- тата позволяет ввести следующую форму представления Д-оператора, )()(...)()()()()()( 222111 kkk DXDDXDDXDDXD  , которая называется его композиционной схемой (КС), в которой )()( DXD  – исходный, а )()( 111 DXD  , )()( 222 DXD  , …, )()( kkk DXD  – производные Д-операторы. С другой стороны представление любого Д-оператора через образующие элементы системы },{};,{ 21 LU назовем регулярной схемой этого Д-оператора (РСД). При этом в работе [4] показано, что любую операцию из 1 на некотором этапе разработки можно трактовать как Д-оператор, а Д-оператор с соот- ветствующей функциональностью, как операция алгебры Д-операторов. Из этого следует, что возможен пере- ход от композиционных к регулярным схемам Д-операторов в процессе описания алгоритма. Представление любых данных через образующие элементы системы 3;D посредством операций ал- гебры данных, назовем схемой данных (СД). Представление любого Д-оператора через образующие элементы системы };D,L,U{ назовем полной схемой этого Д-оператора (ПС). Теоретичні та методологічні основи програмування 33 Процесс разработки алгоритма начинается с этапа проектирования архитектуры программной системы, который играет ключевую роль, так как от качества его реализации в существенной мере зависят все последу- ющие этапы и, в конечном счете, качество программного продукта. На этом этапе решаются две взаимосвязан- ные основные задачи: 1) определяется состав подсистем, образующих алгоритм, и специфицируются обрабатываемые и про- дуцируемые этими подсистемами данные; 2) специфицируются взаимосвязи между этими подсистемами. Учитывая эти задачи подсистему определим следующим образом. Определение 4. Подсистемой назовем Д-оператор )D()P(D iii  , реализующий часть функциональности ал- горитма, обрабатывающий и продуцирующий часть данных, специфицированных на его входе и выходе. Сово- купность информационно связанных подсистем, образующих алгоритм, реализуют всю его функциональность, обрабатывает все данные, специфицированные на его входе, и, с помощью дополнительных (вспомогательных, промежуточных) данных, продуцируют все данные, специфицированные на его выходе. Поскольку алгоритм – это Д-оператор, то для решения приведенных задач запишем его, с учетом опре- деления 4, в виде следующей КС: )()D,(...)()D,()(),( РЕЗИСХ_ k ИСХРЕЗ 11 ИСХ_ 1 ИСХ 1 РЕЗИСХ_ИСХ kk R k RR DPDDPDDADD  . (13) Будем полагать, что данные, специфицированные на входе и выходе алгоритма, являются группами дан- ных и рассмотрим процесс их описания на примере исходных данных. В результате применения к этим данным операции разгруппировки ИСХИСХ 1 ИСХ ,..., sDDD  , (14) разбиваем исходную группу данных на подгруппы, которые необходимо “распределить” между подсистема- ми. Если s=k и каждая полученная группа данных согласована с функциональностью одной из подсистем, то есть могут обрабатываться ими, то данные соответствующим образом распределяются, а процесс описания данных на этом завершается. В противном случае, возможно несколько вариантов описания данных. Если полученные данные не согласуются с функциональностью подсистем, так как степень детализации полученных данных излишняя или s>k, то данные должны быть перегруппированы. Для этого, применив к по- лученным данным операцию группировки следующим образом: ИСХ 1 ИСХ i ИСХ i DD...D s1   ; ………………………… (15) ИСХ r ИСХ i ИСХ i DD...D mp   , где },...,1{ si j  (для всех j), получаем r групп данных с произвольным составом таких, что sr  , то есть ИСХИСХ 1 ИСХ ,..., rDDD  . При kr  и согласованности полученных данных с функциональностью подсистем, процесс их описания на этом завершается. При этом перегруппировке может предшествовать разгруппировка полученных групп данных ИСХИСХ 1 ,..., rDD  или некоторой их части. Если требуемый результат не получен, то процесс описания данных может быть начат сначала (с раз- группировка данных ИСХD ) с целью получения других групп данных, которые, в свою очередь, будут пере- группировываться. Если полученные данные не согласуются с функциональностью подсистем, так как степень детализации данных недостаточна или s<k, то данные необходимо подвергнуть дальнейшей разгруппировке, например, с помощью производной операции (4). В результате некоторые группы данных будут отделены ИСХИСХИСХИСХИСХ 1 ИСХ ,...,,,,...,)( mrprp DDDDDD  (16) и, в случае необходимости, перегруппированы, а группа данных ИСХD может быть перегруппирована отдель- но. Любая из полученных групп данных или они все могут подвергаться дальнейшей разгруппировке и/или пе- регруппировке. В любом случае процесс описания данных продолжается до тех пор, пока количество получен- ных групп данных не будет соответствовать числу подсистем, а функциональность каждой подсистемы не обеспечит обработку специфицированных данных, то есть, не будет согласована с ними. Совершенно аналогично описываются и согласуются с функциональностью подсистем остальные данные ,...,* ИСХ_R1ИСХ_R 1 ИСХ_R kDDD  , (17) РЕЗРЕЗ 1 РЕЗ ,...,* kDDD  , Теоретичні та методологічні основи програмування 34 в результате чего они ( РЕЗ iD и ИСХ_R iD ) специфицируются на входе и выходе каждой i-ой подсистемы. Таким образом, получаем совокупность СД, посредством которых обеспечивается согласованность спе- цифицированных структур данных с числом и функциональность подсистем алгоритма. В общем случае в про- цессе детализации могут быть получены структуры данных, которые будут рассмотрены на следующем этапе. Предложенная КС алгоритма (13), очевидно, не полностью отвечает определению 4, так как в ней специ- фицированы только глобальные данные, в связи с чем, введем понятие локальных данных. Локальными будем называть данные, которые можно рассматривать как инкапсулированные в Д-операторе и которые, являясь вспомогательными, специфицируются на входе и выходе производных Д-операторов для реализации их функциональности. К локальным данным i-ой подсистемы отнесем исх iD – исходные, R iD _исх – вводимые исходные, – вво- димые, W iD – выводимые. R iD Понятие связи в КС введем посредством следующего определения. Определение 5. Д-операторы )()( iii DXD  и )()( jjj DXD  (где i<j), входящие в КС ),()(...)()(...)()()()(...)()( )( 111111 kkkjjjiiiiii DXDDXDDXDDXDDXD)DX(D   прямо связаны, если для них выполняется соотношение  ji DD , а данные jiji DDD   – прямо свя- зывающие эти Д-операторы или прямые связи. В случае, когда  1ii DD , Д-операторы )()( iii DXD  и )()( 111  iii DXD связаны непосредственно, а данные 1ii D  – непосредственно связывающие эти Д-операторы или непосредственные связи. Все связи Д-оператора )()( iii DXD  со всеми следующими за ним и всеми предшествующими ему Д-операторами обозначим 1   k ij ji CB i DD   и 1 1      i j ij CB i DD и назовем правыми и ле- выми его связями. Из определения 5 следует, что каждый Д-оператор )()( iii DXD  может быть связан со всеми следующи- ми за ним Д-операторами и всеми предшествующими Д-операторами. В дальнейшем будем говорить, что неко- торое подмножество выходных данных оператора )()( iii DXD  , который является источником этих данных, поступает на входы Д-операторов )()(),...,()( 111 kkkiii DXDDXD  , которые являются их приемниками. Отме- тим, введенные связывающие данные на данном этапе являются локальными. Учитывая введенные локальные и связывающие данные, КС алгоритма запишем в следующем виде ),,(),,,,,(... ...),,(),,,,,(... ...),,(),,,,( )(),( W k РЕЗ k R k исх_R k исх k ИСХ_R k ИСХ k CB k CB i W i РЕЗ i R i исх_R i исх i ИСХ_R i ИСХ i CB i CB 1 W 1 РЕЗ 11 R 1 исх_R 1 исх 1 ИСХ_R 1 ИСХ 1 РЕЗИСХ_RИСХ DDPDDDDDD DDDPDDDDDD DDDPDDDDD DADD k i      где, CBD1  , CB kD  , так как нет предшествующих и последующих Д-операторов. В результате выполненных построений алгоритм разбит на подсистемы, соответствующие определению 4, у которых специфицированы глобальные, локальные и связывающие данные. В приведенной КС специфи- цированы данные для самого общего случая, который на практике обычно не реализуется. Что бы оценить ре- альное положение вещей остановимся на свойствах специфицированных данных. Поскольку ИСХИСХИСХ ... iii DDD pr   , а семейство множеств ИСХ iD будем трактовать как элемент мно- жества, для исходных глобальных данных выполняется соотношение }) {...}({ ИСХ k ИСХ 1 ИСХ DDD  . (18) Аналогичные соотношения выполняются для остальных глобальных данных: }){ ...}({ ИСХ_R k ИСХ_R 1 ИСХ_R DDD  , (19) }) {...}({ РЕЗ k РЕЗ 1 РЕЗ DDD  . Множества ИСХ jD или RИСХ jD _ могут быть пустыми при условии выполнения соотношения (18) и (19), а РЕЗ jD , при любом j. Пустыми могут быть: множества данных CB jD  и/или CB jD  , если Д-оператор не связан Теоретичні та методологічні основи програмування 35 с предшествующими и/или последующими Д-операторами; исх jD и/или Rисх jD _ , если Д-оператор не имеет ло- кальных исходных данных; R jD и/или W jD , если Д-оператор не осуществляет операций ввода-вывода. Теперь перейдем к следующему этапу, на котором разрабатываются алгоритмы подсистем, для чего каждая из подсистема декомпозируется, а специфицированные у неё данные детализуются. В результате сле- дующий уровень описание алгоритма представляет собой совокупность ПС всех подсистем, которую назовем первым слоем алгоритма. Далее запишем КС всех подсистем, входящих в этот слой, с последовательной нумерацией производных Д-операторов и следующими обозначениями. Полагая, что все специфицированные у всех подсистем (для всех i) данные являются глобальными, множества данных исх i ИСХ i DD  и исх_R i ИСХ_R i DD  обозначим ИС Х_ R i 1D , ИСХ i 1D , связывающие данные CB i 1D  , CB i 1D  , а подсистему – i 1P , где левый верхний индекс указывает уровень (этап) детализации алгоритма. В качестве локальных данных, аналогично вышерассмотренному случаю, бу- дем использовать исх iD2 – исходные, R iD _исх2 – вводимые исходные, r i 2 D – вводимые, w iD2 – выводимые и связывающие данные св i 2D  , св i 2D  . ),,(),,,,,,(... ...),,,,(),,,,,,(... ...),,,,(),,,,,( ),,(),,( CB2W2РЕЗ22r2R2исх_R2исх2ИСХ_R2ИСХ2св2 св i 2CB i 2w i 2W i 2РЕЗ i 22r i 2R i 2исх_R i 2исх i 2ИСХ_R i 2ИСХ i 2св i 2 св i 2CB 1 2w 1 2W 1 2РЕЗ 1 2 1 2r 1 2R 1 2исх_R 1 2исх 1 2ИСХ_R 1 2ИСХ 1 2 CB 1 1W 1 1РЕЗ 1 1 1 1R 1 1ИСХ_R 1 1ИСХ 1 1 11111111111 mmmmmmmmmmm i DDDXDDDDDDD DDDDDXDDDDDDD DDDDDXDDDDDD DDDPDDD       ),,,(),,,,,,,(... ...),,,,( ),,,,,,,(... ...),,,,(),,,,,,( ),,(),,,( CB m 2w2W2РЕЗ22r2R2исх_R2исх2ИСХ_R2ИСХ2св2CB2 св im 2CB im 2w im 2W im 2РЕЗ im 2 m 2r 1m 2R im 2исх_R im 2исх im 2ИСХ_R im 2ИСХ im 2св im 2CB im 2 св 1m 2CB 1m 2w 1m 2W 1m 2РЕЗ 1m 2 1m 2r 1m 2R 1m 2исх_R 1m 2исх 1m 2ИСХ_R 1m 2ИСХ 1m 2CB 1m 2 CB 2 1W 2 1РЕЗ 2 1 2 1R 2 1ИСХ_R 2 1ИСХ 2 1CB 2 1 2222222222222 11111 111111111 1111111111111 DDDDXDDDDDDDD DDDDD XDDDDDDDD DDDDDXDDDDDDD DDDPDDDD mmmmmmmmmmmm i             …………………………………………………………………………………………………………… ),,,(),,,,,,,(... ...),,,,( ),,,,,,,(... ...),,,,( ),,,,,,( ),,(),,,( CB m 2w2W2РЕЗ22r2R2исх_R2исх2ИСХ_R2ИСХ2св2CB2 св im 2CB im 2w im 2W im 2РЕЗ im 2 m 2r im 2R im 2исх_R im 2исх im 2ИСХ_R im 2ИСХ im 2св im 2CB im 2 св 1m 2CB 1m 2w 1m 2W 1m 2РЕЗ 1m 2 1m 2r 1m 2R 1m 2исх_R 1m 2исх 1m 2ИСХ_R 1m 2ИСХ 1m 2CB 1m 2 CB i 1W i 1РЕЗ i 11R i 1ИСХ_R i 1ИСХ i 1CB i 1 i 1-i1-i1-i1-i1-i 1-i1-i1-i1-i1-i1-i1-i1-i1-i 1-i1-i1-i1-i1-i 1-i1-i1-i1-i1-i1-i1-i1-i DDDDXDDDDDDDD DDDDD XDDDDDDDD DDDDD XDDDDDDD DDDPDDDD iiiiiiiiiiii mmmmmmmmmmmm i i                ………………………..…………………………………………………………………………………… ).,,(),,,,,,,(... ...),,,( ),,,,,,,(... ...),,,( ),,,,,,( ),(),,,( w2W2РЕЗ22r2R2исх_R2исх2ИСХ_R2ИСХ2св2CB2 св im 2w im 2W im 2РЕЗ im 2 m 2r im 2R im 2исх_R im 2исх im 2ИСХ_R im 2ИСХ im 2св im 2CB im 2 св 1m 2w 1m 2W 1m 2РЕЗ 1m 2 1m 2r 1m 2R 1m 2исх_R 1m 2исх 1m 2ИСХ_R 1m 2ИСХ 1m 2CB 1m 2 W k 1РЕЗ k 11R k 1ИСХ_R k 1ИСХ k 1CB k 1 1-k1-k1-k1-k 1-k1-k1-k1-k1-k1-k1-k1-k1-k 1-k1-k1-k1-k 1-k1-k1-k1-k1-k1-k1-k1-k kkkkkkkkkkkk mmmmmmmmmmmm i k DDDXDDDDDDDD DDDD XDDDDDDDD DDDD XDDDDDDD DDPDDDD                Описание данных рассмотрим на примере некоторой j-ой подсистемы. Группы данных детализуются аналогично вышерассмотренному случаю (см. (14) – (17)) и записываются в виде СД. Если в результате детализации будет получена структура данных (запись, многомерный или одно- мерный массив записей, многомерный или одномерный массив), то она детализуется посредством операций (2) – (6), (8) – (12). Например, при разгруппировании ИСХ1 jD получили Теоретичні та методологічні основи програмування 36 ИСХ2ИСХ_ЗАП2ИСХ 1 2ИСХ1 ,...,,...,)( srj DDDD  , где ИСХ_ЗАП2 rD – запись. Выполнив дальнейшую детализацию записи, ИСХ_ЗАП r 2ИСХ_ЗАП r 2ИСХ_ЗАП r 2 p1 D,...,D)D(  получаем записи предшествующего уровня вложенности, которые могут быть перегруппированы, в результате чего могут быть включены (все или их часть) в новые группы специфицируемых данных. Эти полученные группы данных и/или полученные записи (перегруппированные, в случае необходимости) распределяются между производными Д-операторами. Поскольку для записей выполняется соотношение ИСХ_ЗАП2ИСХ_ЗАП2ИСХ_ЗАП2 ...** 1 rrr DDD p  , а для исходных данных ИСХ1ИСХ2ИСХ_ЗАП2ИСХ 1 2 ...... jsr DDDD   , то семейство множеств ИСХ2 pD и упорядоченное семейство множеств ИСХ_ЗАП2 rD могут трактоваться как эле- менты множества. Поскольку так же могут детализоваться и остальные глобальные данные, специфицирован- ные в КС, то для них выполняются соотношения (аналогичные (18) – (19)): }{ 1 исх i 2ИСХ j 1 1  j j m mi DD    ; }{ 1 ИСХ_R i 2ИСХ_R j 1 1  j j m mi DD    ; }{ 1 R i 2R j 1 1  j j m mi DD    ; }D{D j 1j m 1mi W i 2W j 1     ; }D{D j 1j m 1mi РЕЗ i 2РЕЗ j 1     ; }D{D j 1j m 1mi CB i 2CB j 1      ; }D{D j 1j m 1mi CB i 2CB j 1      , при условии выполнения которых множества данных CB p 2D  , ИСХ p 2D , ИСХ_R p 2D , R p 2D , РЕЗ p 2D , W p 2D , CB p 2D  , где },...,1{ kmp , могут быть пустыми. Кроме того, CB m CB DD 1 2 1 2 ,...,  ;  CB m CB m kk DD  2 1 2 ,..., 1 и св 1 2D  , св 1 2 1 mD  ,... …, св 1 2 1 kmD  = ; св2 1mD  ,…, св2 kmD  = . Для глобальных данных алгоритма в этом слое выполняются следующие соотношения: }){...}({ ИСХ m 2ИСХ 1 2ИСХ k DDD  ; }){...}({ ИСХ_R m 2ИСХ_R 1 2ИСХ_R k DDD  ; }){...}({ РЕЗ m 2РЕЗ 1 2РЕЗ k DDD  . По поводу связывающих данных будем утверждать следующее. Утверждение. В данном слое алгоритма для глобальных связывающих данных выполняется соотноше- ние   kk m p CB p m j CB j DD 2 2 1 2 1    , а для локальных связывающих данных в каждой КС – соотношения: и   i i i i m mp св p m mj св j DD 2 2 1 1 2 11      . Доказательство очевидно и следует из определения 5. На основе этого утверждения, покажем возможность спецификации информационных связей в слое ал- горитма и КС, детализовав связывающие данные в виде: pjjjj DDD  2 1 22 ,..., , jjjj DDD  2 1 2 1 2 ,...,  , Теоретичні та методологічні основи програмування 37 где левый и правый нижний индекс соответствуют источнику и приемнику данных, и, обозначив для краткости данные, отличные от связывающих, D и D . С учетом введенных обозначений слой алгоритма для случая, когда все подсистемы и все КС, входящие в подсистемы, связаны, запишем следующим образом: ),...,(),...,(),...,,,...,(),...,(... ...),...,,,...,,...,()(),...,()( CB2CB 1 22св2 1 св2 1 св m 2св 1i 2CB m 2CB 1 22св i 2 1 св i 2 1 св m 2 1 св 2 2 1 CB m 2 1 CB 1 2 1 CB 1 2 11 2CB k 1 1 CB 2 1 11 1 11111111k1 1k11 k i mmmmmmmmiiimiii mm DDXDDDDDDXDD DDDDDXDDDPD       ………………………………………………………………………………………………………. ),...,(),...,(... ...),...,,,...,(),...,(... ...),...,,,...,(),...,( ),...,(),...,,( CB k 2CB 1 22св2 1 св2 1 св m 2св 1)( 2CB2CB 1 22св2 )1( св2 1 св m 2 1 св 2 2 1 CB2 1 CB 1 2 11 2CB 1 2CB 1 2 1 CB k CB 1i CB i1 CB i2 CB i1 i1111111111 i111111111 DDXDD DDDDXDD DDDDXDD DDPDDD iiiiiii iiikiiiiiiii iiikiiiiiii mmmmmmm imimimmimmimimimimimm mmmmmmmmmmm iiii             …. ……………………………………………………………………………………………….. ).(),...,(... ...),...,(),...,(... ...*),...,(),...,()(),...,,( 2св2 1 св2 1 св m 2св 1)( 22св2 )1( св2 1 св m 2 1 св 2 2 11 2CB 1 2CB 1 2 1 CB k1 CB k2 CB k1 k1111111 k1111111 DXDD DDXDD DDXDDDPDDD kikk kkkkkkk kkkkkkk mmmm imimimimimimim mmmmmmmkk           В предложенном варианте записи слоя алгоритма специфицированы не только все возможные связи, а источники и приемники данных поставлены в однозначное соответствие. Заключение На описанном этапе разработки поставленная задача решена. Средствами рассматриваемого алгебраиче- ского аппарата согласованно описаны три важнейших аспекта описания алгоритма: поток управления, обраба- тываемые данные и информационные связи. В процессе решения указанной задачи выявлены свойства данных, из которых видно, что все специфицированные данные обрабатываются, а подлежащие обработке специфици- руются. Этот результат естественно переносится и на все следующие этапы, состоящие в повторении показанных действий при сохранении свойств специфицируемых данных. Отличие каждого следующего шага (от преды- дущего) состоит в получении все более “толстых” слоев алгоритма и замене Д-операторов соответствующей функциональности операциями алгебры. После такой замены декомпозиции подвергаются Д-операторы, вхо- дящие в такую операцию. Описанный процесс продолжается до достижения такого уровня детализации, после которого возможен переход от алгоритма к программе, что показано в работе [8]. Из изложенного легко увидеть, что указанная задача решается в рамках нисходящей стратегии проекти- рования алгоритмов. Доказанная в работе [9] теорема о возможности объединения Д-операторов позволяет, проведя рассуждения в порядке обратном вышеприведенному, получить аналогичный результат для восходя- щей стратегии проектирования алгоритмов и программ. 1. Данные в языках программирования: абстракция и типология. Сб. статей / Под ред. В. Агафонова. – М.: Мир, 1982. – 328 с. 2. Bastani F.B., Iyengar S.S. The effect of data structures on the logical complexity of programs // CACM. – 1987. – V. 30, N 3. – P. 250–259. 3. Акуловский В.Г. Основы алгебры алгоритмов, базирующейся на данных // Проблеми програмування. – 2010. – № 2–3. – С.89–96. 4. Акуловский В.Г. Алгебра алгоритмов, базирующаяся на данных // Кибернетика и системный анализ. – 2012. – № 2. – С. 151–166. 5. Дорошенко А.Е., Акуловский В.Г. Алгебра алгоритмов с данными и прогнозирование вычислительного процесса // Проблеми програ- мування.  2011.  № 3.  С. 310. 6. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наукова думка, 1978. – 319 с. 7. Акуловский В.Г. , Дорошенко А.Е. Нисходящее проектирование алгоритмов в рамках алгеброалгоритмического подхода // Математи- ческие машины и системы. – 2012. – № 3. – С. 97–102. 8. Акуловский В.Г. Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов // Проблеми програмування. – 2008.  № 1.  С. 5159. 9. Дорошенко А.Ю., Акуловський В.Г. Висхідне проектування алгоритмів при алгеброалгоритмичному підході // Вісник Київського національного університету імені Тараса Шевченка. Серія фізико-математичні науки, 2012. – Випуск 1. – С. 167–172.

Сoordinated description of algorithms within the framework of algebraic vehicle

Institution

Ähnliche Einträge