Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов

Рассмотрены данные, специфицируемые в композиционных схемах алгоритмов. Показан их состав, структура, свойства и возможность контроля корректности их описания.

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Проблеми програмування
Дата:	2013
Автори:	Акуловский, В.Г., Дорошенко, А.Е.
Мова:	Російська
Опубліковано:	Інститут програмних систем НАН України 2013
Теми:	Теоретичні та методологічні основи програмування
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/86661
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов / В.Г. Акуловский, А.Е. Дорошенко // Проблеми програмування. — 2013. — № 2. — С. 3-12. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859589762739863552
author	Акуловский, В.Г. Дорошенко, А.Е.
author_facet	Акуловский, В.Г. Дорошенко, А.Е.
citation_txt	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов / В.Г. Акуловский, А.Е. Дорошенко // Проблеми програмування. — 2013. — № 2. — С. 3-12. — Бібліогр.: 9 назв. — рос.
collection	DSpace DC
container_title	Проблеми програмування
description	Рассмотрены данные, специфицируемые в композиционных схемах алгоритмов. Показан их состав, структура, свойства и возможность контроля корректности их описания.
first_indexed	2025-11-27T13:53:01Z
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
id	nasplib_isofts_kiev_ua-123456789-86661
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Russian
last_indexed	2025-11-27T13:53:01Z
publishDate	2013
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Акуловский, В.Г. Дорошенко, А.Е. 2015-09-25T19:26:17Z 2015-09-25T19:26:17Z 2013 Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов / В.Г. Акуловский, А.Е. Дорошенко // Проблеми програмування. — 2013. — № 2. — С. 3-12. — Бібліогр.: 9 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/86661 519.683 Рассмотрены данные, специфицируемые в композиционных схемах алгоритмов. Показан их состав, структура, свойства и возможность контроля корректности их описания. ru Інститут програмних систем НАН України Проблеми програмування Теоретичні та методологічні основи програмування Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов published earlier
spellingShingle	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов Акуловский, В.Г. Дорошенко, А.Е. Теоретичні та методологічні основи програмування
title	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
title_full	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
title_fullStr	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
title_full_unstemmed	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
title_short	Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
title_sort	состав и свойства данных, специфицируемых в композиционных схемах алгоритмов
topic	Теоретичні та методологічні основи програмування
topic_facet	Теоретичні та методологічні основи програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/86661
work_keys_str_mv	AT akulovskiivg sostavisvoistvadannyhspecificiruemyhvkompozicionnyhshemahalgoritmov AT dorošenkoae sostavisvoistvadannyhspecificiruemyhvkompozicionnyhshemahalgoritmov

Состав и свойства данных, специфицируемых в композиционных схемах алгоритмов

Репозитарії

Схожі ресурси