СОГЛАСОВАННОЕ ОПИСАНИЕ АЛГОРИТМОВ В РАМКАХ АЛГЕБРАИЧЕСКОГО АППАРАТА

Abstract

Продемонстрирована (в самом общем случае) возможность согласованного описания потоков управления, данных и информационных связей в процессе разработки алгоритмов средствами трехосновной алгебраической системы (алгебры алгоритмов с данными). Показаны свойства получаемых схем алгоритмов. The possibility of the concerted description of management streams is shown in general, 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], “встроены” данные.

Далее приведены некоторые элементы этого алгебраического аппарата необходимые решения указанной задачи.

Упомянутый алгебраический аппарат представляет собой трехосновную алгебраическую систему САА\Д::= {U , L, D}; (алгебру алгоритмов с данными), где U – множество Д-операторов, L – множество Определение 1. Составными данными

будем называть пару D NAj ,З , где З  з1,...,зn – кортеж значений, простыми – d  NAj , з , где з – значение, носитель которых NAj , однозначно идентифицируется определяющий текущее состояние данных.

Используемые далее типы данных соответствуют традиционному для языков программирования понятию и будут обозначаться fi , где fi  F  { f1, f2 ,..., fk } , а F – множество возможных типов данных. Применяя операцию композиции к полученным записям 1D1ЗП*...*1DsЗП  2DЗjП, получаем новую запись второго уровня вложенности, в которую могут быть вложены как первичные, так и производные структуры данных. Продолжая такой процесс можем получать записи nDЗjП с практически неограниченной вложенностью. Получаемые таким образом записи на каждом уровне вложенности могут трактоваться как кортеж семейств {n1Dfi }n2  n2,n1Dfi , к двумерному – трехмерный массив n3,n2,n1Dfi и т. д., на k-ом шаге получаем {.nk-1,...,n2,n1Dfi }nk  nk,...,n2,n1Dfi k-мерный массив.

Распространив операцию итерации данных на множество записей, получаем {DЗП}nnDЗП одномерный массив записей (в дальнейшем массив записей). Применяя эту операцию к массиву записей k раз, получаем многомерный массив записей в виде {.nk-1,...,n1DЗП}nk  nk,...,n1DЗП.

Введенная операция позволила получить производные структуры данных многомерные массивы, одномерные и многомерные массивы записей. Операция композиции распространенная на полученные производные структуры данных, позволяет организовывать записи, включающие в свой состав простые данные, одномерные и многомерные массивы, одномерные и многомерные массивы записей, то есть получать структуры данных произвольной сложности вложенные на произвольную глубину.

Для случая, когда необходимо описывать в виде единого целого произвольно расположенные, в частности, семантически несвязанные данные, введем операцию группировки данных, которую обозначим “  ”. В результате применения этой операции к произвольным структурам данных DS  DS 1DiГ , а в общем случае D1S ...  DpS 1DiГ , получаем

новые данные, называющиеся первичными группами данных. Распространив эту операцию на множество групп 1 D1Г  ... 1DmГ 2 D1Г получаем новую группу данных второго уровня вложенности, в которую могут быть вложены как первичные, так и производные группы.

Элементы группы данных могут быть, как упорядочены, так и не упорядочены, а отличие их от структур данных состоит в том, что на множестве групп данных операция композиции не определена. Последовательное применение операции группировки к группам данных n1D1Г ...  n1DkГ  nDГj позволяет получить вложенность групп данных на практически произвольную глубину.

На любом, начиная со второго уровня вложенности групп данных, они могут трактоваться как семейство множеств nD Гj  {n1 D1Г ,...,n1Dk } таких, что для любого n2 DiГjn1 DiГ допустимо как n2 DiГjn1 DpГ , так и Г n2 DiГjn1 DpГ для всех p  i .

Для детализации данных введем операции. Операция разгруппировки “  ”, применение которой к группе данных

n DiГ n1D1Г ,...,n1DpГ порождает группы данных предшествующего уровня вложенности. В частных случаях и в случае первичной группы данных получаем структуры данных и\или простые данные.

