The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data

Properties of the operations which enter into the signature of algorithms’ algebra with the data are considered. Possibility to create the derivative operations convenient for various appendices, in particular with the fixing logic conditions, taking into account efficiency of realization in a targe...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2025
Автори:	Doroshenko, A.Yu., Akulovskiy, V.G.
Формат:	Стаття
Мова:	Russian
Опубліковано:	PROBLEMS IN PROGRAMMING 2025
Теми:	UDC 519.681
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/821
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-821
record_format	ojs
resource_txt_mv	ppisoftskievua/96/1b9aa14e53238faea789de8f30f92096.pdf
spelling	pp_isofts_kiev_ua-article-8212025-09-02T15:42:07Z The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data Построение и преобразование операций и некоторых алгоритмических конструкций алгебры алгоритмов с данными Побудова і перетворення операцій і деяких алгоритмічних конструкцій алгебри алгоритмів з даними Doroshenko, A.Yu. Akulovskiy, V.G. UDC 519.681 УДК 519.681 УДК 519.681 Properties of the operations which enter into the signature of algorithms’ algebra with the data are considered. Possibility to create the derivative operations convenient for various appendices, in particular with the fixing logic conditions, taking into account efficiency of realization in a target programming language is shown. Possibility to carry out optimizing transformations of algebra’s operations and typical algorithmic designs is shown. Problems in programming 2011; 4: 3-13 Рассмотрены свойства операций, входящих в сигнатуру алгебры алгоритмов с данными. Показана возможность создавать, в частности с помощью фиксирующих логических условий, производные операции, удобные для различных приложений и учитывающие эффективность реализации на целевом языке программирования. Показана возможность осуществлять оптимизирующие преобразования типичных алгоритмических конструкций.Problems in programming 2011; 4: 3-13 Розглянуті властивості операцій, що входять в сигнатуру алгебри алгоритмів з даними. Показана можливість створювати похідні операції, що є зручними для різних застосувань, зокрема, за допомогою фіксуючих логічних умов, з урахуванням ефективності реалізації на цільовій мові програмування. Показана можливість здійснювати оптимізуючи перетворення операцій алгебри і типових алгоритмічних конструкцій.Problems in programming 2011; 4: 3-13 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-09-02 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/821 PROBLEMS IN PROGRAMMING; No 4 (2011); 3-13 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2011); 3-13 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2011); 3-13 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/821/873 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-09-02T15:42:07Z
collection	OJS
language	Russian
topic	UDC 519.681
spellingShingle	UDC 519.681 Doroshenko, A.Yu. Akulovskiy, V.G. The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
topic_facet	UDC 519.681 УДК 519.681 УДК 519.681
format	Article
author	Doroshenko, A.Yu. Akulovskiy, V.G.
author_facet	Doroshenko, A.Yu. Akulovskiy, V.G.
author_sort	Doroshenko, A.Yu.
title	The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
title_short	The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
title_full	The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
title_fullStr	The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
title_full_unstemmed	The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
title_sort	construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data
title_alt	Построение и преобразование операций и некоторых алгоритмических конструкций алгебры алгоритмов с данными Побудова і перетворення операцій і деяких алгоритмічних конструкцій алгебри алгоритмів з даними
description	Properties of the operations which enter into the signature of algorithms’ algebra with the data are considered. Possibility to create the derivative operations convenient for various appendices, in particular with the fixing logic conditions, taking into account efficiency of realization in a target programming language is shown. Possibility to carry out optimizing transformations of algebra’s operations and typical algorithmic designs is shown. Problems in programming 2011; 4: 3-13
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/821
work_keys_str_mv	AT doroshenkoayu theconstructionandtransformationofoperationsandsomealgorithmicdesignsofalgorithmsalgebrawiththedata AT akulovskiyvg theconstructionandtransformationofoperationsandsomealgorithmicdesignsofalgorithmsalgebrawiththedata AT doroshenkoayu postroenieipreobrazovanieoperacijinekotoryhalgoritmičeskihkonstrukcijalgebryalgoritmovsdannymi AT akulovskiyvg postroenieipreobrazovanieoperacijinekotoryhalgoritmičeskihkonstrukcijalgebryalgoritmovsdannymi AT doroshenkoayu pobudovaíperetvorennâoperacíjídeâkihalgoritmíčnihkonstrukcíjalgebrialgoritmívzdanimi AT akulovskiyvg pobudovaíperetvorennâoperacíjídeâkihalgoritmíčnihkonstrukcíjalgebrialgoritmívzdanimi AT doroshenkoayu constructionandtransformationofoperationsandsomealgorithmicdesignsofalgorithmsalgebrawiththedata AT akulovskiyvg constructionandtransformationofoperationsandsomealgorithmicdesignsofalgorithmsalgebrawiththedata
first_indexed	2025-09-17T09:24:15Z
last_indexed	2025-09-17T09:24:15Z
_version_	1850413033975709696
fulltext	Теоретичні та методологічні основи програмування УДК 519.681 А.Е. Дорошенко, В.Г. Акуловский ПОСТРОЕНИЕ И ПРЕОБРАЗОВАНИЕ ОПЕРАЦИЙ И НЕКОТОРЫХ АЛГОРИТМИЧЕСКИХ КОНСТРУКЦИЙ АЛГЕБРЫ АЛГОРИТМОВ С ДАННЫМИ Рассмотрены свойства операций, входящих в сигнатуру алгебры алгоритмов с данными. Показана возможность создавать, в частности с помощью фиксирующих логических условий, производные операции, удобные для различных приложений и учитывающие эффективность реализации на целевом языке программирования. Показана возможность осуществлять оптимизирующие преобразования типичных алгоритмических конструкций. Введение Качество любой программы наиболее результативно обеспечивается на этапе разработки её алгоритма, а наиболее эффективным средством описания алгоритмов является алгебраический аппарат. В работах [1–3] заложены основы алгебраического аппарата, в который, в результате модификации известной [4] модели ЭВМ Глушкова, “встроены” данные. Модификация состояла в оснаще- нии указанной модели ЭВМ памятью – носителем данных. Данными D названа упорядоченная пара , где N – но- ситель данных (фрагмент памяти), S – ор- теж з ачений, хранимы этим носи елем данных в екущий момент времени. В частном случае данные d простыми, когда они в текущий омент времени содержат единственное значение s. Данные, расположенны в амяти и обрабатываемые алгоритмом, представляют собой семейство множеств },...,,{ 21 n P DDDD = . При этом отметим, что х данных iD не ограничена по сложности и объему. Упомянутый фор >< SN, к н й т т называются п некоторым мальный аппарат это U, оров, L – аю х м - ж ераторов, которы м е структура любы – система алгоритмических алгебр (САА\Д) – >< W , , где U – множество Д-операт множество логических условий, W – сигнатура, состоящая из логических операций W L 1, приним щи значения на ножестве L и операций W2, принимающих значения на множестве Д-операторов U. Принципиальные отличия предло енного формального аппарата от алгебры Глушкова состоят в следующем. На входе и выходе Д-оп е записываются в виде )()( DXD ′ , специфицированы обрабатываемы - ные, в связи с чем и введено такое их название. На е дан множестве k-значных логичес- ких условий { }1,...,1,0 −=∈ kѓЈl k определе- ны известны [5]) обоб- щенные операции: - отрицание е (см., например, )( kmod1ll += ; (21 lmaxll =∨ ; Множе принимаемых оги- - дизъюнкция ), 21 l - конъюнкция . ),( 2121 llminll =∧ ство значений, л ческими условиями дополнено логической константой «неопределенность», которая обозначена символом x. Такой, что l=x, если { }1,...,1,0 −=∉ kѓЈl k . Для выведенной константы ло- гические операции выполняются следую- щим образом: xx = , l=∨ xl , xxl =∧ . В результате значпостроены k+1- - ные логические условия { }xkѓЈl k k ,...,1,01 =∈ + ,1− , образу щие множество L, котором тся поняти еделение 1. Вычислительный процес l © А.Е. Дорошенко, В.Г. Акуловський, 2011 ISSN 1727-4907. Проблеми програмування. 2011. № 4 ю на определены приведенные логические операции, образующие множество W1. Ключевым для САА\Д являе е – состояние вычислительного процесса. Опр с на любом, например i-том, шаге выполнения находится в одном из состояний: P iDD = , }{ k i T i DD ∪= , где D – T i P i T i 3 Теоретичні та методологічні основи програмування текущее сос е вычислительного о- цесса, – текущее состояние памяти, k il – логическое условие. Состояние памят является составляющей состояния вычис- лительного процесса на каждом его шаге. Логические условия определены только на некоторых шагах вычислительного про- цессса, т. е. ∃ , где ∅≠}{ k ml в состоянии . Эта соста яющая яния вычисли- ьного процесса существует только на данном шаге, т. е. для любого , где ≠ , выполняется тояни пр и вл состо тел ∅=}{ k ml . Исходя из определения 1, е как , т введены Д-оп раторы. Определение 2. Д-операторы образуют следующий базовый набор: – )()( DOD ′ , для которого допустимо ∅=′∩D ак и ∅≠′D ∩DD , переводит вычислительный проц бого исход- ного для него состояния T iD в состояние T i T i DD ≠+1 , где ∅=+}1 k i{l , P iD ≠+1 ; – ))( PD да есс из лю P iD ( kl , который в л шем будем зывать п ьней на редикатом, представляет собой в общем случае n-местную логическую функцию x}kElDP k kon k ,: 11 =∈→ ++ , 1,...,1,0{ − где – n-арное (в общем лучае) пре не ис ii l ++ ∪ il , ii DD =+1 . В работе [6] едены иксир щие логиче oD с отношение, kl – k+1-значное логическое условие, п одуцируемое предикатом. xlk = , если }1,...,1,0{ −=∉ kEl k k или если - дикат а множестве данных oD . Этот Д-оператор переводит выч - лительный процесс из любого исходного для него состояния в состояние T iD 1+ такое, что 1 kPT i DD + = k PP р определен н }{ 11 , ∅≠+ }{ 1 вв ф ую ские условия как средство фиксации состояния вычислительного процесса. Множество логических условий ⊂ т е ыакое, что вс его элемент ( fLf ∈∀ ) меняются при выполнении любо - оператора не из го Д UDXD ∈′)()( . Другими словами говоря, усло ества fL сохраняют свои значения независимо о действия Д- называются фиксирующими, так как позволяют зафиксировать (сохранить) характеристику текущего осто ния данных, некоторое событие, имевшее место в ходе вычислительно процесса, или имет любую дру ую трактовку. Рассмотрим частный случай Д-опе- ратора )()( DOD вия множ т операторов множества U, в связи с чем с я го ь г ′ – )()( k i j fY∅ , в результате вы- полнения которого фиксирующее усло- вие ет значение }1,...,1,0{ k if получа −=∈ kEj . Поскольку в исходном состоянии выполнения )()( k i j fY∅ ) фиксирующее условие k if не определе- но, то фактически },1,...,1,0{ xkEf k k −=∈ Д-оператор ) вычислительный k (до переводит процесс из любого исходн его сост н г ующи усло являются ч то принци ов п и. При этом к е DO 1+ . ()( k i j fY∅ ого для н оя ия T iD в состояние T i T i DD ≠+1 , де ∅=+}{ 1 k il , P i P i DD +1 . Отметим, что фиксир е логические вия не ем- ≠ пиально н ым в рограммирова- нии, так как они, по-видимому, всегда использовались на практике под именами “флажки”, ”признаки” и т. п. В данном случае это средство только формализова- но в соответствующем контексте. На множестве Д-операторов U определены следующие операци олич ство их минимально. Операция композиция (обознача- ется “”) Д-операторов (D )() 111 ′ )()(* 222 DOD ′ означает последовательное выполнение сначала 111 Д-оператора )()( DOD ′ , а затем Д-оператора )()( DOD 222 ′ . ра и р-дизъюнкции (в уч Опе ци данном сл ае дизъюнкции, когда ()[( 3 333 3 222 3 111 333 222111 3 xlDOD lDOD lDOD DOD DODDOlPDo В случае фиксирующих логических услови 3p - },1,0{12 xEl =∈ + ) (D 3 ⎪ ⎩ ⎪ ⎨ ⎧ =′ =′ =′ =′∨ ∨′∨′ .если,)()( ;0если,)()( ;1если,)()( ))()( )()()())]( й 4 Теоретичні та методологічні основи програмування ∨′∨′ )()()()](([ 222111 3 DODDODf ⎪ ⎩ ⎪ ⎨ ⎧ =′ =′ =′ =′∨ .если,)()( ;0если,)()( ;1если,)()( ))()( 3 333 3 222 3 111 333 xfDOD fDOD fDOD DOD Хотя сигнатура САА\Д содержит минимальное число определенных на множе о х ена данная работа. ций начнем с определения тождественного и неоп дем наз стве U операций, их реализация такова, что п зволяет строить производ- ные операции и удобные для решения конкретных задач алгоритмические кон- струкции. Кроме того, имеет место сис- тема тождественных соотношений, кото- рая позволяет осуществлять эквивалент- ные оптимизирующие преобразования операций и распространенных алгоритми- чески конструкций. Рассмотрению указанных возмож- ностей САА\Д посвящ Производные операции САА\Д Рассмотрение производных опера- ределенного Д-операторов. Определение 3. Д-оператор )()( DXD ′ , в результате исполнения которого будет получено соотношение T i T i DD 1+= , бу- ывать тождественным и обозначать Z. Определение 4. Д-оператор )()( DXD ′ , который переводит вычислительн цесс и вы Ис п ее тождественное соотно- шение (1) Построим производную о и, имеющую аналоги в большинстве языков программирования: D ))(( 222111 2 3 222 222222 DODDODlPD xlDOD lDODDD o ′∨′= = ⎪ ⎩ ⎨ =′ ==∨ Полученная таким образом производная операция приводит к выполнению Д- оператора при истинном начении логического условия (l2=1) и ый про- з любого произвольного состояния T iD в неопределенное состояние, после перехода в которое все последующие шаги числительного процесса не определены, будем называть неопределенным и обозначать N. ходя из о ределений 1–3, при- ведем следующ , свойственное операции компози- ция: )()()()()()( DXDDXDZZDXD ′=′=′ . перацию р2-дизъюнкци ∨′∨′ )()()())]((() 222111 3 DODDODlPo ,1если,)()( 3 3 111 lDOD ⎪ ⎧ ′ =′ ′ [( )).()()())]((()[( если,)()( ,0если,)()()O )()( 111 DOD ′ з )()( 222 DOD ′ при l2≠ водную операцию 111 2 1 DODlPD lZ o ′= = ⎪⎩ = где . Эта операция играет важнейшую роль в дальнейшем , в котором будем называть её оследовательной фильтрацией (р- тром). Дл нные со 1, трактуемом как ложное, т. е. }2 =∈El . Воспользовавшись тождественным Д-оператором, построим ещё одну произ- 1,0{2 ),())](()[( 0если, 1если,)()( ))())](()[( 2 11 11 2 1 lDOD ZDO(DlPDo ⎪ ⎨ ⎧ =′ = =∨′ }1,0{2 2 =∈El изложении п филь я неё справедливы следующие тождестве отношения: ZDOlPDlPD oo =′))()())]([(()[( ; (2) ))())](())]([(()[( DOlPDlPD oo =′ D)]( DODlPDo ′= (3) ())](()()()[( ))())](())]([(()[( 21 2211 2211 21 DODlPDlPD DODlPDlPD oo oo ′∧= =′ Производные операции реализуе- мы и в случае фиксирующих ло ческих условий в виде: 2 DODDODf ′∨′ ; ;)())](()[( D ). ги ))()()()((][ 222111 )()]([ 11 1 DODf ′ . Воспользовавшись операциями р2- дизъюнкции и 3p -дизъюнкции, операцию дизъюнкции, которая построим kp - 5 Теоретичні та методологічні основи програмування существенно расширит возможности алгебраического ппарата. Будем исходить из того, что n-арное отношение и для него выполняются следующие соотношения: ooo DDDD 32 ...⊃⊃⊃⊃ ; ooo DD 21 = а – 1k1 − DD 13 ... −∪∪∪ ; … ; … D 12 −⊃ . Преди ) (см.определение 2) логическая а )( 3o PD – 3 xElDP i o i =∈→ . анизовав в качестве последн женной использовав дизъю +++ +++ +++ −−−−−− −− ,если),()( ;если,)()( ........... ;если,)()( ;если,)()( ))()(... ...)()()())]((()[( ))...)()()()( )(O)()](([( )() 1k xlDOD 0lDOD 2klDOD 1klDOD DOD DODDODlPD DODDOD DDlPD DO k 1k1k1k k kkk k 222 k 111 1k1k1k 222111 ko 1 1k1k1kkkk 1k1k 3 1k1k o k 2k2k где предикат логическая ф - ция такая, что k замещает oD1 o o k o k o i o DDD 11i ... −+ ∪∪= o k o kD − кат ()( 2 ii o i lPD функция }1,0{: 2 2 =∈→ ElDP i o i , )(liii 3 Орг ложенность операций 2p -дизъюнкции, а в ей операцией },1,0{: вло 3p - нкцию получаем ∨ ∨′ −−−− )]((()[(... ...)())]((()[( DlPD DODlPD 2k 2 2k2k o 2k 111 2 11 o 1 ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ =′ =′ −=′ −=′ = =′∨ ∨′∨′= =′∨′∨ ∨′∨ ∨′ )1 )(l)( 1 ko PD унк },1k,1,0{1 xElD:P k ko −=∈→ 1−= kl 12 1 =l , 2−= kl k замещает =2 12 и т. д замещают, соответст начн ие лови позво процес по произвольному числу направлений. о 1k1k1k Очевидна неполнота алгебры алго- ритмов, которая не содержит операцию выполняющую цикл. Для восполнения этого построим такую производ- ную оп 1+′ ′ kko DODlPD DODlPD представляют собой последовательность р- фильтров, связанных операцией компози- ция, которая обрывается в случае, когда редикат некоторого n-го р-фильтра после вы ение Д l ., а 1k =l , 0=kl , xlk = енно 13 1 =−kl , xlk =3 1- . k+1-з ые логическ ус я ляют разветвлять вычислительный с в 03 1 =−kl , Построенная перация реализуется и в случае фиксирующих логических условий =′∨ ∨′∨′ ))()(... ...)()()()](([ 222111 k DOD DODDODf +++ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ =′ =′ −=′ −=′ = +++ .если,)()( ;если,)()( ........... ;если),()( ;если),()( xfDOD 0fDOD 2kfDOD 1kfDOD k 1k1k1k k kkk k 222 k 111 пробела ерацию следующим образом. Определение 5. Операция р-итерации )}())]{(()[(( 1 =′ o o DODlPD ,...)()]{()()[(... ...)())](()[(( )())](()[(( 211 ′= o DODlPD п )()( lPDno продуцирует ложное логичес- кое условие (l=0). Где ioD , iD – данные, полученные после выполнения (j-1)-го элементом последовательности, 1jD +′ – полнения j-го элемента последо- вательности. Иначе говоря, операции р-итерации осуществляют циклическое выполн - оператора )()( DOD ′ при 1=l и завершает- ся в противном случае. ческое усло- вие аждый элемент п Логи l будем называть условием выполне- ния цикла, Д-оператор )()( DOD ′ – телом цикла, а к оследователь- ности р-фильтров – витком (шагом) цикла. Докажем наличие ограничений на организацию циклов. Теорема 1. Необходимым условием для завершения операций 6 Теоретичні та методологічні основи програмування р-итерации )}())]{(()[( DODlPDo ′ является выполнение соотношений ∅≠′∩DD и o ∅≠′∩DD . Доказательство построим от противного. Из ределений 1 и следует, что пос оп 2 р-фильтр ледовательно переводит вычисл сс в состояние D и D . При Д т им я ительный проце из исходного состояния TDi i 1+ i 2+ этом предикат не изменяет состояния множества данных oD , а -оператор изменяет состояние памяти аким образом, что допуст ы соотношени T T ∅=′∩DD и ∅≠′∩DD . Предположим, что имеет место соотношение ∅=′∩DDo и на первом шаге предикат )()( lPDo проду ет циру логическое условие 1=l . В результате выполнения )()( DOD ′ множество данных oD не изменяетс к ∅=′∩DDo , что приведет к вып нию второго и последующих элеме тов последователь- ности р-филь неизменном oD (см. определение 4), т. е. получим 1)()( и, таким образом, последовательность р- фильтров становится бесконечной. То есть, происходит “зацикливание” вычисли- тельного процесса. Предположим, что ∅≠′∩DDo , а ∅=′∩DD , и на первом витке цикла 1 я, так ка олне н тров при ≡lPDo =l . В результате выполнение тела цикла )()( DOD ′ , при условии , , 0=l выпол ∅≠′∩DDo множество данных oD изменится и получаем множество данных 1oD . При услов получения )( PD1o - нение цикла завершится после первого шага. Если этого не произойдет ( 1)()( =lPD1o ), то, в связи с ии )( ∅=′∩D , на втором и всех последующих шагах цикла множество данных iD останется неизмен- ным, ч приведет к неизменности данных D и . Откуда следует 1)()( ≡lPD (i>1), т. е. зацикливание, аналогичное вышерассмотренному случаю. Таким образом, при втором предположении либо зациклива вырождается р-фильтр. Поскольку сделанные предположе- ния противоречат услов ю теоремы, то соотношения ∅≠′DDo и D +′ операция ется, либо в и то 1i ioD io ∩ ∅≠′∩D являются условиями, нео D бходимыми для заверш вие 1. операциях ния его тела. о д где 0 – тож , 1 – тождест- венно истинное условие, Z – - ный, N – н ределенный Д- оператор; – или Z, в случае, когда ения операции р-итерации. Теорема доказана. Следст В р-итерации условие выполнения цикла зависит от результатов выполне Исходя из определения перации и теоремы 1, приве ем свойственные р-итерации тождественные соотношения: – ZDOD =′)}()[0]{( ; – NDOD ′)}()]{(1[ = , дественно тождествен ложное еоп NZlpDo =})]{()[( на первом витке цикла 0)()( =lpDo ; – ZDODlP =′)}}())]{(( ; – DlPD ))]{[(()[( oo ,lDODlPD DODlPDo )}())]{(()[( ′ o )}())]{(()[( ′= = (4) т . по завершению цикла множество данных получает такие значения, при орых 0 . их числу относится в частности извест к , обладающих разной “мощ- ностью”. Для начала, воспользовавшись . е oD кот )()( =lPDo Рассмотрим другие, представляю- щие интерес производных операций САА\Д. К ная [7] операция – переключатель. Построим нес олько вариантов этой операции * Следует обратить внимание на тот факт, что существует достаточно широкий класс программных систем (в частности, системы управления, реализуемые, как правило, на программируемых контроллерах), для которых бесконечный цикл, не только приемлем, но и необходим. Поэтому будем полагать, что существует операция цикла, для которой выполняется NDOD ≠′)()(]1[ , и которую в данной работе не рассматриваем. 7 Теоретичні та методологічні основи програмування вложен ) 111 2 11 ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ′′ = kkk k o k o DODDOD PDlPD выполняющий i-й Д-оператор, которому соответствует истинное значение логического условия, продуцируемого предикатом . ...)()]((( 2 DDl ′ ′′= kkk -k-k-k k o k o DOD DODDOD lPDlPD который отличается от предыдущего тем, что Д-оператор выполняется в случае, когда все предикаты продуцируют ложные логические условия. Мощность переключателя возрастет [ )( 121212 222222 12112111 22 11 121212222 121212 ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ ′ ′′ ′′ = =′∨′∨ ∨′ ∨′ +++ −−− +++ −−− ).DOD DODDOD DODDOD lPDlPD DODDD DOD D kkk kkk k2kk k o k o kkkkkk kkk В данном случае, при истинном значении логического условия продуциру- емого предикатом выполняется Д-оператор а при лож- ном – ными операциями р2-дизъюнкции и р-фильтром, получим переключатель ))...)())]((()[(... ...)())]((()[( )())]((([( 222 2 22 111 2 11 =′∨ ∨′∨ ∨′ kkkk o k o o DODlPD DODlPD DODlPD , )()(),...,()( )l()(),...,()( )()( 2 i o i lPD Воспользовавшись р2-дизъюнкци- ей, в качестве последней вложенной опе- рации, получаем переключатель ))[( o OPD =′∨ ∨′∨ ))...)()( )())]((()[(... 111 2 11 11111 kkk -k-k-k-k o -k DOD DODlPD ∨′ , )()( )()(),...,()( )()(),...,()( 111111 22 11 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ )()( kkk DOD ′ в случае использования вложенных р3- дизъюнкций )()())]((()[( 3 11 ∨′ ODDODlPD . ()( )()(),...,()( )()(),...,()( )()(),...,()( ))...)()()()( )())]((()[(... ...)()()())]((()( 3 444333 3 22 222111 ∨ ∨′∨′∨ lPD DODDODlPD k o k o O )()( 2 i o i lPD , )()( 12i12i12i DOD −−− ′ , )()( 2i2i2i DOD ′ . В случае неопределен ного логического условия выполняется следующий предикат. Если логическое условие не определено после выполнения всех предикатов, то выполняется Д-опера- тор - )()( 12k12k12k DOD +++ ′ . Очевидно, что в переключателях могут быть задействованы фиксирующие огические условия, а процесс построения , в связи рокого класса за Такой ью следую где Д- л переключателей может быть продолжен. Широко используемым в программировании с удобством решения ши дач, является цикл for. цикл реализуется с помощ щей алгоритмической конструкции )},()(* )())]{(l()[()()( 11 o pp DSD DODPDDUD ′ ′′ pp оператор )()( pp DUD ′ устанавливает исходные значения параметров цикла pD , а )()( pp DSD ′ – изменяет их с заданным ша- гом. При услови выполнения соотноше- ний ∅=′∪ и ∩′∪ )()( p11 pDDDD будет полу- чен аналог операции for, который офор- мим традиционно в виде производной операции р итерации - ерация при си сть услов ла, в качес вием, н для ным операциям тносится обратная р-итерация (цикл с постусловием), в котором услови выпол- нения проверяется после выполнения тела икла и который получим в результате ледующего построения: )}.())]{(()(; );l()();()[( 11pp o pp DODDSD PDDUD ′′ ′ Построенная оп заданных огра- ничениях позволяет обеспечить незави - мо ия выполнения цикла от его те тве которого рассматривается Д-оператор )()( 11 DOD ′ (см. следствие 1). Усло завершения цикла, является ∅≠∩′ o p DD , что легко доказать по аналогии с теоремой 1. К производ еобходимым о е ц с 8 Теоретичні та методологічні основи програмування )}.())]{(l()[()()( )]l())}[((){( DODPDDOD PDDOD o o ′′= =′ Условием, необходимым для завершения цикла, являет ∅≠oD , что легко доказать по аналогии с теоремой 1. Исходя из оп д л операций и условия заверш , приведем тождественные соотношения, свой ся D ре е ения ения цикла ствен- ные р- ием Z . Ещё одна производная констру ∩′ итерации с постуслов : )()()}[0](){( DODDOD ′=′ ; NDOD =′ [1])}(){( ; NlpDZ o =)]()}[({ или , когда на первом витке цикла 0)()( =lpDo к- ция – обобщенный цикл [7] )}())](())[((){( 222111 DODlPDDOD ′′ , т. е. цикл с контролем условия выполне- ния, осуществляемом в середине цикла. Такая операция легко реализуема на алг ритмическом уровне в виде о )())[(() 112 11 222111 D OD DODlPDDOD = =′′ отсутствует такой ператор, то при записи приведе - ной реализации на языке программмиро - ния проявится тот недостаток, что Д- ивести к акому увеличению программы, что возникшие издержки сделают применение этой конструкции недопустимой. Учитывая это, реализуем данную алгоритмическую конструкцию с по- мощью 22 )}.()()())]{(()[(* ) 122 1 DODODlPD D ′′ ′()( )}()]({( Однако, поскольку в большинстве языков программирования о н ва оператор )()( 111 DOD ′ записывается дваж- ды. Если это Д-оператор достаточно объемен, а операция используется доста- очно часто, то это может прт т фиксирующего логического усло- вия: ))}.()()()(()]()([ )()]{([)()( )}())](())[((){( fYDOlPD DODffY DODlPDDOD 0 2 2 111 1 222111 ∅∨′ ′∅= =′′ Данная реализация выполняется следующим образом. Для входа в цикл Д- оператор )()( fY 1∅ устанавливает исход- ное истинное значение условия f . В цик- ле выполняется Д-оператор )()( 111 DOD D ′ , и при ис а итинном зн чени условия l опера- ция р-дизъюнкции выполняет Д-оператор )()( 222 DOD ′ . Этот процесс продолжается до тех пор, пока l=1. значение ложь, Д-оператор Когда l примет )()( 222 DOD ′ влено 0 не выполнится, а будет устано =f . е В результате чего, выполнение цикла зав р- шится. Таким образом, цикл выполняется пор ческ значение. я являю ра contin ′ до тех , пока логи ое условие, проверяемое в середине цикла, имеет истинное Из рассмотренного случая видно, что фиксирующие услови тся удобным средством для построения новых алгоритмических конструкций. Продемон- стрируем эту возможность на примерах операторов, характерных для многих язы- ков программирования. Начнем с операто ue, полагая, что нам необходимо реализовать следующую алгоритмическую конструк- цию: )]((()[(* )())]{(()[( 111 DlPD DODlPD ′ ′ )},()( 333 22211 DOD continueDO ′ в которой, при истинном значении логи- ческого условия 1l , выполняется Д-опера- тор )()( 222 DOD )))() ′ , а )()( 333 DOD ′ не выпол- няется, так как цикл переходит следую- щей итерации в результате выполнения оператора continue. Поскольку оператор continue не являет к ся операцией САА\Д, воспользуемся фиксирующим логическим условием для построения конструкции, которая решает вленную задачу. 111 f DODlPD ′ поста )},()]([))()( ))()()()](()()[(* 1 222 2 1 DODfY fYDODlPD 0 ′∅∨ ∨∅′′ )())]{(()([ 333 9 Теоретичні та методологічні основи програмування где при истинном значении логического условия l2 фиксирующее условие f полу- чает ложное значение, что и позволяет перейт ате Д- оператор выполняется с по- мощью той же операции. Рассмотрим оператор break, необходимость использования которого )) , после вып прерывает- ся. р ю п 0 ′ ∅′′ ′∧∅ устанавлив ояние для входа в цикл. выполн и к следующей итерации, пропус- кая Д-оператор )()( 333 DOD ′ с помощью операции р-фильтрации. При ложном значении l2 фиксирующее условие f ста- новитс истинным, в я результ чего )()( 333 DOD ′ подвергается сомнению, но, тем не менее, он присутствует во всех наиболее распространенных языках программирова- ния. Возьмем аналогичную задачу )},()( )())]((()[( ())]{(([( 333 2221 111 2 DOD breakDODlPD DODlPD ′ ′′ ′ в которой олнения Д-оператора )()( 222 DOD ′ , выполнение цикла ) Снова воспользуемся фиксирующи- ми логическими условиями для построе- ния конструкции, еша щей оставлен- ную задачу )},()]([* ))()()())]((()[(* )()]{()()[()()( 333 22211 111 1 DODf fYDODlPD DODflPDfY в которой фиксирующее условие f ается в исходное истинное сост Цикл яется по условию fl ∧ при 1=f , если условие 1l не принимает истинного значения. Когда 1, в результате 1 =l выпол дизъюн Д-оператор , и фиксирующее условие f ложное значение В результате чего, Д-оператор нения р- кции выполняется )()( 222 DOD ′ принимает . )()( 333 DOD ′ не п выполняется, а процесс циклирования е я р рываетс по условию fl при 0∧ =f . 222111 nnn ok l ских аций ак ре льтат одуцируемы )](( 222 D ∨′ ′oo ч ом - д чных приложений. При этом показана возможность, не только строить такие конструкции, но и строить их с учетом эффективности реализации на целевом языке программирования. Эквивалентные реобразования н а с в частности Д-операторы и операции С исх й вы в результате их выполнения бу ны состоя При выполнении композиции пре- дикатов )()..)()()()( koko PDlPDlPD ooo , где o – одна из логиче опер , формируется логическое условие k n kkk R l..lll ooo 21= к зу примене- ния логических операций ко всем условиям, пр м предикатами. Учитывая это, операции, например, р (. . 2-дизъюнкции и р-итерации записывают- ся в виде ()()(...)()[( 22 1 DOlPDlPD oo oo )),()( 11111 DOD nnn ′∨ o ) )}())]{(()(...)()[( 111 DODlPDlPD i nn o n i и очевидно, то все рассмотренные операции САА\Д могут выполняться с учет логических условий неограничен- ной сложности. Приведенные производные опера ции емонстрируют возможности созда- вать в рамках САА\Д операции, удобные для разли п операций САА\Д и екоторых алгоритмических конструкций Рассмотрение этого раздела начнем с определения понятия эквивалентности алгоритмических конструкций. При этом под лгоритмиче кой конструкцией будем понимать любые допустимые сочетания Д- операторов и операций САА\Д. Определение 6. Две любые алгоритмические конструкции, АА\Д, эквивалентны, если при равенстве одных для них состояни числительного процесса T j T i DD = дут получе ния вычислительного процесса T kD и T mD , такие, что P m P k DD = . Рассмотрим возможность разложе- ния операции p2-дизъюнкции на последо- вательные фильтры. Учитывая это, будем утверждать следующее. 10 Теоретичні та методологічні основи програмування Утверждение 1. пера я pО ци ∨ ры, . пр е зиции та и o 2- дизъюнкции ))()()())]((()[( 222111 2o DODDODPD ′′ может быть разложена на последователь- ные фильт т. е едставл на в виде эквивалентной ей компо к х фильтров, при условии выполнения следующих ограничений ∅=′∩ 2 o DD или ∅=′1DD . l ∩ Доказательство. Для обеспечения эквивалентности в выражении )())](()[(* )())](()[( 111 D DODlPDo ′= ))()( 222 222 DODlP DOD o ′ =′∨ не влияет. )())]((()[( 111 DODlPD 2o ′ необходимо обеспечить только выполнение одного и того же Д-оператора в левой и правой его частях, так как предикат на состояние PD При 12 =l и 1 =l я , в обеих частях соотно проверяет- , это приведет к изменению - ва данных . В результате чего, может быть пол шени выполняется Д-оператор )()( 111 DOD ′ , однако, в правой части сос- тояние ожества данных oD мн ся дважды. В случае ∅≠′∩ 1DDo состояния множест oD учено 1=l , что приведет к ыполнению 2 DODв )()( 22 ′ и нарушению ение может выполнено эквивалентности. Специфика рассматриваемой операции такова, что при наличии указанного ограничения разлож быть ),())](()[( )())](()[( ))()()())](( 111 222 222111 2 DODlPD DODlPD DODDODl o o ′ ′= =′∨′ однако аналогичные рассуждения приве- дут к нарушени вивале тности при выполнении с ∅≠′∩ 2DDo . Таким обр ()[( PDo ю эк н оотношения азом, ъю o Утверждение доказано. Исходя из утверждения, можно сделать следующие выводы. В том случае, когда на услови l влияет один из двух Д-операторов, казанное ограничение можно снять за логично м ут дизъюнкций значностью елесообразным. х логических услови н о эквивалентность разложения p2-диз нкции в первом случае обеспечивается ограничением ∅=′∩ 1DDo , а во втором – ∅=′∩ DD . 2 е у счет выбора порядка следования этих Д- операторов. Отметим, что ана ог быть доказаны случаи разложения р- дизъюнкций с большей значностью логических условий. Однако, имеющие место ограничения делают разложение р- с большой логических условий нец Из доказанного утверждения следу- ет, что в случае фиксирующи й, которые по определению не зависят от выполне ия Д- ператоров, на преобразование операции p2-дизъюнкции )()]([)()]([ ))()()) 222111 222111 DODfDODf DODDO ′′ ′∨′ никаких ограничений не накладывается. Теперь покажем возможности оптимизирую их реобразов ий вложен- ных р-дизъюнкций, при выполнени ( = = щ п ан и привед DODDOD DODlPDlPD ′∨′∨ ∨′ Разложим р-дизъюнкцию на ](([ 2 Df енных в утверждении 1 ограниче- ний, и р-итераций. Рассмотрим следующие алгоритми- ческие конструкции: )).()())()( )())]((())]([(()[( 333222 111 2o2o последовательные фильтры ))())](())]([(()[( 111 oo DODlPDlPD ′ )),())]((l()[( ))())](l())]([(l()[( 3 o 222 oo DODPD DODPDPD ′ ′ 33 ение преобразуем в соответствии с соотношениями (2), (3). В результате получаем выражение а полученное выраж ),)())](()[(* )))())]((()[( 333 111 DODlPD ZDODlPD o o ′ ′ 11 Теоретичні та методологічні основи програмування исклю и атор, и свер- нув фильтры в р-дизъюнкцию получим следующий оптимизированный результ т . ( 111 2 12 o 2 2 1 o 1 DODlPDlPD ∨′ (5) 222 111122 DOD DODlPD ′ ∨ (6) 222 DOD ′∨ выражение (6) – к виду 11 2 12 o 2 2 1 o 1 DOD DODlPDlPD ′∨ ∨′∨ Доказательство в данных случаях очевидно, так как эквивалентность этих преобразований определяется сл ми фактами. В соотношении 2 Д-оператор OD ′ выполняется только при истинн ных случаях. В нии 3 Д- ер чив из которого, в соответстви с (1), тождественный Д-опер а ))()()())]((()[( 333111 o DODDODlPD ′∨′ )).()())()( 222222 DODDOD ′∨′∨ )())]((()[( 2o 111 2 1 o 1 DODlPD ′∨ ∨′ )())]((())]([(()[ ))).()( )())]((()[( ∨ Будем утверждать, что выражение (5) преобразуется к виду )())]((()()()[( 11112 o 21 o 1 DODlPDlPD ∨′∧ )),()( а )).()( )())]((()()()[( 222 1 едующи- )()( 111 D ости условий l 2 и 1l 2, а Д-оператор )()( 222 DOD ′ во всех осталь соотноше оп атор )()( 222 DOD ′ ложных выполняется только при 2, а Д-оператор DO ′ во всех тальных случаях. Преоб ется одно р завершени ательно со- : значениях условий l 2 и l1 )()( 111D ос )}}.())]{(())]{[(()[( 11112211 DODlPDlPD oo ′ разуется к виду )}).())]{((P))([(()( 12 111 o 21 o 1 DODlDlPD ′ Из полученного соотношения следует, что предикат )()( lPD 1 o 1 выполня- к атно. Докажем справедли- вость этого от против олагая, что по ю вложенного цикла условие l истинно и применяя последов отношения (4), (2), (3) получаем ного п .))(()( 11 lPDo )})()]{(0)([()( )( 11111 11 11 NZ DODlPD PD o o = =′= = ольку при сделанном предположе- нии п ил е невер 33311 o 1 1 DODlPD ′ ′ В данном случае доказательств служит тождественное соотношение (2), в соответствии с которым, при 333 =′ )}() . В случае, будет выполняться цик телом ))}())]{(())([(( )})())]{(())([(()( 111112 112211 lDODlPDl DODlPDlPD 2 o oo =′ =′ Поск олуч и неопределенный Д-опера- тор, это предположени но и пре- образование эквивалентно. )}).())]{(()[( )}())]{(())]([(()[( 33311 o 1 11111 o 1 2o DODlPD DODlPDlPD ′∨ ∨′ преобразуется к виду ())]{(())]([(()[( 1111 o 1 o DODlPDlPD )}.())]{(()[(* *)}) ом 1)()( = , после выполнения в цикле Д-оператора )D()O(D 111 ′ будет получено такое состояние o 1D , что 0)()( =11 o 1 lPD . В результате – DlPD 11 o 1 )]{(()[( 2o lPD ZDO кода 0)()( =2o lPD л с )()( 333 DOD ′ , а с телом 222 )()( DOD ′ будет пропущен. Данный раздел иллюстрир т возможности преобразования за счет исполь их стр ют ожности соз САА\Д удобные дл ений операции ть, не т и строить эффекти на целево п в л н я пре образований, показанные в работе, пред- ставляющие й интерес, могут уе зования соотношений, характери- зующих общие свойства операций и алгоритмическ кон укций. Заключение Приведенные производные опера- ции демонстриру возм да- вать в рамках я различных прилож . При этом показана возможнос олько строить такие операции, но их с учетом вности реализации м языке рограммирования. Эта возможность, частности с прив ече ием фиксирующих логических условий, пред- ставляетс практически неисчерпаемой. Возможности оптимизирующих самостоятельны быть существенно расширены за счет привлечения тождественных соотно- шений, характерных для различных предметных областей. Обобщение полученных результа- тов и их апробация на конкретных приме- рах является перспективным направлением дальнейших исследований. 12 Теоретичні та методологічні основи програмування 1. Акуловский В.Г. Основы алгебры алгоритмов, базирующейся на данных // Проблеми програмування. – 2010. – № 2 – С -3. оцесса // Проблеми про 319 с. 6. 7. мические модели и 1 Дор док профессор. Григорьевич, ических наук, доцент. ограммных систем .ua. Об авторах: ошенко Анатолий Ефимович, тор физико-математических наук, . 89–96. 2. Акуловский В.Г. Некоторые аспекты формализации данных и декомпозиция Д- операторов // Проблеми програмування. – 2009. – № 4 – C. 3–10. 3. Дорошенко А.Е., Акуловский В.Г. Алгебра алгоритмов с данными и прогнозирование вычислительного пр Акуловский Валерий кандидат техн Место работы авторов: грамування. – 2011. – № 3. – С. 3–10. 4. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – Киев.: Наук. думка, 1978. – . Институт пр НАН Украины, 03187, Киев-187, проспект Академика Глушкова, 40 Тел.: (044) 526 3559. 5. Яблонский С В. Введение в дискретную математику: учебн. Пособие для вузов. – М.: Высш.шк., 2002. – 384 с. Акуловский В.Г. Расширенная алгебра e-mail: or@isofts.kiev.ua d Академия таможенной службы Украины. 49000, г. Днепропетровск, ул. Дзержинского 2\4. алгоритмов // Проблеми програмування. − 2007. − № 3. − C. 3–15. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е. и др. Алгеброалгорит Тел/Факс: (056) 745 55 96, e-mail: academy@amsu.dp методы параллельного программирования. – Киев.: Академперіодика, 2007.– 634 с. Получено 11.07.201 13 mailto:dor@isofts.kiev.ua mailto:dor@isofts.kiev.ua

The construction and transformation of operations and some algorithmic designs of algorithms’ algebra with the data

Репозитарії

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