Algebra for the description of data in the composite schemes of algorithms

The algebra of the data in which frameworks the complex approach to programming is realized at the description of operating structures and structures of the data in composite schemes of algorithms is offered.

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
1. Verfasser:	Akulovskiy, V.G.
Format:	Artikel
Sprache:	rus
Veröffentlicht:	Інститут програмних систем НАН України 2015
Schlagworte:	UDC 004.42
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/75
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-75
record_format	ojs
resource_txt_mv	ppisoftskievua/a3/b564e58997620727e51a1609a6e893a3.pdf
spelling	pp_isofts_kiev_ua-article-752018-09-18T14:42:28Z Algebra for the description of data in the composite schemes of algorithms Алгебра для описания данных в композиционных схемах алгоритмов Алгебра для опису даних у композиційних схемах алгоритмів Akulovskiy, V.G. UDC 004.42 УДК 004.42 The algebra of the data in which frameworks the complex approach to programming is realized at the description of operating structures and structures of the data in composite schemes of algorithms is offered. Предлагается алгебра данных, в рамках которой реализуется комплексный подход к программированию при описании управляющих структур и структур данных в композиционных схемах алгоритмов. Пропонується алгебра даних, в рамках якої реалізується комплексний підхід до програмування при описі керованих структур та структур даних у композиційних схемах алгоритмів. Інститут програмних систем НАН України 2015-09-10 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/75 PROBLEMS IN PROGRAMMING; No 2-3 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2012) 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/75/76 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-09-18T14:42:28Z
collection	OJS
language	rus
topic	UDC 004.42
spellingShingle	UDC 004.42 Akulovskiy, V.G. Algebra for the description of data in the composite schemes of algorithms
topic_facet	UDC 004.42 УДК 004.42
format	Article
author	Akulovskiy, V.G.
author_facet	Akulovskiy, V.G.
author_sort	Akulovskiy, V.G.
title	Algebra for the description of data in the composite schemes of algorithms
title_short	Algebra for the description of data in the composite schemes of algorithms
title_full	Algebra for the description of data in the composite schemes of algorithms
title_fullStr	Algebra for the description of data in the composite schemes of algorithms
title_full_unstemmed	Algebra for the description of data in the composite schemes of algorithms
title_sort	algebra for the description of data in the composite schemes of algorithms
title_alt	Алгебра для описания данных в композиционных схемах алгоритмов Алгебра для опису даних у композиційних схемах алгоритмів
description	The algebra of the data in which frameworks the complex approach to programming is realized at the description of operating structures and structures of the data in composite schemes of algorithms is offered.
publisher	Інститут програмних систем НАН України
publishDate	2015
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/75
work_keys_str_mv	AT akulovskiyvg algebraforthedescriptionofdatainthecompositeschemesofalgorithms AT akulovskiyvg algebradlâopisaniâdannyhvkompozicionnyhshemahalgoritmov AT akulovskiyvg algebradlâopisudanihukompozicíjnihshemahalgoritmív
first_indexed	2025-07-17T09:43:09Z
last_indexed	2025-07-17T09:43:09Z
_version_	1838499863256367104
fulltext	Формальні методи програмування УДК 004.42 АЛГЕБРА ДЛЯ ОПИСАНИЯ ДАННЫХ В КОМПОЗИЦИОННЫХ СХЕМАХ АЛГОРИТМОВ В.Г. Акуловский Академия таможенной службы Украины. 49000, г. Днепропетровск, ул. Дзержинского 2/4. Тел/Факс: (0562) 745 5596, (0562) 47 1791 e-mail: academy@amsu.dp.uа. Предлагается алгебра данных, в рамках которой реализуется комплексный подход к программированию при описании управляющих структур и структур данных в композиционных схемах алгоритмов. The algebra of the data in which frameworks the complex approach to programming is realized at the description of operating structures and structures of the data in composite schemes of algorithms is offered. Введение В соответствии с важностью роли, играемой данными в программировании [1, 2], автором в работах [3, 4], заложены основы алгебраического аппарата, в котором, в результате модификации модели ЭВМ Глушкова [5], в описание управляющих структур алгоритмов органично “встроены” данные. Упомянутый формальный аппарат − это система алгоритмических алгебр (САА/Д) <U; L; S>, где U − множество Д-операторов, L – множество логических условий, S – сигнатура операций, состоящая из операций S1, принимающих значения на множестве операторов U и логических операций S2, принимающих значения на множестве L. В рамках САА/Д в качестве одной из форм описания алгоритмов используются композиционные схемы (КС) [3, 4], которые записываются, в виде )D(OD)D(OD)D(ODDOD kkk ′′′=′ )(...)()()()( 222111 , (1) где – исходный, а , )()( DOD ′ )D(OD 111)( ′ )D(OD 222 )( ′ , …, )D(OD kkk ′)( – производные Д-операторы. То есть, исходный Д-оператор декомпозируется, а каждый производный Д-оператор )()( DOD ′ )D(OD iii ′)( , реализует некоторую часть функций исходного Д-оператора. При этом на входах Д-операторов специфицированы обрабатываемые, а на выходах результирующие данные, чем и обусловлено использование названия Д-оператор. В КС, помимо данных специфицированных на входе и выходе Д-оператора , имеют место промежуточные данные , которые, играя вспомогательную роль, служат для преобразования исходных данных в результирующие, а на входе и выходе Д-оператора )()( DOD ′ prD )()( DOD ′ не специфицируются. Для данных и D D′ , специфицированных на входе и выходе исходного Д-оператора )D(O)D( ′ , выполняются следующие соотношения: kDDDD ∪∪∪⊆ ...21 , (2) kDDDD ′∪∪′∪′⊆′ ...21 , (3) где для любого и может выполняться iD iD′ ∅=∩ DDi и ∅=′∩′ DDi ; DDDDDDDDD kk pr ′′∪∪′∪′∪∪∪∪= /)...()/)...( 2121 . (4) То есть, обрабатывает все или некоторую часть данных, специфицированных на входе исходного Д-оператора, при и продуцирует все или некоторую часть данных, специфицированные на его выходе, при )D(OD iii ′)( ∅≠∩ DDi ∅≠′∩′ DDi . В случае, когда ∅=∩ DDi и/или ∅≠′∩′ DDi , он обрабатывает и/или продуцирует промежуточные данные и . prpr i DD ∈ prpr i DD ∈′ Множества данных DD ⊆′′ и DD ′⊆′′′ таких, что iDD ⊆′′ , ∅≠∩′′ jDD и iDD ′⊆′′′ , ∅≠′∩′′′ jDD (5) для всех i и j, целиком обрабатываются Д-оператором )D(OD iii ′)( . То есть, с точки зрения описания этих данных в КС они на данном этапе разработки являются неделимыми. В противном случае данные будем называть делимыми. ©В.Г. Акуловский, 2012 ISSN 1727-4907. Проблеми програмування. 2012. № 2-3. Спеціальний випуск 234 http://mail.rambler.ru/mail/mail.cgi?mode=compose;mailto=academy%40amsu.dp.u;83ec;enc=utf-8 Формальні методи програмування Разработка управляющих структур алгоритмов неразрывно связана с проектированием структур данных. В работе [6] отмечалась целесообразность применения средств, используемых для описания управляющих структур, для описания структур данных. Такой формальный аппарат (алгебра структур данных, базирующаяся на теории модифицированной системы алгоритмических алгебр (САА-М)), ориентированный на порождение и распознавание данных, был предложен в работах [7, 8]. Однако, САА/Д имеет принципиальные отличия от САА-М, которые в первую очередь состоят в том, что данные наряду с описанием управляющих структур, являются неотъемлемой частью формализованного описания алгоритма. Это отличие является предпосылкой для пересмотра основополагающих подходов к программированию, применительно к некоторому классу программных систем. Остановимся на упомянутых подходах. При разработке алгоритмов описываются две их составляющие – управляющие структуры и структуры данных. В случае, когда первая составляющая более приоритетна, реализуется программирование от управления. В противном случае – программирование от данных. При этом не один из этих подходов, воплощениями которых являются методологии структурного и объектно-ориентированного программирования, не универсален. Это обуславливается тем, что существуют программные системы, которым не адекватен любой, в отдельности используемый, подход (соответственно, методология). Типичным представителем такого класса систем являются информационно-управляющие системы. Исходя из этого, сформулируем цель данной работы. Целью данной работы является построение алгебры данных, которая при разработке алгоритмов для вышеупомянутого класса систем обеспечит реализацию комплексного подхода к программированию, адекватного специфике этого класса. Комплексность подхода заключается в возможности использования любого из указанных подходов на различных этапах разработки одного алгоритма и совместного их использования в случае необходимости. Кроме того, формальный аппарат должен обеспечивать согласованность при описании управляющих структур и структур данных, реконфигурацию данных, в случае изменения (модификации) алгоритма, а так же возможности контроля корректности описания и обработки данных. Для достижения указанных целей необходимо определить формы записи структур данных, их свойства, способы доступа к ним и средства преобразования. Под доступом к данным будем понимать возможность спецификации требуемых данных на входе или выходе производного Д-оператора в КС. Построение алгебраического аппарата начнем с формализации данных. Формализация данных Для формализации данных введем понятие носителя данных. Атомарным носителем данных является бит (разряд). Заметим, что не обязательно бит. В качестве атомарного носителя данных может выступать, например, трит в случае трехзначного компьютера. Будем полагать, что в нашем распоряжении имеется множество атомарных носителей данных . Непрерывные последовательности атомарных носителей данных образуют элементарные (неделимые) носители данных (в частном случае },...,{ 1 nbbB = >=< ++ smmmi bbbn ,...,, 1 pc bn = ). Размер (количество атомарных носителей) элементарного носителя данных определяет его информационную ёмкость. В общем случае существуют как различные ji nn ≠ , так и одинаковые ji nn = ( ji ≠ ) по размеру носители данных. Памятью данных будем называть перестановку элементарных носителей данных maaa nnnN ,...,, 21 = такую, что , а для элементов индексного множества Bnnn maaa =∪∪∪ ... 21 m,...,a,aaA 21= выполняется при i<j. ji aa < Носители данных в общем случае определим следующим образом. Определение 1. Носителями данных будем называть классы разбиения памяти AA\|N iAi ∈=N , образующие семейство непустых и различимых подмножеств таких, что kiiii aaaA nnnN ++ = ,...,, 1 , ii aA = , , для всех . Частными случаями носителей данных являются элементарные носители данных, когда U N=∈ ii AAA N ∅=∩ ji AA NN AAA ji ∈, ii aA nN = . Элементы множества piii AAAA ,...,, 21 =N ( ), поставленные в однозначное соответствие носителям данных ( ), будем называть адресами носителей данных. Элементы множества AA ⊆N N∈ iAN NA~N kiiiN aaaA ++= ,...,, 1 ( ), поставленные в однозначное соответствие элементарным носителям данных ( ) – адресами элементарных носителей данных. AAN⊆ ij Aa Nn ∈ NA AN i ~ Очевидно, что при различных разбиениях могут быть получены различные сочетания носителей данных, при этом существуют как различные ji AA NN ≠ , так и одинаковые ji AA NN = по размеру носители данных. После определения носителей данных перейдем к рассмотрению понятия данные. Элементарный носитель данных содержит (хранит) в каждый момент времени некоторое значение, записанное в некоторой форме (например, целое число или число с плавающей точкой), которое изменяется в ходе вычислительного процесса. 235 Формальні методи програмування Информационная емкость элементарных носителей данных и формы хранимых значений определяют форматы данных, образующих множество },...,,{ 21 kfffF= . Множество значений , которые может хранить элементарный носитель данных, ограничены форматом этих значений . То есть значения, хранимые носителями данных, изменяются в диапазоне, определяемом форматом хранимых данных. },...,{ 1 jj f p f ззЗ= Ff j ∈ Отметим, что в частном случае в качестве значений, хранимых элементарным носителем данных, могут выступать адреса носителей данных. Исходя из изложенного и определения 1, обозначив формат данных для общего случая , определим их следующим образом. xf Определение 2. Данными будем называть упорядоченную пару KAD i fx ,= , где xx f n f ззK ,...,1= – кортеж значений, носителем которого является элемент разбиения , расположенный по адресу . Кортеж iAN NAAi∈ K образован текущими значениями, хранимыми всеми элементарными носителями данных, входящими в . Формат данных определяется форматом значений, образующих кортеж iAN xfD K . Частным случаем данных являются простые данные xx f i f зAd ,= . Простые данные aa f i f зAd ,= такие, что , то есть содержат адрес некоторых данных, расположенных по адресу , называются ссылкой. Aaз j f a ∈= ja Будем говорить, что данные расположены (размещаются) по адресу и определим, связанное с размещением данных по адресам, следующее их свойство. xfD iA Определение 3. Данные и расположены последовательно, то есть непосредственно предшествует , а непосредственно следует за , если для адресов этих данных и выполняется , и не существует данных с адресом , для которого выполняется xf iD xf jD xf iD xf jD xf jD xf iD iA jA ji AA < xf kD kA jki AAA << . В противном случае будем говорить, что данные и расположены непоследовательно. xf iD xf jD Определив данные, перейдем к рассмотрению регулярно организованных данных, обозначая совпадающие форматы данных . Для этого, учитывая, что, в соответствии с определениями 1 – 3, yf yfyf x n f ddD ,...,1= – n-размещение простых данных, где Kn= , а каждому элементу кортежа K в однозначное соответствие поставлен адрес, будем осуществлять разбиения множества . xfD Первое разбиение 111 \| 11 JjDD xfxf jj ∈= образует семейство непустых и различимых подмножеств таких, что (при ), U xxf f jJj DD =∈ 111 ∅=∩ xfxf ij DD 11 11 ij ≠ xfxf ij DD 11 = (для всех и ), где 1j 1i 11 ,...,2,1 pJ = , nDn xf j =× 11 и каждому в однозначное соответствие поставлен адрес xf jD 1 AA ij ∈ . Аналогичное разбиение при тех же условиях выполним для каждого полученного класса предыдущего разбиения и т.д. Этот процесс продолжим до получения разбиения xfD2 xf jD 1 kkjjj f n JjdD yf k x ∈= \|,...,, 21 такого, что U , где xf k yf kkk jjjjjjJj Dd 12121 ,...,,,...,, − =∈ kk pJ ,...,2,1= . В результате проведенных построений получены регулярно организованные данные, представляющие собой иерархию из k уровней, на каждом i-м уровне которой адресам, изменяются с постоянным шагом, в соответствие поставлен индекс с единичным шагом изменения. Исходя из этого, массивы определим следующим образом. Определение 4. Регулярно организованные данные , элементы кортежа значений которых xfD YY f n f ззK ,...,1= имеют один формат, будем называть многомерным массивом простых данных и обозначать , где – индексы, задающие размерности массива, для которых выполняется xk fnn D,...,1 knn ,...,1 Knn k =××...1 . Частным случаем многомерных массивов является вектор (одномерный массив), который запишем в виде (xfnD Kn= ), полученный в результате того, что адресу каждого элемента в однозначное соответствие ставится значение индекса j. x yf f j Dd ∈ Из соображений общности изложения, простые данные в случае необходимости будем трактовать как вырожденный случай массива и обозначать . xfD1 Исходя из изложенного, введем следующее утверждение, предварительно оговорив, что в нем индексы массивов будем трактовать как любые совокупности индексов, а последовательно расположенные данные будем записывать, используя в качестве разделителя символ “;”. xprr ,, 21 Утверждение 1. Любой массив, за исключением , может быть преобразован к виду , где – произвольная совокупность последовательно расположенных массивов любой размерности, при условии xfD1 xsxx f k pfpfr DDD ;...;1 11 = xsx f k pfp DD ;...;1 1 xxsx frf k pfp DDD 11 ...1 =++ . Любая совокупность последовательно расположенных массивов, 236 Формальні методи програмування образованных элементами одного формата, может быть преобразована к виду , где – массив произвольной размерности, при условии xxsx frf m pfp DDD 21 ;...;1 = xfr D2 xsxx f m pfpfr DDD ++= ...1 12 . Доказательство. В соответствии с определением 4, , а может быть представлено в виде , где все подмножества расположены последовательно, для всех j и i выполняется и xx ffr DD =1 xfD xxx f k ff DDD ∪∪= ...1 ∅=∩ xx f i f j DD xxx f k ff DDD ++= ...1 . В результате выполнения описаного выше процесса разбиения над всеми подмножествами будет получена совокупность массивов требуемой размерности, в частности векторов. Если простые данные ( ), они сохраняется неизменными. Таким образом, требуемое соотношение при указанном ограничении реализуемо. xf iD xf jD xf jD1 Так как каждый массив получен в результате разбиения, то . А так как, по условию утверждения, массивы расположены последовательно и образованы элементами одного формата и для всех j и i выполняется , то в результате объединения подмножеств получим данные такие, что xi f i p D xxi f i f i p DD = xsx f m pfp DD ;...;1 1 ∅=∩ xx f i f j DD xxx ff m f DDD =∪∪...1 xxx ff m f DDD =∪∪...1 . Выполняя рассмотренное выше разбиение множества получим многомерный массив требуемой размерности при указанном ограничении. xfD xfr D2 Утверждение доказано. Следствие 1. Из доказательства утверждения легко увидеть, что любой массив размерности может быть преобразован в массив размерности , при условии xj fr D jr xi fr D ir xixj frfr DD = . Теперь остановимся на таком важном аспекте описания данных, как их именование. Очевидно, что данные однозначно идентифицируются своими адресами в памяти. При этом подчеркнем, что адресом любой структуры данных является адрес её первого компонента. Однако, для удобства описания алгоритмов, всем данным необходимо поставить в однозначное соответствие уникальные имена – идентификаторы. Заметим, что, очевидно, следует придерживаться некоторых правил формирования идентификаторов. В частности, рационально использовать правила, характерные для целевого языка программирования (языка, на котором будет реализовываться разрабатываемый алгоритм). В данном случае, из соображений общности, будем полагать, что мы располагаем некоторым конечным множеством произвольных идентификаторов I таким, что I достаточна для описания любого алгоритма, любой идентификатор уникален и ставится в однозначное соответствие адресу данных . Такой идентификатор замещает данные при описании алгоритма и обеспечивая доступ к данным расположенным по этому адресу. IX i ∈ jA xfD Данные, снабженные идентификатором, будем называть поименованными. Поименованные простые данные будем называть переменной, а поименованную ссылку – указателем. Именование массивов выполним традиционно. Если многомерному массиву приписывается идентификатор M, то массив запишем в виде , элемент массива – , а идентификатор подмассива (сечения) формируются в результате отбрасывания размерностей справа налево, например, . Векторы именуются аналогично , , а подмассив , где индексы, определяющие границы подмассива, такие, что xk fnn D,...,1 ],...,[ 1 knnM ],...,[ 1 kiiM ],...,[ 11 −knnM ][nV ][ jV ],[ jiV )1(0 −≤<≤ nji . Заметим, что индексы могут изменяться как от нуля, так и от единицы. В результате формализации данных введены и поименованы простые данные, в частности указатели, и массивы произвольной размерности. В дальнейшем изложении введенные данные будем называть базовыми структурами, понимая под этим термином то, что они формируются в результате некоторой интерпретации структуры носителя данных. На основе выполненной формализации, исходя из поставленной задачи, перейдем к построению алгебраического аппарата. Алгебра данных Учитывая пассивную роль, которую данные играют в алгоритмах и программах [9], в сигнатуру создаваемой алгебры включим как операции, имеющие аналоги в алгебре алгоритмов, так и операции таких аналогов не имеющие. Операцию композиция определим с элементами рекурсии. Операция композиция (), определенная на множестве последовательно расположенных поименованных базовых структур данных и записей, YXX =21 * (в общем случае ) описывает новые данные, называемые записью. Доступ к i-му элементу записи осуществляется посредством пары идентификаторов , разделенных символом “_”. В случае вложенности записей – последовательностью YXX k =...1 iXY _ 237 Формальні методи програмування идентификаторов, разделенных символом “_”, длина которой определяется глубиной вложенности. Если элементом записи является массив, доступ осуществляется с помощью идентификатора вида . ],...,[_ 1 ki jjXY Исходя из определения операции, приведем следующее свойства записи Y: 1* YXY = , 1* YYX = , 121 ** YXYX = , (6) где – записи или базовые структуры данных, – новая запись; 21 ,, XXX 1Y nXXY ;...;1= , (7) где – запись или базовая структура данных. iX На множестве последовательно расположенных поименованных базовых структур данных и записей определим операцию р-итерация . Эта операция, выполнив над этими структурами операцию композиция, и, трактуя результат как единые (простые) данные, описывает массив (в частном случае вектор ), который будем называть массив записей. Массивы записей именуются аналогично массивам простых данных в виде , , а доступ к элементам записи осуществляется с помощью пары идентификаторов , разделенных символом “_”. Доступ к вложенным записям осуществляется с помощью последовательности идентификаторов. };...;]{,...,[ 11 kk XXnn xk fnn D,...,1 xfnD ],...,[ 1 knnMS ][nVS ik XjjMS _],...,[ 1 Записи и массивы записей отнесем к классу составных структур данных, а по поводу массивов записей будем утверждать следующее. Утверждение 2. Массивы записей обладают свойствами заданными утверждением 1. Доказательство. При трактовке носителя данных как элементарного доказательство становится тривиальным, так как реализуется в результате использования приведенных выше рассуждений. xfD Теперь рассмотрим данные, непоследовательно расположенные в памяти, которые будем записывать, используя в качестве разделителя “/”, в виде . kXX /.../1 Здесь уместно сделать небольшое отступление. Данные бывают связаны с точки зрения последовательности их обработки. Для регулярно организованных данных, в частности массивов, эта связь легко учитывается в силу их последовательного размещения. Для непоследовательно расположенных данных такая связь обеспечивается указателями. Отметим, что отсутствующие на текущем этапе разработки алгоритма связи между данными могут проявиться на следующих её этапах. Для непоследовательно расположенных связанных данных введем следующую операцию. Операция объединения любых непоследовательно расположенных в памяти связанных поименованных данных (в общем случае YXX =21 U YXX k =UU ...1 ) описывает новые данные , которые именуются с помощью идентификатора и называются сложными структурами данных. Доступ элементам сложной структуры данных возможен как посредством идентификаторов, так и с помощью указателей. Сложные структуры данных могут являться элементами таких структур. Y Исходя из определения операции, приведем следующее свойства сложной структуры данных Y : 1YXY =∪ , (8) где X – структура данных, – новая сложная структура данных; 1Y nXXY ;...;1= , (9) где – сложная или произвольная структура данных. Свойство (9) выполняется при условии сохранения связей между данными. iX Любые произвольно, в частности непоследовательно, расположенные не связанные данные, которые в результате именования образуют совокупности данных, будем записывать в виде ,. Доступ к элементам совокупностей данных осуществляется посредством их идентификаторов. kXXY \|...\|1= Наконец, введем операцию совмещения данных , которая в однозначное соответствие одному адресу памяти ставит два (или более) идентификатора, обеспечивая, таким образом, возможность различной интерпретации одних и тех же данных. ji XX I Таким образом, построена алгебра SD; , где D – множество поименованных данных, S – сигнатура, определенных на них операций. Представление любых данных через образующие элементы SD; называется схемой данных (СД). Расширяя посредством предложенной алгебры данных САА\Д, получаем трехосновную алгоритмическую систему – <U;L;D;S>, где U − множество Д-операторов, L – множество логических условий, D – множество данных, S – сигнатура операций, состоящая из операций S1, принимающих значения на множестве Д-операторов U, логических операций S2, принимающих значения на множестве логических условий L, и S3, принимающих значения на множестве данных D. 238 Формальні методи програмування Покажем возможность решения поставленной задачи в рамках построенного алгебраического аппарата. Разработка КС алгоритмов Рассмотрение процесса разработки КС начнем с возможности реализации комплексного подхода к их описанию. Для этого рассмотрим процесс описания управляющих структур и структур данных, полагая, что алгоритм (фрагмент алгоритма) задан в виде Д-оператора )()( YOY ′ , на входе и выходе которого специфицированы идентификаторы совокупностей данных. Первый подход от управления. Исключив из рассмотрения промежуточные данные, получим следующие свойства данных в КС: kDDDD ∪∪∪= ...21 ; kDDDD ′∪∪′∪′=′ ...21 . Исключив из числа производных Д-операторов такие, что обрабатывают промежуточные данные, декомпозируем Д-оператор и КС запишем в виде kOOOYOY ...)()( 21=′ . После этого Y и Y ′ совокупности даны, опишем их в виде СД nXXY \|...\|1= и . nXXY ′′=′ \|...\|1 Если все полученные данные соответствуют функциям всех Д-операторов, то есть соответствуют соотношениям (5), то они являются неделимыми и “распределяются” между Д-операторами . Если некоторые (или все) данные соотношению (5) не соответствуют, или не соответствуют функциям некоторых (или всех) производных Д-операторов, то они делимые и детализуются, то есть записываются в виде СД. kOOO ,...,, 21 Покажем возможности детализации структур на примерах такой распространенной структуры данных, как строка. Строка может рассматриваться как вектор простых данных и в этом случае представляет собой СД . ][nSTRSTR = Строка переменной длины со счетчиком может быть описана с помощью СД вида , то есть в виде записи, где – переменная-счетчик, а доступ к элементам строки осуществляется по правилам доступа к элементам записи. ][ nSTRsckSTR = sck Строка с управляемой длиной записывается в виде следующей СД ][nVDSCSTRD U= , представляющей собой сложную структуру данных, где – дескриптор строки. Элементы СД могут быть детализованы. В данном случае дескриптор строки запишем в виде записи DSC UTDMAXDSC = или в виде последовательно расположенных переменных , где UTDMAXDSC ;;= MAX – максимальная, а TD – текущая длина строки, U – указатель на строку. Использование операции совмещения данных позволяет реализовать запись с вариантами . В этом случае выбор варианта, то есть одного из возможных счетчиков, определяется выбором соответствующей пары имен или . )( 21 UUTDMAXDSC ∪= 1_UDSC 2_UDSC Сверх того, один дескриптор может использоваться с несколькими строками . ][][][3 321 nVnVnVDSCSTRD UUU= Указатели позволяют реализовать списковое представление строк. В простейшем случае строки могут быть представлены однонаправленным списком. В этом случае они описываются следующей СД , компоненты которой при детализации представляет собой СД вида , где – звено (многосимвольная группа, подстрока), описанное с помощью вектора, или символ, U – указатель на следующий элемент списка (следующую подстроку). kSTRSPSTRSPSTRSPSTR ∪∪∪= ...21 UnSTRSTRSP ii ];[= ][nSTRi Процесс детализации продолжается до тех пор, пока не достигает уровня, который определяется функциями производных Д-операторов и выполнением соотношения (5). Отметим, что приведенные примеры, не отражая всего многообразия структур данных, демонстрируют достаточные возможности для их описания. То есть, средствами алгебры данных могут быть описаны разнообразные структуры данных и осуществлена их детализация. В частности, вектор может интерпретироваться как дек, стек, очередь, а указатели позволяют описывать списки, деревья и т. п. Кроме того, указатели, ссылающиеся на указатели, образуют указатели высшего ранга [10], они могут быть организованы в массивы и использоваться для описания сложных структур данных. После того, как данные были детализованы и специфицированы на входах и выходах производных Д- операторов, КС дополняется Д-операторами, обрабатывающими промежуточные данные, на входе и выходе которых эти данные специфицируются. При этом промежуточные данные, если они делимые, описываются в виде СД и таким образом детализуются и специфицируются на входах и выходах производных Д-операторов аналогично вышеописанному случаю. На любом следующем (или предыдущем) этапе разработки может быть использован подход – от данных. Отличие в данном случае состоит в том, что процесс разработки начинается с детализации данных. После этого исходный Д-оператор декомпозируется таким образом, что производные Д-операторы обрабатывают полученные данные. 239 Формальні методи програмування Очевидно, что на каждом этапе могут использоваться оба подхода одновременно. По-видимому, при разработке программ, интуитивно используется именно такой вариант. В этом случае процесс описания алгоритма разбивается на последовательность шагов. На каждом шаге сначала выделяется Д-оператор и для него детализуются данные или наоборот шаг начинается с детализации данных. В результате записывается Д-оператор )X(OX iii ′)( со специфицированными данными такими, что и , если промежуточные данные имеют место. На каждом очередном шаге операции повторяются в произвольном порядке, то есть вводится Д-оператор i pr i XX ⊆ i pr i XX ′⊆′ )X(OX jjj ′)( , причем данные на его входе и выходе специфицируются с учетом имеющих место промежуточных данных. Таким образом, согласование данных с управляющей структурой происходит на каждом шаге, что упрощает и повышает качество этого процесса. Кроме того, облегчается работа с промежуточными данными. Таким образом, при описании КС алгоритмов может быть использован комплексный подход, при котором описание данных и управляющих структур осуществляется согласованно. При использовании любых подходов, стратегий и методов разработки алгоритмов, как правило, возникает задача их трансформации, если получен неудовлетворяющий результат или в случае модернизации алгоритма. Возможность трансформации данных в этом случае обеспечивается соотношениями (6) – (9) и утверждениями 1,2. Одним из важнейших требований, предъявляемых к формальному аппарату, является обеспечение возможности контроля за корректностью описания и обработки данных. Рассмотрим такие возможности. Очевидным средством контроля за корректностью описания данных в рамках алгебры данных, является проверка выполнения соотношений (2) – (4). Отметим, что этими соотношения свойства данных не исчерпываются, но в данной работе другие соотношения и, соответственно, средства контроля не рассматриваются. Действенным средством контроля за корректностью обработки данных в программировании является их типизация. Этот механизм может быть использован и на алгоритмическом уровне. Тип данных определим следующим образом. Определение 4. Типами данных, образующими множество Τ , будем называть интерпретации данных, хранимых в некотором формате , которые определяют множество операций, применимых к этим данным. Если для данных в некотором формате определено множество операций, то они называются типизированными. В противном случае – не типизированными. Ffx∈ Заметим, что данные в одном формате могут интерпретироваться по-разному и, таким образом, иметь различные типы. Кроме того, если операции определенные над некоторыми структурами данных, например массивами, не полиморфны, то есть зависят от типа образующих его элементов, то для каждого типа данных, образующих массив, определяется свой тип массива. Таким образом, типизированным данным в соответствие будет поставлено некоторое множество допустимых на них операций. На некотором этапе разработки, когда на входе Д-оператора специфицированы эти и только эти данные, а Д-оператор выполняет над данными одну операцию, то достаточно легко, при этом автоматически, проверить входит ли эта операция в множество допустимых. Заключение В результате выполненных исследований построена трехосновная алгебраическая система и показана возможность реализации комплексного подхода к программированию при описании КС алгоритмов и возможность согласованности в описании управляющих структур и структур данных. Описание структур данных в виде СД позволяет их детализовать, обеспечивая спецификацию данных на входе и выходе производных Д-операторов. Структуры данных могут быть реконфигурированы в соответствии с изменением алгоритма решаемой задачи. Кроме того, предложены некоторые средства контроля за корректностью описания и обработки данных. Перспективным направлением развития полученных результатов является описание известных структур данных в виде СД и апробация полученных результатов на конкретных задачах. 1. Данные в языках программирования: абстракция и типология. Сб. статей / Под ред. В.Агафонова. – М.: Мир, 1982. – 328 с. 2. Bastani F.B., Iyengar S.S. The effect of data structures on the logical complexity of programs // CACM. – 1987. – V. 30, N 3. – P. 250 – 259. 3. Акуловский В.Г. Основы алгебры алгоритмов, базирующейся на данных // Проблеми програмування. – 2010. – № 2–3. – С. 89 – 96. 4. Дорошенко А.Е., Акуловский В.Г. Алгебра алгоритмов с данными и прогнозирование вычислительного процесса // Проблеми програмування. − 2011. − № 3. − С. 3 − 10. 5. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наукова думка, 1978. – 319с. 6. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985. – 406 с. 7. Цейтлин Г.Е. Алгоритмические алгебры структур данных и многоуровневое проектирование программ // Программирование. – 1986. – № 3. – С. 8 – 16. 8. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий. – М.: Финансы и статистика, 1989. – 208 с. 9. Турский В. Методология программирования. – М.: Мир, 1981. – 264 с. 10. Ющенко Е.Л. Адресное программирование. – Киев: Гостехиздат УССР, 1963. – 288 с. 240

Algebra for the description of data in the composite schemes of algorithms

Institution

Ähnliche Einträge