Вторая такая операция – это операция детализации (декомпозиции) данных, обозначенная – “ * ” . Применение этой операции к полученным выше структурам данных выполняется следующим образом: – из многомерного массива записей получаем nk массивов записей *(nk,...,nDЗП)  nk-1,...,n1,nD1ЗП,...,nk-1,...,n1,nDnЗП; k – из одномерного массива записей получаем n записей *(nDЗП)  D1ЗП,..., DnЗП; *n DiЗП n1D1ЗП ,...,n1DmЗП (1) (2) (3) (4) или/и любые другие структуры данных (массивы записей, массивы, простые данные). В случае первичной записи *Dis d1fx ,...,dnfx – кортеж простых данных произвольного типа; – из многомерного массива получаем n k массивов – из одномерного массива получаем кортеж из n простых данных типа fi *(nk,...,n1Dfi )  nk-1,...,n1D1fi ,...,nk-1,...,n1Dfi ;

nk *(nDfi )  d1fi ,..., dnfi .

Приведенные операции позволяют детализовать все возможные структуры данных. В результате такой декомпозиции массивы разбиваются на образующие их компоненты. Однако необходимость осуществлять детализацию сложных глубоко вложенных структур данных требует дополнительных средств. Достаточно легко увидеть, что на основе введенных легко могут строиться производные операции.

В частности, для групп данных операция

r *s (n DiГ )n1D1Г ,...,n1DrГ ,n DiГ ,n1DsГ ,...,n1DpГ , где n DiГ n1DrГ1  ... n1DsГ1 , отделяет r первых и s последних групп данных предыдущего уровня их вложенности. Ограничением на применение этой операции является соотношение r  s . Заметим, что при r  s операции вырождаются в исходную операцию разгруппировки (см. (1)). Заметим так же, что эти операции, очевидно, могут использоваться и в случае, когда детализуемые группы данных включают не только группы, а и любые структуры данных.

Для записей производными операциями детализации данных являются:

* p1, p2,...ps (n DiЗП )n DiЗ1П ,...,n DiЗsП , где n DiЗjП n1Dp1... pj11  ... n1Dp1... pj ; ЗП ЗП

r *s (n DiЗП )n1D1ЗП ,...,n1DrЗП ,n DiЗП ,n1DsЗП ,...,n1DpЗП , где n DiЗП n1DrЗП1 *...*n1 DsЗП1 .

Для массивов и массивов записей, которые в общем многомерном случае обозначим nk ,...,n1 D , производными операциями детализации данных являются: * p1, p2,...ps (sk ,...,s1D jfi ) p1,sk1,...,s1D jf1i ,..., ps,sk1,...,s1D jfsi и * p1, p2,...ps (sk ,...,sn1DiЗП ) p1,sk1,...,sn1DiЗ1П ,..., ps ,sk1,...,sn1DiЗsП , (10) в результате выполнения которых каждый из исходных массивов распадается на s массивов таких, что p1  p2  ...  ps  sk , что является ограничением на применение этой операции.

Эта операция, примененная к одномерным массивам

* p1, p2,...ps (sD jfi ) p1D jf1i ,..., ps D jfsi и * p1, p2,...ps (nsDiЗП ) pn1DiЗ1П ,..., pns DiЗsП , порождает s одномерных массивов, при условии, что p1  p2  ...  ps  s .

Распространив производную операцию (4) на множество массивов, получаем следующий результат: и r *s (sk ,...,s1D jfi )sk1,...,s1D fi ,...,sk1,...,s1D fi ,(sk rs),...,s1Dj fi ,sk1,...,s1D fi ,...,sk1,...,s1D fi

j1 jr jr1 jrs r *s (sk ,...,sn1DiЗП )sk1,.n..,s11DiЗ1П ,...,sk1,.n..,s11DiЗrП (sk rs),...,sn1 DiЗП ,sk1,.n..,s11DiЗrП1 ,...,sk1,.n..,s11DiЗrПs , при условии r  s  sk .

