Composition and properties of data specified in compositional schemes of algorithms

The data specified in composite schemes of algorithms are considered. Their composition, structure, properties and the possibility of controlling the correctness of their description are shown.Problems in programming 2013; 2: 3-12

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Akulovsky, V.G., Doroshenko, A.Yu.
Format:	Artikel
Sprache:	rus
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/773
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-773
record_format	ojs
resource_txt_mv	ppisoftskievua/1b/7864a0202b3ae1a30b5d71c969cccd1b.pdf
spelling	pp_isofts_kiev_ua-article-7732025-08-27T13:11:22Z Composition and properties of data specified in compositional schemes of algorithms Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов Akulovsky, V.G. Doroshenko, A.Yu. The data specified in composite schemes of algorithms are considered. Their composition, structure, properties and the possibility of controlling the correctness of their description are shown.Problems in programming 2013; 2: 3-12 Рассмотрены данные, специфицируемые в композиционных схемах алгоритмов. Показан их состав, структура, свойства и возможность контроля корректности их описания.Problems in programming 2013; 2: 3-12 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/773 PROBLEMS IN PROGRAMMING; No 2 (2013); 3-12 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2013); 3-12 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2013); 3-12 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/773/825 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-08-27T13:11:22Z
collection	OJS
language	rus
topic
spellingShingle	Akulovsky, V.G. Doroshenko, A.Yu. Composition and properties of data specified in compositional schemes of algorithms
topic_facet
format	Article
author	Akulovsky, V.G. Doroshenko, A.Yu.
author_facet	Akulovsky, V.G. Doroshenko, A.Yu.
author_sort	Akulovsky, V.G.
title	Composition and properties of data specified in compositional schemes of algorithms
title_short	Composition and properties of data specified in compositional schemes of algorithms
title_full	Composition and properties of data specified in compositional schemes of algorithms
title_fullStr	Composition and properties of data specified in compositional schemes of algorithms
title_full_unstemmed	Composition and properties of data specified in compositional schemes of algorithms
title_sort	composition and properties of data specified in compositional schemes of algorithms
title_alt	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
description	The data specified in composite schemes of algorithms are considered. Their composition, structure, properties and the possibility of controlling the correctness of their description are shown.Problems in programming 2013; 2: 3-12
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/773
work_keys_str_mv	AT akulovskyvg compositionandpropertiesofdataspecifiedincompositionalschemesofalgorithms AT doroshenkoayu compositionandpropertiesofdataspecifiedincompositionalschemesofalgorithms AT akulovskyvg sostavisvojstvadannyhspecificiruemyhvkompozicionnyhshemahalgoritmov AT doroshenkoayu sostavisvojstvadannyhspecificiruemyhvkompozicionnyhshemahalgoritmov
first_indexed	2025-09-17T09:21:20Z
last_indexed	2025-09-17T09:21:20Z
_version_	1843502388725415936
fulltext	Теоретичні та методологічні основи програмування © В.Г. Акуловский, А.Е. Дорошенко, 2013 ISSN 1727-4907. Проблеми програмування. 2013. № 2 3 УДК 519.683 В.Г. Акуловский, А.Е. Дорошенко СОСТАВ И СВОЙСТВА ДАННЫХ, СПЕЦИФИЦИРУЕМЫХ В КОМПОЗИЦИОННЫХ СХЕМАХ АЛГОРИТМОВ Рассмотрены данные, специфицируемые в композиционных схемах алгоритмов. Показан их состав, структура, свойства и возможность контроля корректности их описания. Введение Достаточно давно осознана прин- ципиальная важность роли, которую дан- ные играют в программировании [1, 2]. Более того, часто утверждается [3, 4], что информация о данных для понимания про- грамм важнее, чем информация об управ- лении. Таким образом, в описании алго- ритма наряду с описанием потоков управ- ления должны быть отображены и данные. При этом роль данных и их влияние на процесс проектирования алгоритмов в рамках известных алгебраических аппара- тов изучены и используются далеко недо- статочно. Для изучения влияния данных на процесс проектирования алгоритмов они были формализованы следующим образом [5]. Определение 1. Данными называ- ется пара N,ЗD  , где N – носитель дан- ных, З – кортежей значений, носителем которых является N . На каждом шаге вычислительного процесса носитель со- держит (хранит) некоторый (текущий) кортеж значений данных, в частности, эти значения могут быть неопределенны- ми. Для того, что бы “имплантировать” данные в алгебраический аппарат, извест- ная модель ЭВМ Глушкова дополнена внешней средой (ВС). Внешняя среда – память и внешние устройства представляют собой множество данных   },...,{ 1 n ВУПВС DDDDD  , харак- теризующиеся в каждый момент времени некоторым множеством значений, кото- рые, изменяются в ходе вычислительного процесса. На основе модифицированной мо- дели ЭВМ авторами предложена система алгоритмических алгебр (САА/Д) [5 – 7], представляющая собой трех-основную ал- гебраическую систему <U,L,D,>, осно- вами которой являются множество Д- операторов U, множество логических условий L и множество данных D, а 321  – её сигнатура, состоя- щая из 1 – логических операций, прини- мающих значения на множестве L, множе- ства 2 – операций, принимающих значе- ния на множестве Д-операторов, и 3 – операций, принимающих значения на множестве данных D. Д-операторы – это операторы вида    DOD  со специфицированными на входе и выходе данными такими, что ВСDD и ВСDD  , чем и обусловлено использование названия Д-оператор. Такой Д-оператор обрабатывает данные, т.е. анализирует и преобразует, изменяя их значения. Одна из форм описания алгорит- мов – композиционные схемы (КС) [6], в которых для описания алгоритмов исполь- зуется операция (в САА\Д операция обо- значается “”) композиции Д-операторов        222111 DXDDXD  , означающая последовательное выполне- ние сначала Д-оператора    111 DXD  затем Д-оператора    222 DXD  . С помощью КС реализуются две стратегии проектирования алгоритмов нисходящая и восходящая [8, 9]. В дан- ном случае рассмотрим первую – более распространенную стратегию, в рамках Теоретичні та методологічні основи програмування 4 которой исходный Д-оператор    DOD  декомпозируется, а специфицированные на его входе и выходе данные детализиру- ются, в результате чего он представляется в виде КС:             ...** 222111 DODDODDOD     ,... kkk DOD  где    ,111 DOD         kkk DODDOD  ,,222  – производные Д-операторы, полученные в результате декомпозиции исходного. Одна из основных задач, решаемых в процессе описания алгоритмов в виде КС – это спецификация данных на входах и выходах производных Д-операторов. Актуальность этой задачи обусловлена тем, что наличие таких спецификаций для каждого Д-оператора на каждом уровне представления алгоритма являются необ- ходимым условием для перехода к следу- ющему его уровню, т. е. необходимым условием для определения функциональ- ности производных Д-операторов, получа- емых в результате декомпозиции исходно- го. При этом данные на входе и выходе Д-оператора специфицируются однократ- но, т.е. дублирование спецификаций недо- пустимо. Сложность указанной задачи обу- словлена тем, что производные Д-опера- торы, входящие в КС, обрабатывают гло- бальные, специфицированные на входе и выходе исходного Д-оператора, данные как “автономно”, так и “коллективно”. То есть, в общем случае каждый из произ- водных Д-операторов, с одной стороны, обрабатывает данные независимо от дру- гих производных Д-операторов. С другой – обработка множества (подмножества) глобальных данных, начатая некоторым Д-оператором    iii DOD  , продолжается и\или завершается в результате выполне- ния другого Д-оператора    jjj DOD  , где j>i. Таким образом, в последнем случае обработка данных осуществляется некото- рой последовательностью Д-операторов, в которой результат выполнения    iii DOD  подвергается дальнейшей обработке Д- оператором    jjj DOD  и может продол- жаться несколькими следующими Д- операторами. Не все и не всегда специфицируе- мые данные изменяются в результате об- работки. Это обусловлено тем, что изме- нение данных зависит от некоторых усло- вий, полученных в результате их анализа и “скрытых” внутри Д-оператора. Кроме того, для обработки глобаль- ных данных могут использоваться и, как правило, используются вспомогательные (локальные) данные, которые служат для преобразования входных глобальных дан- ных в выходные, но сами таковыми не яв- ляются. То есть, производные Д-опера- торы обрабатывают и продуцируют как глобальные, так и локальные данные в лю- бых сочетаниях. Источниками и приемни- ками (носителями) этих данных часто вы- ступают внешние устройства (ВУ), в част- ности, внешняя память (файлы). Из вышеизложенного очевидно, что решение указанной задачи не тривиально и предполагает изучение состава, структу- ры и свойств специфицируемых данных. Этому и посвящена данная работа, из дальнейшего изложения которой будет видно, что специфицируемые данные имеют достаточно сложный состав и структуру. Очевидно, что спецификация дан- ных должна быть выполнена таким обра- зом, чтобы обеспечить корректность пе- рехода от исходного Д-оператора к произ- водным, т.е. возможность получения ре- зультата совпадающего с результатом, продуцируемым исходным Д-оператором. Поскольку на рассматриваемом уровне представления алгоритма решить задачу корректности такого перехода не пред- ставляется возможным, в данной работе рассматриваются один из её аспектов, а именно, контроль корректности специфи- кации данных. Свойства данных в композиционных схемах алгоритмов Прежде чем приступить к изучению состава и структуры данных в КС, огово- рим некоторые особенности обозначений, которые будем далее использовать. Теоретичні та методологічні основи програмування 5 В соответствии с определением 1, значения специфицируемых данных изме- няются (могут изменяться) в ходе вычис- лительного процесса, а на некоторых его этапах могут быть не определены. Отсюда следует, что специфицируются, фактиче- ски, носители данных. Учитывая это в данной работе под теоретико-множествен- ными операциями, определенными на множествах данных, будем понимать опе- рации над их носителями. В частности, под соотношением DD  будем пони- мать совпадение множеств носителей дан- ных D , D . В том случае, когда будем го- ворить о равенстве данных, понимая под этим равенство как множества носителей, так и множества значений, будем исполь- зовать символ “” ( DD  ). В случае сов- падения множеств носителей при несовпа- дении множеств значений – символ “ ” ( DD  ). Теперь определим некоторые виды специфицируемых данных, которые в дальнейшем будем использовать. Определение 2. Данные, специфи- цируемые на входе и выходе Д-оператора    DOD  , будем называть: D входными или обрабатываемыми, D – выходными или продуцируемыми. Для множеств, спе- цифицируемых данных, допустимо как соотношение   DD (в частности, DD  и DD  ), так и   DD . Обрабатываемые данные изменяются (мо- гут изменяться) в результате обработки. Входные данные DDC  такие, что DDC и CD не изменяется Д- оператором    DOD  ни при каких усло- виях и ни при каких значениях данных D , будем называть используемыми (в отличие от обрабатываемых). Определение 3. Данные, носителя- ми которых являются некоторые множе- ства ВУ R, с которых хранимые значения переносятся (копируются) в память, будем обозначать RD и называть вводимыми, и W, в которые хранимые значения перено- сятся (копируются) из памяти на ВУ, – WD и выводимыми. Вводимые и выводи- мые данные специфицируются, соответ- ственно, на входе DDR  и выходе DDW  произвольного Д-оператора. Множества RD и\или WD могут быть пустыми ( RD и\или WD ), т.е. вводимые и\или выво- димые данные могут отсутствовать. Общий случай спецификации дан- ных в КС определим исходя из вышепри- веденных аспектов обработки данных и определения 2. Определение 4. Глобальными для КС             222111 DODDODDOD     ,... kkk DOD  являются данные DDDG  , специфицированные на вхо- де и выходе исходного Д-оператора. На входе и выходе любого производного Д- оператора    iii DOD  , специфицируются как локальные, так и глобальные данные, то есть L i G ii DDD  , L i G ii DDD  , где GG i G i DDD , , LL i L i DDD , . Глобальные данные такие, что DDD G k G  )...( 1 , DDD G k G  )...( 1 , а локальные – такие, что )...( 11 L k L k LLL DDDDD  . При этом локальные данные инкапсулиро- ваны в КС, то есть определяются в данной КС, невидимы и недоступные в других КС данного уровня и на предшествующих уровнях описания алгоритма, и GL DD  . По поводу данных, введенных в определении 4, отметим следующее. Исходный Д-оператор на предше- ствующем уровне детализации алгоритма рассматривался как производный, а произ- водные Д-операторы на следующем уровне детализации будут играть роль ис- ходных. При этом, глобальные данные, являющиеся таковыми на данном уровне описания алгоритма, на предшествующем уровне являлись локальными. Локальные данные на следующем уровне детализа- ции алгоритма играют роль глобальных. Исходя из того, что, в соответствии с определением 3, данные могут являться или содержать вводимые и выводимые Теоретичні та методологічні основи програмування 6 данные, определим спецификации вводи- мых и выводимых данных с учетом опре- деления 4. Определение 5. Вводимые RD rR DD  и выводимые wW DDD W  дан- ные делятся на глобальные   GWR DDD  и локальные   Lwr DDD  . Глобальные, специфицируемые на входе и выходе как исходного DD R , DD W  , так и любого производного Д-оператора i R i DD  , i W i DD  такие, что   RR k R DDD  ...1 и   W k W DD ...1 WD . Локальные Lw i r i DDD , , специ- фицируемые только на входе и выходе производных Д-операторов i r i DD  , такие, что rr k r DDD  )...( 1 ,  ...1 wD  ww k DD ... . Исходя из того, что Д-операторы взаимодействуют в процессе обработки данных, определим понятие информаци- онной связи. Определение 6. В КС Д-операторы    iii DOD  и    jjj DOD  (j>i) назовем информационно связанными (в дальней- шем связанными), если для специфициро- ванных у них данных выполняется со- отношение  ji DD , в противном случае эти Д-операторы не связаны. Данные  jiji DDD  назовем связывающими, ес- ли при обозначении их на выходе i-го Д- оператора ji D  , а на входе j-го – ji D  , вы- полняется соотношение jiji DD   . Если это соотношение не выполняется, то ji D не являются связывающими данными. Данные, связывающие Д-оператор    iii DOD  со всеми предшествующими iii СВ i DDD 111 ...  и всеми последующими kiii СВ ki DDD   ...1 Д-операторами, назо- вем связывающими Д-оператор    iii DOD  , соответственно, слева и спра- ва. Данные kk СВ k DDD 1211 ...  назовем связывающими Д-операторы в КС. Отметим, что в данной работе глав- ным образом рассматриваются локальные связи, т.е. связи внутри КС. Теперь, определим множества гло- бальных данных, обрабатываемых произ- водными Д-операторами автономно. Эти данные назовем собственными. Определение 7. Собственные дан- ные i СБ i DD  и i СБ i DD  , специфицирован- ные на входе и выходе любого i-го Д- оператора такие, что i СБ i СБ i DDDD  , i СБ i СБ i DDDD  и DDDD СБСБ k СБ  )...( 1 , DDDD СБСБ k СБ  )...( 1 . По поводу определения 7 отметим, что данные D и D на предшествующем уровне детализации алгоритма включали данные, связывающие исходный Д-опе- ратор    DOD  с другими Д-операторами этого предшествующего уровня. При переходе к текущему уровню описания алгоритма все Д-операторы предшеству- ющего уровня детализуются и представ- ляют собой композиции производных Д-операторов с сохранением вышеупо- мянутых связей. Функцию связывающих производные Д-операторы данной КС с производными Д-операторами других КС на данном уровне детализации алгорит- ма выполняют собственные данные СБ iD и СБ iD . Спецификации собственных дан- ных, таким образом, позволяет специ- фицировать глобальные связи между все- ми КС, описывающими алгоритм на дан- ном уровне его детализации. В данной работе глобальные связи детально не рас- сматриваются. Будем полагать, исходя из опре- делений 4 – 7, что данные, специфици- руемые на входе и выходе Д-оператора, представляют собой семейства множеств. Исходный Д-оператор при этом записы- вается в виде:    WR DDODD ,,  , (1) а производный – в виде: Теоретичні та методологічні основи програмування 7    СВ ki СБ iii СВ i СБ ii DDDODDD WR ,,,, 1  . Для того, чтобы обеспечить упомя- нутое во введении требование об отсут- ствии дублирований в спецификациях данных, необходимо эти данные детализо- вать таким образом, чтобы для любых множеств данных, полученных в результа- те детализации и специфицируемых на входе и выходе любого производного i-го Д-оператора, выполнялось  )( a i b i DD . Для детализации состава данных, специфицируемых на входе и выходе i-го производного Д-оператора, покажем нали- чие некоторых их свойств, предварительно записав производный Д-оператор с учетом определения 5, в виде:    ,,,, 1 W ii СВ i СБ i r i R i DODDDD СВ ki СБ i w i DDD ,,,  . (2) Начнем рассмотрение с выводимых данных, для общего случая которых будем утверждать следующее. Утверждение 1. Выводимые дан- ные i w i W i DDD , включают подмноже- ства W i CBW ki DD _ , w i CBw ki DD _ , кото- рые входят в состав данных, связывающих Д-оператор    iii DOD  справа CB ki CBw ki CBW ki DDD  __ , . Доказательство. Если для данных, специфицированных на входе любого Д- оператора    sss DOD  (s>i), выполняется   cвW sis W i DDD _ и   cвw sis w i DDD _ , то, поскольку, в соответствии с определе- нием 3, W iD и w iD копируются из памяти на ВУ и, таким образом, их значения не изменяются, то есть выполняется cвW si cвW si DD __   , cвw si cвw si DD __   , в соот- ветствии с определением 6, эти данные являются связывающими. Так как очевидно, что приведенные рассуждения справедливы для всех s>i, то )......( ___ 1 _ cвW ki cвW si cвW ii CBW ki DDDD   и )......( ___ 1 _ cвw ki cвw si cвw ii CBw ki DDDD   , в соответствии с определением 6, входят в состав данных, связывающих Д-оператор    iii DOD  справа CB ki CBw ki CBW ki DDD __ , . Утверждение доказано. Следствие. Из соотношения kiii СВ ki DDD   ...1 (см. определение 6) следует, что для лю- бых i и j выполняется ji cвw ji cвW ji DDD __ , . Теперь покажем наличие некоторых свойств, которыми в общем случае обла- дают собственные данные. Утверждение 2. Собственные дан- ные i СБ i DD  включают подмножество данных СБ i СВСБ ki DD  _ , входящие в со- став связывающих Д-оператор    iii DOD  справа CB ki СВСБ ki DD _ при условии, что эти данные являются используемыми. При этом, данные CBСБ ki свСБ si DD __  (s>i) свя- зывают i-ый Д-оператор с любыми следу- ющими за ним Д-операторами, на входе которых эти данные специфицированы. Доказательство. Пусть для дан- ных, специфицированных на входе Д- оператора    sss DOD  (s>i), выполняется s СБ i cвСБ si DDD _ . Поскольку cвСБ si D _ , в соответствии с условием утверждения, используемые данные, т.е. в соответствии с определени- ем 2, они не изменяются никаким Д- оператором, то выполняется СБ i cвСБ si cвСБ sis DDDD  __  и, в соответствии с определением 6, эти данные являются связывающими. Очевидно, что приведенные рас- суждения справедливы для любого s>i, от- куда следует   СВСБ ki cвСБ ki cвСБ si cвСБ ii DDDD ____ 1 ......  . В соответствии с определением 6, дан- ные СВСБ ki D _ входят в состав связываю- щих Д-оператор    iii DOD  справа CB ki СВСБ ki DD  _ . Теоретичні та методологічні основи програмування 8 Теперь предположим, что на входе    ppp DOD  и    sss DOD  специфициро- ваны одни и те же данные, связывающие эти Д-операторы с    iii DOD  . То есть CBСБ ki свСБ si свСБ pi DDD ___ ,  и свСБ si свСБ pi DD __  при i<p<s. Поскольку из определения 6 известно, что свСБ pi свСБ pi DD __   , а по усло- вию утверждения свСБ pi D _ – используемые данные, то из свСБ si свСБ pi DD __  следует, свСБ si свСБ pi DD __   . Откуда, в свою очередь, следует, что i-ый Д-оператор, на выходе которого данные обозначены свСБ spiD _ , , свя- зан с p-ым и s-ым  свСБ pi свСБ spi DD __ ,  свСБ si D _  . Очевидно, что полученный резуль- тат легко обобщить на случай, когда дан- ные свСБ kiiD _ ,...,1 связывают i-ый Д-оператор с любыми (в частности, со всеми) следую- щими за ним Д-операторами, на входах которых эти данные специфицированы. Утверждение доказано. Следствие. Из соотношения kiii СВ ki DDD   ...1 (см. определение 6) следует, что для любых i и j выполняется ji cвСБ ji DD  _ . Отметим, что данные СВСБ ki D _ иг- рают как роль собственных (глобальных связывающих) данных, так и локальных связывающих данных. Для дальнейшей детализации дан- ных на выходе Д-оператора покажем наличие ещё одного свойства выводимых данных. Утверждение 3. Глобальные выво- димые данные Д-оператора    iii DOD  входят в состав собственных    СБ i W i DD . Доказательство аналогично доказа- тельству утверждения 1 с тем отличием, что собственные данные СБ iD рассматри- ваются как глобальные связывающие дан- ные (о чем выше упоминалось), а   СБW i СБ i W i DDD _  . Следствие. Из утверждения 3 с учетом утверждений 1, 2 и следствий из них легко увидеть, что имеют место гло- бальные данные, являющиеся выводимы- ми, собственными и связывающими )( __ СВ ki СБ i W i СВСБW i DDDD  и для любых i и j выполняется ji cвСБW ji DD  __ . Для исключения дублирования спе- цифицируемых данных, исходя из утвер- ждений 1 – 3, введем следующие их мно- жества:   СБ i CB ki W i W i DDDD  \ , (3)  CB ki w i w i DDD \ , (4)  CB ki W i СБ i СБ i DDDD  (\ , (5) а из следствий из этих утверждений мно- жество  kiii CB ki DDD   ...1 , (6) где   cвСБW ji cвw ji cвW ji cвСБ jijiji DD DDDD ___ __ \   (i<j). В соответствии с утверждениями 1 – 3, учетом (3) – (6), данные, специфи- цируемые на выходе i-го Д-оператора, представим в виде следующего семейства множеств:  ,,,,, ,,,,, ____ __ СB ki CBСБW ji CBw ki CBW ki СВСБ ki СБW ki СБ i w i W ii DDDD DDDDDD   (7) а данные, связывающие Д-оператор спра- ва, представим в виде:   .___ __ CBСБW ji CBw ki CBW ki СВСБ ki CB ki CB ki DD DDDD   (8) Полученный результат позволяет перейти к рассмотрению данных на входе i-го производного Д-оператора по поводу которых будем утверждать следующее. Теоретичні та методологічні основи програмування 9 Утверждение 4. Данные СВ iD1 , свя- зывающие i-ый Д-оператор слева, вклю- чают множество связывающих данных CBW iD _ 1 , CBw iD _ 1 , СВСБ iD _ 1 , CBСБW ji D __ . Доказательство. В соответствии с (8) и следствиями из утверждений 1 – 3, на выходе Д-оператора    ppp DOD  (p<i) присутствует множество данных cвW ip D _ , , cвw ip D _ , cвСБ ip D _ , cвСБW ji D __ СB kp D , связывающих этот Д-оператор справа. Ис- ходя из определения 6, легко увидеть, что при p<i  СB i СB kp DD 1 и СB i cвСБW ip cвСБ ip cвw ip cвW ip DDDDD 1 _____ ,,,  . Если рассмотреть все Д-операторы, для которых выполняется p<i, получаем:   ,...... _ 1 _ 1 __ 1 CBW i cвW ii cвW ip cвW i DDDD     ,...... _ 1 _ 1 __ 1 CBw i cвw ii cвw ip cвw i DDDD     CBСБ i cвСБ ii cвСБ ip cвСБ i DDDD _ 1 _ 1 __ 1 ......   ,   ....... __ 1 __ 1 ____ 1 CBСБW i cвСБW ii cвСБW ip cвСБW i DDDD   Поскольку, в соответствии со след- ствиями из утверждений 1 – 3, для любых i и j выполняется ji cвСБW ji cвСБ ji cвw ji cвW ji DDDDD  _____ ,,, то, очевидно, .,,, 1 __ 1 _ 1 _ 1 _ 1 CB i CBСБW i CBСБ i CBw i CBW i DDDDD  Утверждение доказано. Чтобы исключить дублирование специфицируемых данных, исходя из утверждений 1 – 3 и следствий из них, введем следующее их множество:  iii CB i DDD  111 ... , где    . \ ___ __ cвСБW ip свw ip свW ip свСБ ipipip DD DDDD   В соответствии с утверждением 4, данные, связывающие i-ый Д-оператор слева, представим в виде:  .__ 1 _ 1 _ 1 _ 111 CBСБW i CBw i CBW i СВСБ i CB i CB i DD DDDD   (9) В соответствии с (2) и (9), данные, специфицируемые на входе i-го Д- оператора, представим в виде следующего семейства множеств:  .,,, ,,,,, __ 11 _ 1 _ 1 _ 1 CBСБW i CB i CBw i CBW i СВСБ i СБ i r i R ii DDD DDDDDD   (10) Исходя из соотношений (7), (10), запишем Д-оператор, со специфицирован- ными на входе и выходе данными,    .,,, ,,,,, ,,,,, ,,,,, ___ ___ 1 __ 1 _ 1 _ 1 _ 1 СB ki CBСБW ki CBw ki CBW ki СВСБ ki СБW i СБ i w i W ii CB i CBСБW i CBw i CBW i СВСБ i СБ i r i R i DDD DDDD DDODDD DDDDD    (11) При этом по построению и в соот- ветствии с определениями 4 – 7, для спе- цифицируемых данных выполняются со- отношения:   , 1 __ 1 _ 1 _ 1 _ 1   CB i CBСБW i CBw i CBW i СВСБ i СБ i r i R i DDD DDDDD   , ____ __   СB ki CBСБW ki CBw ki CBW ki СВСБ ki СБW i СБ i w i W i DDDD DDDDD т.е. все данные специфицируются одно- кратно (не дублируются). В итоге покажем наличие особен- ностей в спецификации данных для перво- го и последнего в КС Д-операторов. Утверждение 5. На входе первого    111 DOD  и последнего    kkk DOD  в КС Д-операторов спецификации связываю- щих данных отсутствуют. Доказательство очевидно и вытека- ет из определения 6, так как для первого Д-оператора отсутствуют предшествую- щие, а для последнего последующие Д- операторы. Исходя из (1), (2), (11) и утвержде- ния 5 запишем КС в виде: Теоретичні та методологічні основи програмування 10                 .,,,, ,,,,,, ................................................... ,,, ,,,,,, ,,,,,, .................................................. ,,,, ,,,,,,, ,, _ 1 _ 1 _ 1 _ 1 __ __ 1 _ 1 _ 1 _ 1 1 _ 1 _ 1 _ 1 _ 11111111 СБW k СБ k w k W kk CB k CBw k CBW k СВСБ k СБ k r k R k СB ki CBw ki CBW ki СВСБ ki СБW i СБ i w i W ii CB i CBw i CBW i СВСБ i СБ i r i R i СB k CBw k CBW k СВСБ k СБWСБwWСБrR WR DDDDOD DDDDDD DDD DDDDDOD DDDDDD DDDD DDDDODDD DDODD       (12) В результате выполненных постро- ений показана возможность специфика- ции данных на входах и выходах про- изводных Д-операторов, входящий в КС, соответствующей сформулированной за- даче. Кроме того, могут быть специфи- цированы связи между Д-операторами. В этом случае, рассматривая связываю- щие данные, в соответствии с определе- нием 6, выражение (12) запишем в виде:                .,, ,,,,,,, ................................................. ,,,, ,,,,,,,, ................................................. *,...,,...,, ,,,,,,, ,, _ 11 1 _ 11 1121 _ 11111111 СБW k СБ k w k W kkkkk СБ k r k R k kiii СБW i СБ i w i W iiiii СБ i r i R i ki СБWСБwWСБrR WR DD DDODDDDD DDD DDDODDDDD DDD DDDDODDD DDODD                 Отметим, что спецификации данных, в частности, связывающих могут иметь раз- личную степень детализации, что легко увидеть из изложенного. Помимо вышеприведенных свойств специфицируемых данных имеют место такие свойства, которые ограничивают возможности спецификаций. Перейдем к рассмотрению данных свойств, которое начнем с вводимых и выводимых данных. Утверждение 6. Вводимые данные не могут быть связывающими  СВ kDDR 1 . Доказательство построим от про- тивного и рассмотрим некоторые свя- зывающие данные СВ ip DD 1i , продуци- руемые Д-оператором    ppp DOD  (p<i), для которых, в соответствии с опреде- лением 6, выполняется соотношение ii DD pp   . Предположим, что   iDD p R i  и    iDD p r i . Поскольку, в соот- ветствии с определением 3, данные R iD копируются с ВУ в память, значения под- множества данных iDD p R i  , продуци- руемых Д-оператором    ppp DOD  , бу- дут изменены. То есть, при сделанном предположении приходим к противоре- чию, так как получаем ii DD pp   и подмножество данных iDD p R i  , в соот- ветствии с определением 6, не являющих- ся связывающими. Аналогично рассуждая, к такому же противоречию придем в случае локальных вводимых данных r iD . В результате сделанные предполо- жения недопустимы, т.е.    iDD p R i и    iDD p r i . Очевидно, что, таким же образом рассуждая, аналогичный результат полу- чим для всех связывающих данных СВ iij DD 1 при любых j и i (j<i). Таким образом,  СВ i R DD 1 ,  СВ iDDr 1 и  СВ iDDR 1 , т.е. вводимые данные не бывают связывающими слева. Поскольку, в соответствии с опре- делением 5, вводимые данные не специ- фицируются на выходе Д-оператора, то они для любого Д-оператора не бывают связывающими справа  СВ ki DDR , от- куда следует, что  СВ kDDR 1 . Утверждение доказано. Теоретичні та методологічні основи програмування 11 Утверждение 7. Вводимые данные не могут быть собственными  СБDDR . Доказательство. Если предполо- жить, что  СБ ii DDR , то, поскольку, в соответствии с определением 3, данные R iD копируются с ВУ в память, значения подмножества данных СБ ii DDR  будет изменено. В результате чего получим про- тиворечие с определением 7, так как в этом случае i СБ i СБ i DDDD  . К такому же противоречию придем при всех i, и, таким образом,  СБDDR . Утверждение доказано. Утверждение 8. Локальные выво- димые данные не могут быть собственны- ми  СБw DD . Доказательство очевидно, так как Lw DD  , GСБ DD  и  LG DD (см. определения 4, 5, 7). Теперь остановимся на локальных данных. Утверждение 9. Локальные данные бывают только вводимыми, выводимыми и связывающими. Доказательство очевидно и следует из (11) и утверждения 8. Утверждение 10. Любые связыва- ющие данные, за исключением СВСБ kiD _ , не могут связывать i-ый Д-оператор бо- лее чем с одним следующим за ним Д-оператором. Доказательство. СВСБ kiD _ является исключением, в соответствии с утвержде- нием 2. Предположим, что для связываю- щих данных pi D  , si D  (i<p<s), специфи- цированных на входах соответствующих Д-операторов, выполняется соотношение sipi DD   , т.е. специфицируются одни и те же данные. pi D  специфицированы на вхо- де p-го Д-оператора и для них в соответ- ствии с определением 6 выполняется pipi DD   . Поскольку, в соответствии с определением 2, pi D  обрабатываемые и могут изменяться, то, в случае такого из- менения, sipi DD   , откуда последует, sipi DD   и, в соответствии с определением 6, si D  не будут данными, связывающими i-ый и s-ый Д-операторы. Таким образом, пришли к противоречию, к которому, оче- видно, будем приходить при всех s>p. К тому же противоречию, очевидно, придем при рассмотрении всех остальных (см. (11)) связывающих данных CBСБW i CBw i CBW i СВСБ i DDDD __ 1 _ 1 _ 1 _ 1 ,,, . Поскольку во всех возможных слу- чаях связывающих данных приходим к противоречию, то сделанное предположе- ние не соответствует действительности и утверждение доказано. Полученные в утверждениях 6 – 10 свойства специфицируемых данных будем трактовать как ограничения на специфика- ции. Заключение В процессе выполнения данной работы рассматривался общий случай спецификации данных на входах и вы- ходах производных Д-операторов, входя- щих в КС. Результатом является возмож- ность записывать КС алгоритмов со спе- цифицированными данными. Наличие спецификаций позволяет определить функциональность каждого Д-оператора и осуществить их декомпозицию, т.е. позво- ляет выполнить переход к следующему уровню представления алгоритма. При этом детализация рассматриваемых дан- ных доведена до такой степени, при ко- торой спецификации данных не дублиру- ются. Иначе говоря, сформулированная задача решена с учетом специфики обра- ботки данных. Выше отмечено, что спецификация данных может осуществляться с различной степенью детализации, причем данная степень может задаваться в зависимости от решаемой задачи. Кроме того, весьма существенным результатом является воз- можность спецификации информационных Теоретичні та методологічні основи програмування 12 связей между Д-операторами, которые так же могут быть детализованы. Что касается корректности вы- полнения спецификации данных, то для контроля над ней могут использоваться как проверка соответствия свойствам, заданным определениями 1 – 7 и утвер- ждениями 1 – 5, так и проверка удовлетво- рения ограничений, заданных утверждени- ями 6 – 10. Дальнейшее изучение свойств спе- цифицируемых данных, в частности, даль- нейшая их детализация, распространение полученных результатов на описание ал- горитмов, выполненное в виде совокупно- сти КС, является направлением будущих исследований. 1. Данные в языках программирования: абстракция и типология. Сб. статей / Под ред. В. Агафонова.  М.: Мир, 1982. – 328 с. 2. Турский В. Методология программирова- ния.  М.: Мир, 1981.  264 с. 3. Шнейдерман Б. Психология программиро- вания: человеческие факторы в вычисли- тельных и информационных системах.  М.: Радио и связь, 1984. – 304 с. 4. Bastani F.B., Iyengar S.S. The effect of data structures on the logical complexity of pro- grams // CACM. – 1987. Vol. 30, N 3. – P. 250259. 5. Акуловский В.Г. Основы алгебры алго- ритмов, базирующейся на данных // Про- блеми програмування.  2010.  № 23.  С. 8996. 6. Дорошенко А.Е., Акуловский В.Г. Алгебра алгоритмов с данными и прогнозирование вычислительного процесса // Проблеми програмування.  2011.  № 3.  С. 310. 7. Акуловский В.Г. Алгебра для описания данных в композиционных схемах алго- ритмов // Проблеми програмування.  2012.  № 23.  С. 234240. 8. Дорошенко А.Е., Акуловский В.Г. Нисхо- дящее проектирование алгоритмов в рам- ках алгеброалгоритмического подхода // Математические машины и системы. – 2012. – № 3. – С. 97–102. 9. Дорошенко А.Ю., Акуловський В.Г. Висхід- не проектування алгоритмів при алгеброа- лгоритмичному підході // Вісник Київсько- го національного університету імені Тара- са Шевченка. Серія фізико-математичні науки. – 2012. – Вип. 1. – С. 167–172. Получено 26.07.2012 Об авторах: Акуловский Валерий Григорьевич, кандидат технических наук, доцент кафедры информационных систем и технологий, Дорошенко Анатолий Ефимович, доктор физико-математических наук, профессор, заведующий отделом теории компьютерных вычислений. Место работы авторов: Академия таможенной службы Украины, Тел. 050 941 05 66, E-mail: valeryakulovskiy@rambler.ru Институт программных систем НАН Украины. Тел. (044) 526 3559, E-mail: dor@isofts.kiev.ua http://mail.rambler.ru/mail/mail.cgi?mode=compose;mailto=valeryakulovskiy%40rambler.ru;83ec;enc=utf-8 mailto:dor@isofts.kiev.ua

Composition and properties of data specified in compositional schemes of algorithms

Institution

Ähnliche Einträge