Введенные операции (1)–(12) позволяют разгруппировать (перегруппировать) группы и детализовать структуры данных произвольной сложности и размера вложенные на произвольную. Производные операции, набор которых, очевидно может быть расширен, упрощают процесс детализации сложно организованных данных.

К логическим операциям, определенным на множестве логических условий L, отнесены известные операции дизъюнкция, конъюнкция отрицание со своими таблицами истинности [6]. (5) (6) (7) (8) (9) (11) (12) Фундаментальным элементом описания алгоритмов, в рамках этого аппарата, являются Д-операторы (D) X (D) , обрабатывающие данные и определенные в работе [4] следующим образом.

Определение 2. На входе Д-оператора (D) X (D) специфицировано множество входных данных D (в частном случае простые данные d ), обрабатывая которые он в общем случае изменяет множество выходных (специфицированных на его выходе) данных D (в частном случае простых данных d  ). Для множеств входных и выходных данных таких, что D   и D   , может выполняться как соотношение D  D   (в частности, D  D и D  D ), так и D  D   . В первом случае, изменяются значения подмножества входных данных D  D  (D  D) (в частности, все входные данные, если D  D ). Во втором – значения входных данных остаются неизменными.

Определяющей для дальнейших рассуждений является операция композиции Д-операторов определенная следующим образом. ~ ~ ~ Композиция Д-операторов (операция обозначается “*”) (D)X (D) * (D)X (D) означает последовательное где DИСХ – исходные, DИСХ_R – вводимые исходные данные, DРЕЗ – результирующие данные. При этом DИСХ или DРЕЗ могут отсутствовать, а множество DРЕЗ   .

Рассмотрение процесс разработки алгоритма начнем со следующего требования предъявляемого к этому процессу. Наряду с реализацией известных принципов (формальности, абстрактности, иерархической упорядоченности и т. д.), в процессе разработки необходимо обеспечить, что бы все специфицированные в алгоритме данные были обработаны, а все обрабатываемые – специфицированы.

В качестве основы для организации процесса разработки воспользуемся теоремой, доказанной в работе [7], смысл которой, если отбросить не существенные для рассматриваемого случая подробности, состоит в следующем.

Произвольный Д-оператор (D)X (D) может быть декомпозирован, то есть, представлен в виде эквивалентной ему композиции двух других Д-операторов ( (D) X (D)  (D )X (D ) * ( D)X( D) . Обобщение этого результата позволяет ввести следующую форму представления Д-оператора, (D) X (D)  (D1) X1(D1) * (D2 ) X 2 (D2 ) *...* (Dk ) X k (Dk ) , которая называется его композиционной схемой (КС), в которой (D)X (D) – исходный, а (D1) X1(D1) , (D2 ) X 2 (D2 ) , …, (Dk ) X k (Dk ) – производные Д-операторы.

С другой стороны представление любого Д-оператора через образующие элементы системы {U , L};{1,2} назовем регулярной схемой этого Д-оператора (РСД). При этом в работе [4] показано, что любую операцию из 1 на некотором этапе разработки можно трактовать как Д-оператор, а Д-оператор с соответствующей функциональностью, как операция алгебры Д-операторов. Из этого следует, что возможен переход от композиционных к регулярным схемам Д-операторов в процессе описания алгоритма.

Представление любых данных через образующие элементы системы D;3 посредством операций алгебры данных, назовем схемой данных (СД).

Представление любого Д-оператора через образующие элементы системы {U, L, D}; назовем полной схемой этого Д-оператора (ПС). разбиваем исходную группу данных на подгруппы, которые необходимо “распределить” между подсистемами. Если s=k и каждая полученная группа данных согласована с функциональностью одной из подсистем, то есть могут обрабатываться ими, то данные соответствующим образом распределяются, а процесс описания данных на этом завершается.

В противном случае, возможно несколько вариантов описания данных.

Если полученные данные не согласуются с функциональностью подсистем, так как степень детализации полученных данных излишняя или s>k, то данные должны быть перегруппированы. Для этого, применив к полученным данным операцию группировки следующим образом:

Будем полагать, что данные, специфицированные на входе и выходе алгоритма, являются группами данных и рассмотрим процесс их описания на примере исходных данных.

В результате применения к этим данным операции разгруппировки

DiИ1 СХ ...  DiИs СХ  D1ИСХ ; …………………………

DiИpСХ ...  DiИmСХ  DrИСХ , Процесс разработки алгоритма начинается с этапа проектирования архитектуры программной системы, который играет ключевую роль, так как от качества его реализации в существенной мере зависят все последующие этапы и, в конечном счете, качество программного продукта. На этом этапе решаются две взаимосвязанные основные задачи:

1) определяется состав подсистем, образующих алгоритм, и специфицируются обрабатываемые и продуцируемые этими подсистемами данные; 2) специфицируются взаимосвязи между этими подсистемами. Учитывая эти задачи подсистему определим следующим образом.

Определение 4. Подсистемой назовем Д-оператор (Di)Pi(Di) , реализующий часть функциональности алгоритма, обрабатывающий и продуцирующий часть данных, специфицированных на его входе и выходе. Совокупность информационно связанных подсистем, образующих алгоритм, реализуют всю его функциональность, обрабатывает все данные, специфицированные на его входе, и, с помощью дополнительных (вспомогательных, промежуточных) данных, продуцируют все данные, специфицированные на его выходе.

Поскольку алгоритм – это Д-оператор, то для решения приведенных задач запишем его, с учетом определения 4, в виде следующей КС: (DИСХ , DИСХ_R ) A(DРЕЗ )  (D1ИСХ , D1ИСХ_R )P1(D1РЕЗ ) *...* (DkИСХ , DkИСХ_R )Pk (DkРЕЗ ) . (13) (14) (15) (16) (17) где i j {1,..., s} (для всех j), получаем r групп данных с произвольным составом таких, что r  s , то есть DИСХ  D1ИСХ ,..., DИСХ . При r  k и согласованности полученных данных с функциональностью подсистем, r процесс их описания на этом завершается. При этом перегруппировке может предшествовать разгруппировка полученных групп данных DИСХ ,..., DИСХ или некоторой их части.

1 r Если требуемый результат не получен, то процесс описания данных может быть начат сначала (с разгруппировка данных DИСХ ) с целью получения других групп данных, которые, в свою очередь, будут перегруппировываться.

Если полученные данные не согласуются с функциональностью подсистем, так как степень детализации данных недостаточна или s<k, то данные необходимо подвергнуть дальнейшей разгруппировке, например, с помощью производной операции (4). В результате некоторые группы данных будут отделены p r (DИСХ )  D1ИСХ ,..., DpИСХ , DИСХ , DrИСХ ,..., DmИСХ и, в случае необходимости, перегруппированы, а группа данных DИСХ может быть перегруппирована отдельно. Любая из полученных групп данных или они все могут подвергаться дальнейшей разгруппировке и/или перегруппировке. В любом случае процесс описания данных продолжается до тех пор, пока количество полученных групп данных не будет соответствовать числу подсистем, а функциональность каждой подсистемы не обеспечит обработку специфицированных данных, то есть, не будет согласована с ними. Совершенно аналогично описываются и согласуются с функциональностью подсистем остальные данные * DИСХ_R  D1ИСХ_R 1,..., DkИСХ_R , * DРЕЗ  D1РЕЗ ,..., DkРЕЗ , в результате чего они ( DiРЕЗ и DiИСХ_R ) специфицируются на входе и выходе каждой i-ой подсистемы.

Таким образом, получаем совокупность СД, посредством которых обеспечивается согласованность специфицированных структур данных с числом и функциональность подсистем алгоритма. В общем случае в процессе детализации могут быть получены структуры данных, которые будут рассмотрены на следующем этапе.

Предложенная КС алгоритма (13), очевидно, не полностью отвечает определению 4, так как в ней специфицированы только глобальные данные, в связи с чем, введем понятие локальных данных.

Локальными будем называть данные, которые можно рассматривать как инкапсулированные в Д-операторе и которые, являясь вспомогательными, специфицируются на входе и выходе производных Д-операторов для реализации их функциональности.

К локальным данным i-ой подсистемы отнесем Diисх – исходные, Diисх _ R – вводимые исходные, – вводимые, DiW – выводимые. DiR Понятие связи в КС введем посредством следующего определения. Определение 5. Д-операторы (Di ) X i (Di) и (D j ) X j (Dj ) (где i<j), входящие в КС (D) X(D)  (D1) X1(D1) *...* (Di ) X i (Di) * (Di1) X i1(Di1) *...* (D j ) X j (Dj ) *...* (Dk ) X k (Dk ), k  предшествующими ему Д-операторами обозначим DiCB   i D j ji1 j1 i1  и DiCB   j Di и назовем правыми и левыми его связями.

Из определения 5 следует, что каждый Д-оператор (Di ) X i (Di) может быть связан со всеми следующими за ним Д-операторами и всеми предшествующими Д-операторами. В дальнейшем будем говорить, что некоторое подмножество выходных данных оператора (Di ) X i (Di) , который является источником этих данных, поступает на входы Д-операторов приемниками. Отметим, введенные связывающие данные на данном этапе являются локальными. Учитывая введенные локальные и связывающие данные, КС алгоритма запишем в следующем виде (Di1) X i1(Di1),...,(Dk ) X k (Dk ) , которые являются их (DИСХ , DИСХ_R ) A(DРЕЗ )   (D1ИСХ , D1ИСХ_R , D1исх , D1исх_R , D1R )P1(D1РЕЗ , D1W , D1CB ) *... ...* (DiCB , DiИСХ , DiИСХ_R , Diисх , Diисх_R , DiR )Pi (DiРЕЗ , DiW , DiCB ) *...

...* (DkCB , DkИСХ , DkИСХ_R , Dkисх , Dkисх_R , DkR )Pk (DkРЕЗ , DkW ), где, D CB   , DkCB   , так как нет предшествующих и последующих Д-операторов.

1 В результате выполненных построений алгоритм разбит на подсистемы, соответствующие определению 4, у которых специфицированы глобальные, локальные и связывающие данные. В приведенной КС специфицированы данные для самого общего случая, который на практике обычно не реализуется. Что бы оценить реальное положение вещей остановимся на свойствах специфицированных данных.

Поскольку DiИrСХ  ...  DiИp СХ  DiИСХ , а семейство множеств DiИСХ будем трактовать как элемент множества, для исходных глобальных данных выполняется соотношение Аналогичные соотношения выполняются для остальных глобальных данных:

DИСХ  ({D1ИСХ}... { DkИСХ}) .

DИСХ_R  ({D1ИСХ_R }... {DkИСХ_R }) , DРЕЗ  ({D1РЕЗ}... { DkРЕЗ}) . (18) (19) Множества D ИjСХ или D ИjСХ _ R могут быть пустыми при условии выполнения соотношения (18) и (19), а D РjЕЗ   , при любом j. Пустыми могут быть: множества данных D CjB и/или D CjB , если Д-оператор не связан с предшествующими и/или последующими Д-операторами; D иjсх и/или D иjсх _ R , если Д-оператор не имеет локальных исходных данных; D Rj и/или D Wj , если Д-оператор не осуществляет операций ввода-вывода. связывающие данные 2Diсв , 2Diсв .

Теперь перейдем к следующему этапу, на котором разрабатываются алгоритмы подсистем, для чего каждая из подсистема декомпозируется, а специфицированные у неё данные детализуются. В результате следующий уровень описание алгоритма представляет собой совокупность ПС всех подсистем, которую назовем первым слоем алгоритма.

Далее запишем КС всех подсистем, входящих в этот слой, с последовательной нумерацией производных Д-операторов и следующими обозначениями. Полагая, что все специфицированные у всех подсистем (для всех i) данные являются глобальными, множества данных DiИСХ  Diисх и DiИСХ_R  Diисх_R обозначим 1DiИСХ_R , 1DiИСХ , связывающие данные 1 DiCB , 1 DiCB , а подсистему – 1Pi , где левый верхний индекс указывает уровень (этап) детализации алгоритма. В качестве локальных данных, аналогично вышерассмотренному случаю, будем использовать 2Diисх – исходные, 2Diисх _ R – вводимые исходные, 2 Dir – вводимые, 2Diw – выводимые и (1D1ИСХ ,1D1ИСХ_R ,1D1R )1P1(1DРЕЗ ,1D1W ,1D1CB ) 

1 (2D1ИСХ ,2D1ИСХ_R ,2D1исх ,2D1исх_R ,2D1R ,2D1r )2X1(2D1РЕЗ ,2D1W ,2D1w ,2D1CB,2Diсв ) *... ... *(2Diсв ,2DiИСХ ,2DiИСХ_R ,2Diисх ,2Diисх_R ,2DiR ,2Dir )2X i (2DiРЕЗ ,2DiW ,2Diw ,2DiCB ,2Diсв ) *... ... *(2D mсв ,2DmИСХ ,2DИСХ_R ,2Dmисх ,2Dисх_R ,2DmR ,2Dmr )2X m1 ( Dm

2 РЕЗ ,2DmW ,2DmCB ) 1 1 m1 1 m1 1 1 1 1 1 ... *(2DmC1Bi ,2D mсв1i ,2DmИ1СХi ,2DИСХ_R ,2Dmис1хi ,2Dmис1х_iR ,2DmR1i ,2Dmr11)2X m1i 

m1i (1D2CB ,1D2ИСХ ,1D2ИСХ_R ,1D2R )1P2 (1D2РЕЗ ,1D2W ,1D2CB )  (2DmC1B1,2DmИ1СХ1 ,2DИСХ_R ,2Dmис1х1,2Dmис1х_1R ,2DmR11,2Dmr11)2X m11(2DmРЕ1З1,2DmW11,2Dmw11,2DmC1B1,2D mсв11) *...

m11 ... *(2DmC2B ,2D mсв2 ,2DmИ2СХ ,2DИСХ_R ,2Dmисх ,2Dисх_R ,2DmR2 ,2Dmr2 )2X m2 (2DmРЕЗ ,2DmW2 ,2Dmw2 ,2DmCB2 ) m2 2 m2 2 (2DmРЕ1Зi ,2DmW1i ,2Dmw1i ,2DmC1Bi , Dm1i ) *...

2  св …………………………………………………………………………………………………………… (1DiCB ,1DiИСХ ,1DiИСХ_R ,1DiR )1Pi (1DiРЕЗ ,1DiW ,1DiCB )   (2DmCBi-11,2DmИiС-1Х1,2DmИiС-1Х1_R ,2Dmисi-х11,2Dисх_R 2 2 r 2

mi-11 , DmRi-11, Dmi-11) X mi-11  ... *(2DmCBi-1i ,2D mсвi-1i ,2DmИiС-1Хi ,2DmИiС-1Хi_R ,2Dmисi-х1i ,2Dmисi-х1_Ri ,2DmRi-1i ,2Dmri-1i )2X mi-1i  ... *(2DmCiB,2D mсвi ,2DmИiСХ ,2DmИiСХ_R ,2Dmисiх ,2Dmисiх_R ,2DmRi ,2Dmri )2X mi (2DmРЕiЗ ,2DmWi ,2Dmwi ,2DmCBi ) (2DmРЕi-1З1,2DmWi-11,2Dmwi-11,2DmCBi-11,2D mсвi-11) *...

(2DmРЕi-1Зi ,2DmWi-1i ,2Dmwi-1i ,2DmCBi-1i ,2D mсвi-1i ) *... ………………………..…………………………………………………………………………………… (1DkCB ,1DkИСХ ,1DkИСХ_R ,1DkR )1Pk (1DkРЕЗ ,1DkW )  (2DmCBk-11,2DmИkС-1Х1,2DmИkС-1Х_1R ,2Dmисkх-11,2Dmисkх-1_R1 ,2DmRk-11,2Dmrk-11)2X mk-11  ... *(2DmCBk-1i ,2D mсвk-1i ,2DmИkС-1Хi ,2DmИkС-1Х_iR ,2Dmисkх-1i ,2Dmисkх-1_Ri ,2DmRk-1i ,2Dmrk-1i )2X mk-1i  ... *(2DmCB,2D mсв ,2DmИСХ ,2DИСХ_R ,2Dmисх ,2Dисх_R ,2DmR ,2Dmr )2X mk (2DmРЕЗ ,2DmW ,2Dmw ).

k k k mk k mk k k k k k (2DmРЕk-З11,2DmWk-11,2Dmwk-11,2D mсвk-11) *... (2DmРЕk-З1i ,2DmWk-1i ,2Dmwk-1i ,2D mсвk-1i ) *... Описание данных рассмотрим на примере некоторой j-ой подсистемы.

Группы данных детализуются аналогично вышерассмотренному случаю (см. (14) – (17)) и записываются в виде СД. Если в результате детализации будет получена структура данных (запись, многомерный или одномерный массив записей, многомерный или одномерный массив), то она детализуется посредством операций (2) – (6), (8) – (12). Например, при разгруппировании 1D j ИСХ получили (1D j ИСХ )2DИСХ ,...,2DИСХ_ЗАП ,...,2DИСХ ,

1 r s где 2DИСХ_ЗАП – запись. Выполнив дальнейшую детализацию записи, r *(2DИСХ_ЗАП )2DИСХ_ЗАП,...,2 DИСХ_ЗАП

r r1 rp получаем записи предшествующего уровня вложенности, которые могут быть перегруппированы, в результате чего могут быть включены (все или их часть) в новые группы специфицируемых данных. Эти полученные группы данных и/или полученные записи (перегруппированные, в случае необходимости) распределяются между производными Д-операторами.

Поскольку для записей выполняется соотношение а для исходных данных элементы множества. Поскольку так же могут детализоваться и остальные глобальные данные, специфицированные в КС, то для них выполняются соотношения (аналогичные (18) – (19)): 1DjИСХ 

mj imj11 {2Diисх} ; 1DИСХ_R  j imj11 mj {2DiИСХ_R} ; 1DjR 

mj imj11 {2DiR } ; 1D Wj 

mj imj11 {2 DiW} ; при условии выполнения которых множества данных 1D РjЕЗ  imj11 mj {2 DiРЕЗ} ; 1 D CjB  imj11 mj {2 DiCB} ; 1 D CjB  imj11 mj {2 DiCB} , …, 2D mсвk1 1 =  ; 2D mсв1 ,…, 2D mсв =  .

k Для глобальных данных алгоритма в этом слое выполняются следующие соотношения: где p {1,..., mk } , могут быть пустыми. Кроме того, 2D1CB ,...,2DmCB   ; 2DmCkB11,...,2DmCB   и 2D1св , 2D mсв1 1 ,... 1 k DИСХ  ({2D1ИСХ}  ... {2DmИkСХ}) ; DИСХ_R  ({2DИСХ_R }  ... {2DИСХ_R }) ;

1 mk DРЕЗ  ({2D1РЕЗ}  ... {2DmРЕkЗ}) . По поводу связывающих данных будем утверждать следующее.

Утверждение. В данном слое алгоритма для глобальных связывающих данных выполняется соотношение mk1 2D CjB  k 2D CpB ,

m  j1 p2 а для локальных связывающих данных в каждой КС – соотношения: и mi12D сjв   jmi11 m i 2D сpв .

 pmi12 Доказательство очевидно и следует из определения 5.

На основе этого утверждения, покажем возможность спецификации информационных связей в слое алгоритма и КС, детализовав связывающие данные в виде:

2D j  2jD j1,..., 2jD p , 2D j 12D j ,..., j12D j , где левый и правый нижний индекс соответствуют источнику и приемнику данных, и, обозначив для краткости данные, отличные от связывающих, D и D .

С учетом введенных обозначений слой алгоритма для случая, когда все подсистемы и все КС, входящие в подсистемы, связаны, запишем следующим образом: (D)1P1(1D2CB ,...,1DkCB )  (D)2X1(12DmC1B1,...,12DmCiB11,...,12DmCBk ,12D2св ,...,12D mсв1 ) *...

1 1 ... *(12Diсв ,...,i12Diсв )2X i ( 2iDmC1B1,..., 2iDmCBk , 2iDiсв1,..., 2iD mсв1 ) *(12D mсв ,...,m112D mсв )2X m1 (m12DmC1B1,...,m12DmCB ) 1 1 k ………………………………………………………………………………………………………. (1DiCB ,2 DiCB ,...,i1DiCB )Pi (i DiC1B ,...,i DkCB )  (12DmCiB11,...,mi12DmCiB11)2X mi11(mi112DmCiB1,...,mi112DmCkB ,mi112D mсвi12 ,...,mi112D mсвi ) *...

2  св 2  св 2 2  2  k mi12iD mсвi1(i1) ,...,mi12iD mсвi ) *... ... *(mi11Dmi1i ,...,mi1(i1) Dmi1i ) X mi1i (mi1i DmCiB1,...,mi1i DmCB , ... *(12D mсвi ,...,mi12D mсвi )2X mi (m2iDmCiB1,...,m2iDkCB )

 ... *(12D mсвk ,...,mk 12D mсвi )2X mk (D). …. ……………………………………………………………………………………………….. ... *(12D mсвk1i ,...,mk1(i12)D mсвk1i )2X mk1i (mk12iD mсвk1(i1) ,...,mk12iD mсвk ) *...

(1DkCB ,2 DkCB ,...,k1DkCB )Pk (D) (12DmCkB11,...,mk12DmCkB11)2X mk11(mk112D mсвk12 ,...,mk112D mсвk ) *...

В предложенном варианте записи слоя алгоритма специфицированы не только все возможные связи, а источники и приемники данных поставлены в однозначное соответствие. Заключение

На описанном этапе разработки поставленная задача решена. Средствами рассматриваемого алгебраического аппарата согласованно описаны три важнейших аспекта описания алгоритма: поток управления, обрабатываемые данные и информационные связи. В процессе решения указанной задачи выявлены свойства данных, из которых видно, что все специфицированные данные обрабатываются, а подлежащие обработке специфицируются.

Этот результат естественно переносится и на все следующие этапы, состоящие в повторении показанных действий при сохранении свойств специфицируемых данных. Отличие каждого следующего шага (от предыдущего) состоит в получении все более “толстых” слоев алгоритма и замене Д-операторов соответствующей функциональности операциями алгебры. После такой замены декомпозиции подвергаются Доператоры, входящие в такую операцию.

Описанный процесс продолжается до достижения такого уровня детализации, после которого возможен переход от алгоритма к программе, что показано в работе [8].

Из изложенного легко увидеть, что указанная задача решается в рамках нисходящей стратегии проектирования алгоритмов. Доказанная в работе [9] теорема о возможности объединения Д-операторов позволяет, проведя рассуждения в порядке обратном вышеприведенному, получить аналогичный результат для восходящей стратегии проектирования алгоритмов и программ. 1. 2. 3. 4. 5.

Данные в языках программирования: абстракция и типология. Сб. статей / Под ред. В. Агафонова. – М.: Мир, 1982. – 328 с. 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. Акуловский В.Г. Основы алгебры алгоритмов, базирующейся на данных // Проблеми програмування. – 2010. – № 2–3. – С.89–96. Акуловский В.Г. Алгебра алгоритмов, базирующаяся на данных // Кибернетика и системный анализ. – 2012. – № 2. – С. 151–166. Дорошенко А.Е., Акуловский В.Г. Алгебра алгоритмов с данными и прогнозирование вычислительного процесса // Проблеми програмування.  2011.  № 3.  С. 310.

References