Algebra of algorithms with the data and forecasting of computing process

The algebraic apparatus is developed focused on the description of algorithms with data at the expense of use of k-valued logic conditions and forecasting of computing process.Problems in programming 2011; 3: 3-10

Збережено в:

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

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-811
record_format	ojs
resource_txt_mv	ppisoftskievua/77/b69e74886ec194f7c63dfb2c0a8b5677.pdf
spelling	pp_isofts_kiev_ua-article-8112025-08-29T13:29:04Z Algebra of algorithms with the data and forecasting of computing process Алгебра алгоритмов с данными и прогнозирование вычислительного процесса Алгебра алгоритмів з даними та прогнозування обчислювального процесу Doroshenko, A.Yu. Akulovskiy, V.G. UDC 519.681 УДК 519.681 УДК 519.681 The algebraic apparatus is developed focused on the description of algorithms with data at the expense of use of k-valued logic conditions and forecasting of computing process.Problems in programming 2011; 3: 3-10 Развивается алгебраический аппарат, ориентированный на описание алгоритмов с данными, за счет использования k-значных логических условий и прогнозирования вычислительного процесса.Problems in programming 2011; 3: 3-10 Розвивається алгебраїчний апарат, орієнтований на опис алгоритмів з даними, за рахунок використання k-значних логічних умов та прогнозування обчислювального процесу.Problems in programming 2011; 3: 3-10 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-29 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/811 PROBLEMS IN PROGRAMMING; No 3 (2011); 3-10 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2011); 3-10 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2011); 3-10 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/811/863 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-08-29T13:29:04Z
collection	OJS
language	rus
topic	UDC 519.681
spellingShingle	UDC 519.681 Doroshenko, A.Yu. Akulovskiy, V.G. Algebra of algorithms with the data and forecasting of computing process
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	Algebra of algorithms with the data and forecasting of computing process
title_short	Algebra of algorithms with the data and forecasting of computing process
title_full	Algebra of algorithms with the data and forecasting of computing process
title_fullStr	Algebra of algorithms with the data and forecasting of computing process
title_full_unstemmed	Algebra of algorithms with the data and forecasting of computing process
title_sort	algebra of algorithms with the data and forecasting of computing process
title_alt	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса Алгебра алгоритмів з даними та прогнозування обчислювального процесу
description	The algebraic apparatus is developed focused on the description of algorithms with data at the expense of use of k-valued logic conditions and forecasting of computing process.Problems in programming 2011; 3: 3-10
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/811
work_keys_str_mv	AT doroshenkoayu algebraofalgorithmswiththedataandforecastingofcomputingprocess AT akulovskiyvg algebraofalgorithmswiththedataandforecastingofcomputingprocess AT doroshenkoayu algebraalgoritmovsdannymiiprognozirovanievyčislitelʹnogoprocessa AT akulovskiyvg algebraalgoritmovsdannymiiprognozirovanievyčislitelʹnogoprocessa AT doroshenkoayu algebraalgoritmívzdanimitaprognozuvannâobčislûvalʹnogoprocesu AT akulovskiyvg algebraalgoritmívzdanimitaprognozuvannâobčislûvalʹnogoprocesu
first_indexed	2025-09-17T09:23:44Z
last_indexed	2025-09-17T09:23:44Z
_version_	1843502539694145536
fulltext	Теоретичні та методологічні основи програмування УДК 519.681 А.Е. Дорошенко, В.Г. Акуловский АЛГЕБРА АЛГОРИТМОВ С ДАННЫМИ И ПРОГНОЗИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА Развивается алгебраический аппарат, ориентированный на описание алгоритмов с данными, за счет ис- пользования k-значных логических условий и прогнозирования вычислительного процесса Введение Учитывая важность роли, которую данные играют в программировании [1–5], [6, 7] были заложены основы алгебраиче- ского аппарата, в который органично “встроены” данные в результате модифи- кации модели ЭВМ [8]. Упомянутый фор- мальный аппарат это – система алгорит- мических алгебр (САА/Д) , где – множество Д-операторов; L – множе- ство 3-значных логических условий, Ω – сигнатура операций, состоящая из логиче- ских операций Ω >Ω <U, L, U 1, принимающих значения на множестве L и операций Ω2, прини- мающих значения на множестве операто- ров U. Принципиальное отличие предла- гаемого формального аппарата от алгебры Глушкова (АГ) состоит в том, что под ин- формационным множеством в модифици- рованной модели ЭВМ понимаются со- стояния множества данных. Исходя из это- го введено понятие Д-оператора, который в общем случае записывается в виде , где ( ) ( )D X D′ X – Д-оператор, – множе- ство обрабатываемых (исходных), а D D′ – множество результирующих данных, из- менения которых представляют собой из- менения состояния операционного автома- та в модели ЭВМ. Данные и специ- фицируются, соответственно на входе и выходе Д-оператора. D D′ На множестве U определены опера- ции [6]. 1. Операция композиции * Д- операторов озна- чает последовательное выполнение снача- ла оператора и затем оператора . )()()()( 222111 DODDOD ′′ )()( 111 DOD ′ )()( 222 DOD ′ 2. Операция р-дизъюнкции, в ко- торой используется предикат, продуци- рующий логические условия μ}{0,1,α 3 =∈E , существует в следующих вариантах: ⎪ ⎩ ⎪ ⎨ ⎧ = =′ =′ = =′∨′ μ.αесли, 0;αесли),()( 1;αесли),()( ))()()())]((α)[( 222 111 222111 π N DOD DOD DODDODPD ⎩ ⎨ ⎧ ≠′ =′ = =′∨′ 1.αесли),()( 1;αесли),()( ))()()())](α)[( 222 111 222111 π DOD DOD DODDODPD ⎩ ⎨ ⎧ ≠ =′ = =′ 1,αесли, 1;αесли),()( )()()](α)[( 111 111 π Z DOD DODPD где N – неопределенный, а Z – то- ждественный Д-операторы (см. далее). Результатом выполнения этой опе- рации является один из трех (двух) воз- можных Д-операторов, который выбирает- ся в соответствии со значением логическо- го условия α. В предпоследнем случае не- определенное состояние логического усло- вия игнорируется. В последнем случае иг- норируются все значения логического ус- ловия, кроме 1α = . Этот вариант р- дизъюнкции будем называть последова- тельным фильтром (р-фильтром). 3. Операция р-итерации с пред- и постусловиями )}())]{(()~[( DODPD ′α и 3 Паралельне програмування )]()~)}[((){( α′ PDDOD осуществляет цик- лическое выполнение Д-оператора при и завершается в про- тивном случае. ( ) ( )D O D′ 1α = На множестве L определены [6] (см. так же, например, [8]) операции: дизъюнкция, конъюнкция и отрицание. Таким образом, сигнатура данной алгебраической системы Ω включает те же операции, что и АГ. Очевидным недостат- ком предлагаемого формального аппарата является отсутствие операции левого ум- ножения условия на оператор. Так как именно эта операция, реализующая про- гнозирование вычислительного процесса, определяет преимущества АГ перед дру- гими алгебраическими аппаратами, с точки зрения изобразительных возможностей [9, 10]. Кроме того, при отсутствии ограни- чений на сложность Д-операторов логиче- ская составляющая САА/Д (как впрочем, и АГ) ограничена трехзначными логически- ми условиями. То есть, в результате анали- за большого объема сложно организован- ных данных достижимо разветвление вы- числительного процесса только по двум направлениям, что ограничивает изобрази- тельные возможности алгебраического ап- парата. При этом, поскольку предикаты могут быть не определены на множестве анализируемых данных, то алгоритм ока- зывается “незащищенным” от таких ситуа- ций, вызванных, в частности, ошибками разработки. Чтобы восполнить указанные про- белы, дополним и модифицируем разраба- тываемый алгебраический аппарат и пока- жем возможность реализации прогнозиро- вания вычислительного процесса. Алгебры алгоритмов с данными В качестве данных, специфицируе- мых на входе и выходе Д-операторов, вы- ступают оперативные (статические), дина- мические данные и логические условия. Данными называется упорядо- ченная пара , где − носитель дан- ных (фрагмент памяти), S – кортеж значе- ний, хранимый этим носителем данных в текущий момент времени. В частном слу- чае данные называются простыми, когда они в текущий момент времени содержат единственное значение s. Множество дан- ных, расположенных в оперативной памя- ти и обрабатываемых некоторым алгорит- мом, запишем в виде D D Δ, S< > Δ d ОП={D1, D2, Dn}. При этом отметим, что структура любых данных не ограничена по сложности и объему. iD Динамическими данными будем называть кортеж значений S dD d, определен- ный (существующий) в текущий момент времени в динамической памяти, время существования которого ограничено (см. ниже). В частном случае данные назы- ваются простыми, когда они в текущий момент времени содержат единственное значение s dd d. Заметим, что в дальнейшем под обозначением будем понимать dD D= S dS= . К множеству кортежей, которые могут хранить носители данных, присое- диним специальный кортеж Sµ – кортеж неопределенных значений и данные, хра- нящие такой кортеж, будем называть не- определенными и обозначать , а в слу- чае динамических данных . μD μdD Множество логических условий L образовано в общем случае k+1-значными логическими условиями. Это , где µ – неопреде- ленное значение этого логического усло- вия, и всюду определенные логические ус- ловия 1α {0,1,..., 1,μ}k kE k+∈ = − 1α {0,1,..., 1, }k kE k k+ + +∈ = − . В частных случаях логические условия могут быть произвольной значности. В случае трех- значных логических условий и . 2 3α {0,1,μ}E∈ = 2 3α { 0,1,2 }E+ +∈ = В дальнейшем логические условия для самого общего случая будем записы- вать в виде . xα Теперь определим понятия: состоя- ние вычислительного процесса, тождест- венный и неопределенный Д-операторы. Определение 1. Вычислительный процесс на любом, например, i-том шаге выполнения находится в одном из трех возможных состояний: , ОПT i iD D= 4 Теоретичні та методологічні основи програмування ОПT d i iD D D= ∪ i }, , где – текущее состояние множества оператив- ных данных (статическая составляющая), – текущее состояние множества дина- мических данных и – состояние логиче- ского условия (динамическая составляю- щая). Статическая составляющая состоя- ния вычислительного процесса имеет ме- сто на каждом его шаге. Динамическая со- ставляющая определена только на некото- рых шагах вычислительного процесса, то есть ОП αT x i i iD D {= ∪ ОП iD d iD x iα p∃ , где в состоянии и d pD ≠∅ T pD m∃ , где в состоянии . Эта состав- ляющая существует только на данном ша- ге, то есть для любого α x m{ }≠∅ T mD T jD , где pj≠ и mj≠ , выполняется и . d pD =∅ α x m{ }=∅ Определение 2. Д-оператор )()( DXD ′ , в результате исполнения которого будет получено соотношение , будем называть тождественным и обозначать Z. 1 T iD D += T i Определение 3. Д-оператор ( ) ( )D X D′ , который переводит вычислительный про- цесс из любого произвольного состояния в неопределенное состояние , после перехода в которое все последующие шаги вычислительного процесса не определены, будем называть неопределенным и обозна- чать N. T iD γT D Д-операторы образуют следующий базовый набор: – , который переводит вы- числительный процесс из любого исходно- го для него состояния в состояние , где и ; ( ) ( )D O D′ T iD 1 T T i iD D+ ≠ 1 d iD + =∅ i 1{α }x + = ∅ – переводит вычислитель- ный процесс из любого исходного для него состояния в состояние такое, что , где , , . ( ) ( )dD O D T iD T iD 1+ ОП 1 1 T d i iD D D+ += ∪ 1i+ ОП ОП 1i iD D+ = 1 d iD + ≠ ∅ 1{α }x i+ = ∅ – и π( ) (α )kD P π( ) (α )kD P + , которые в даль- нейшем будем называть предикатами, представляют собой в общем случае n- местные логические функции 1 1: ρ α {0,1,..., 1,μ}n n k k D kP E+ +→ ∈ = −k k k 1+ 1+ и , 1 1: ρ α {0,1,..., 1, }n n k k D kP E+ + + +→ ∈ = − где и – k+1-значные логические ус- ловия, продуцируемые предикатами. Этот Д-оператор переводит вычислительный процесс из любого исходного для него со- стояния в состояние такое, что и , где , kα +kα T iD T iD 1+ ОП 1 1 {α }T k i i iD D+ += ∪ ОП 1 1 {α }T k i i iD D + + += ∪ ОП ОП 1i iD D+ = 1 d iD + = ∅, 1{α }k i+ ≠ ∅ и 1{α }k i + + ≠ ∅ . Если T d i iD D⊃ ≠ ∅, то . Если предикат не определен на множестве данных , то и . πd iD D⊆ πD μα =k kk =+α Все возможные Д-операторы обра- зуют множество U, на котором определены операции САА/Д. Дополним совокупность этих операций следующим образом. Операция -дизъюнкции kp π 1 1 1 2 2 2 1 1 1 1 1 1 2 2 2 1 1 1 [( ) (α )](( ) ( ) ( ) ( ) ... ( ) ( ) ( ) ( )) ( ) ( ) если α 1; ( ) ( ) если α 2; . . . . . . . . . . ( ) ( ) если α 0; ( ) ( ) если α . k k k k k k k k k k k k k k k k k D P D O D D O D D O D D O D D O D , k D O D , k D O D , D O D , k + − − − + + + + + + + ′ ∨ ′ ′∨ ∨ ∨ ′∨ = ′⎧ = − ⎪ ′ = −⎪ ⎪= ⎨ ⎪ ′ =⎪ ⎪ ′ =⎩ ∨ = π 1 1 1 2 2 2 1 1 1 1 1 1 2 2 2 [( ) (α )](( ) ( ) ( ) ( ) ... ( ) ( )) ( ) ( ) если α 1; ( ) ( ) если α 2; . . . . . . . . . . ( ) ( ), если α 0; , если α μ. k k k k k k k k k k k D P D O D D O D D O D D O D , k D O D , k D O D N − − − ′ ∨ ′ ′∨ ∨ ∨ ′⎧ = − ⎪ ′ = −⎪ ⎪= ⎨ ⎪ ′ =⎪ ⎪ =⎩ Результатом выполнения этой опе- рации является один из k+1 возможных Д- операторов, который выбирается в соот- ветствии со значением логического усло- вия или . kα +kα В частности, операция - дизъюнкции записывается в виде 2p 5 Паралельне програмування π 2 1 1 1 2 2 2 3 3 3 [( ) ( )](( ) ( ) ( ) ( ) ( ) ( )) D P D O D D O D D O D α + ′ ∨ ′ ′∨ ∨ = = 2 1 1 1 2 2 2 2 2 3 3 1 ( ) ( ) если α 1; ( ) ( ) если α 0; ( ) ( ) если α 2. D O D , D O D , D O D , + + + ′⎧ = ⎪ ′= ⎨ ⎪ ′ =⎩ Результатом выполнения этой опе- рации является один из трех возможных Д-операторов, который выбирается в соот- ветствии со значением логического усло- вия . На множестве логических условий +2α L, продуцируемых предикатами, определены известные (см., например, [11]) операции, образующие множество : 1Ω – обобщенное отрицание α α 1 (mod )k= + ; – обобщенная дизъюнкция ; 1 2 1α α max(α ,α )∨ = 2 – обобщенная конъюнкция . )α,(αminαα 2121 =∧ Для того, чтобы воспользоваться этими операциями, рассмотрим компози- цию предикатов )α()()α()( 22 π 211 π 1 xx PDPD . Потребуем, чтобы при выполнении предикатов, связанных операцией компо- зиция, формировалось логическое условие как результат применения заданных логи- ческих операций к условиям, продуцируе- мым этими предикатами. В соответствии с этим требованием композицию предикатов запишем в виде , где – одна из логических операций. Результатом выпол- нения такой композиции является логиче- ское условие , полученное в результате применения логической операции к усло- виям, связанным этой операцией . )α()()α()( 22 π 211 π 1 xx PDPD o o x Σα xxx 21Σ ααα o= Таким образом, возможности опе- раций р-дизъюнкции и р-итерации расши- ряются, а эти операции будут записаны для случая -дизъюнкции в виде kp π π 1 1 1 2 2 2 1 1 1 2 2 2 1 1 1 [( ) (α ) ( ) (α )](( ) ( ) ( ) ( ) ( ) ( )), k k k k k D P D P D O D O D ... D O D + + + + + D′ ′∨ ∨ ∨ o ′ а для р-итерации, например, с предуслови- ем, в виде π 2 π 2 1 1 1 2 2 2[( ) (α ) ( ) (α )]{( ) ( )}D P D P D O D′o . Для остальных вариантов операций запись аналогична. Композиция предикатов может быть записана в более общем виде )α()(...)α()()α()( π 22 π 211 π 1 x nnn xx PDPDPD ooo . При выполнении такой композиции будет получено логическое условие как результат примене- ния логических операций ко всем этим ус- ловиям. В этом случае вышеприведенные операции будут записаны в виде: x n xxx α...ααα 21Σ ooo= π π 1 1 1 1 1 1 2 2 2 1 1 1 [( ) (α ) ... ( ) (α )] (( ) ( ) ( ) ( ) ( ) ( )) k k n n n k k k D P D P D O D D O D D O D + + + + + ′ ′∨ ∨ ′ o o и 2 π 2 1 1 1[( ) (α ) ... ( ) (α )]{( ) }.n n nD P D P D O(D )π ′o o Для остальных вариантов операций запись аналогична. Использование предикатов указан- ным способом позволяет выполнять опе- рации САА\Д с учетом логических усло- вий неограниченной сложности. В результате увеличения значности логических условий построены операции, позволяющие разветвлять вычислитель- ный процесс по произвольному числу на- правлений. Прогнозирование вычислительно- го процесса Под прогнозированием вычисли- тельного процесса будем понимать, пред- сказание результата выполнения (состоя- ния выходных данных) некоторого Д- оператора ( ) ( )D O D′ , которое определим следующим образом. Определение 4. Прогнозом резуль- тата (или его части) выполнения Д- оператора ( ) ( )D O D′ , который переводит вычислительный процесс из исходного со- стояния T jD в результирующее состояние 1 T jD + , будем называть логическое условие (x j 1α + 1{α }x 1 T j jD+ +⊂ ), характеризующее со- стояние данных D′ ( ОП j 1 1 T jD D D+′⊆ ⊆ + ) (или pp DD ′⊂′′ ), которое было бы получено в 6 Теоретичні та методологічні основи програмування результате выполнения этого Д-оператора, при условии сохранения неизменного со- стояния оперативной памяти . Прогноз трактуется как положительный (удовлетворительный) в случае, когда , и как отрицательный в противном случае, когда , где i – некоторое за- данное значение. ОП ОП j 1 jD D+ = ix j =+1α ix j ≠+1α Будем полагать, что на месте пре- диката в выше приведенных операциях могут быть использованы композиции Д- операторов при том условии, что результа- том выполнения таких композиций явятся логические условия. Предположим и далее это докажем, что композиция Д-операторов позволяет осущест- вить прогнозирование вычислительного процесса. π( ) ( ) ( ) (α )dD O D D P x Исходя из этого предположения, введем понятия. Определение 5. Д-оператор эквивалентен или частично эквивалентен Д-оператору ( ) ( )dD O D )()( ppp DOD ′ , если при после выполнения перво- го будет получено или . pDD = p d DD ′= pp d DDD ′⊂′′= Определение 6. В композиции анализируемым ре- зультатом выполнения Д-оператора является множество данных , а информационным контекстом (в дальнейшем контекстом) этого резуль- тата назовем множество данных , специфицированных на входе предиката и анализируемых им, но не являющихся вы- ходными данными Д-оператора ( . π( ) O( ) ( ) (α )dD D D P x x ( ) ( )dD O D πDDd ⊆ dDD \π ) ( )dD O D Прежде чем доказать возможность выполнения прогнозирования, докажем наличие ограничения на использование композиции вида π( ) ( ) ( ) (α )d xD O D D P полагая, что – динамические данные, специфицированные на входе предиката. πDD d ⊆′ Лемма. В композиции динамические дан- ные, продуцируемые Д-оператором , полностью анализируются пре- дикатом, а все анализируемые предикатом данные определены только при условии выполнения соотношения . π( ) ( ) ( ) (α )dD O D D P ( ) ( )dD O D dd DD ′= Доказательство. Предположим об- ратное. Пусть dD′ =∅ или ∅≠′dd DD \ . В этом случае динамические данные ( , в соответствии с определением Д-оператора) или их часть , в соот- ветствии с определением 6, анализируе- мым результатом не являются, т.е. преди- катом не обрабатываются, а, в соответст- вии с определением 1, будут утрачены на следующем шаге вычислительного про- цесса, что противоречит условию леммы. dD ∅≠dD dd DD ′\ Предположим, что ∅≠′ dd DD \ . По- скольку, в соответствии с определением 1, никаких динамических данных кроме , продуцируемых Д-оператором , на данном шаге вычислительного процесса не существует, то множество динамиче- ских данных , специфицированных на входе предиката, будет неопределен- ным , что противоречит усло- вию леммы. dD ( ) ( )dD O D dd DD \′ μ\ ddd DDD =′ Поскольку при , dD′ =∅ ∅≠′dd DD \ , ∅≠′ dd DD \ условия леммы не выполняют- ся, то единственным возможным соотно- шением, удовлетворяющем условиям лем- мы, является dd DD ′= . Лемма доказана. Теорема 1. Композиция Д- операторов , выпол- няет прогнозирование результата или час- ти результата, который мог бы быть полу- чен после выполнения Д-оператора π( ) ( ) ( ) (α )dD O D D P x )( ) (p p pD O D′ , как с учетом контекста этого результата, так и без него, если эквивалентен или частично эк- вивалентен Д-оператору ( ) ( )dD O D ( ) ( )p p pD O D′ . Доказательство. В результате вы- полнения Д-оператора из ис- ходного состояния вычислительного про- цесса , в соответствии с определением Д-оператора, будет получено состояние ( ) ( )dD O D T iD 7 Паралельне програмування 1 T iD + такое, что , а или , так как по условию теоре- мы Д-операторы и ( эквивалентны или частично эквивалентны. ОП ОП 1iD D += i D O D а (α)( π PD p d DD ′= pp d DDD ′⊂′′= )()( ppp DOD ′ ) ( )dD O D В результате выполнения следую- щего за Д-оператором )d преди- кат )x , для которого, в соответ- ствии с леммой, выполняется соотношение , будет получено логическое ус- ловие , характеризующее состояние данных или в случае частичной эквивалентности. ( ) ( dd DD =′ xα p d DD ′=′ pp d DDD ′⊂′′=′ Поскольку в полученном состоянии вычислительного процесса, в соответствии с определением предиката, , а является характеристикой или ОП ОП 1i iD D += xα pD′ pD ′′ , то, в соответствии с определением 4, логиче- ское условие – прогноз результата вы- полнения Д-оператора или его части. В последнем случае часть вы- ходных данных Д-оператора будет исключена из рассмот- рения. xα )()( ppp DOD ′ pD \ D′ p′′ )()( ppp DOD ′ В случае, когда , то, в соответствии с определением 6, получаем прогноз с учетом контекста, а при без него. ∅≠dDD \π ∅=dDD \π Теорема доказана. Отметим, что, в соответствии с оп- ределением 4, если логическое условие равно некоторому заданному значению , то прогноз трактуется как положи- тельный, а в противном случае, при , как отрицательный. ix =α ix ≠α Проиллюстрируем возможности прогнозирования вычислительного про- цесса на примере -дизъюнкции, предпо- ложив, что необходимо осуществить про- гноз выполнения Д-оператора kp )()( ppp DOD ′ и, что ему эквивалентен или частично эк- вивалентен Д-оператор . ( ) ( )dD O D Заметим, что Д-оператор, относи- тельного которого осуществляется прогно- зирование, может быть как включен в чис- ло Д-операторов, из которых операцией р- дизъюнкции осуществляется выбор, так и исключен из него. То есть, в случае поло- жительного прогноза в первом случае ( ) операция р-дизъюнкции приведет к выполнению Д-оператора а во втором ( ) – px =α π 1 1 1 1 1 1 [( ) ( ) ( ) (α )](( ) ( ) .. ... ( ) ( )) ( ) ( ), d k k k k p p p D O D D P D O D D O D D O D+ + + ′ ∨ ′ ′∨ = . . ix =α π 1 1 1 1 1 1 [( ) ( ) * ( ) (α )](( ) ( ) .. ... ( ) ( )) ( ) ( ). d k k k k i i i D O D D P D O D D O D D O D+ + + ′ ∨ ′ ′∨ = В случае отрицательного прогноза будет выбран Д-оператор, в соответствии с полученным значением логического усло- вия. При использовании операции р- фильтрации и положительном прогнозе в первом случае будет выполнен Д- оператор, относительно которого осущест- влялось прогнозирование 1α 2 = π 2[( ) ( ) * ( ) (α )]( ) ( ) ( ), d p p p p p p D O D D P D O (D ) D O D ′ = ′= во втором – π 2[( ) ( ) * ( ) (α )]( ) ( ) ( ) ( ). d i i i i i i D O D D P D O D D O D ′ = ′= В случае отрицательного прогноза ни один из Д-операторов выполнен не бу- дет. Прогнозирование осуществимо для нескольких Д-операторов в случае ис- пользования композиции конструкций (см. (1)). Последний пример в этом случае при положительном прогнозе записывается в виде π( ) ( ) ( ) (α )dD O D D P x ) π 1 1 1 1 1 π 1 1 1 2 2 2 1 1 1 [(( ) ( ) ( ) (α )) ... ... (( ) ( ) * ( ) (α ))] (( ) ( ) ( ) ( )) ( ) ( ), d x d x n n n n n n n n n n n n k n K n k D O D D P D O D D P D O D D O D D O D + + + + + + + + + + + + ′ ′∨ = ′= o o где Д-операторы 1 1( ) ( ), ..., ( ) (d d n nD O D D O D эквивалентны или частично эквивалентны Д-операторам )()(),...,()( nsnsnssss DODDOD +++ . Для того, чтобы расширить воз- можности прогнозирования, дополним множество Д-операторов ещё одним ви- дом, который назовем инверсные Д- 8 Теоретичні та методологічні основи програмування операторы и которые определим следую- щим образом. Определение 7. Инверсным по от- ношению к Д-оператору (D азовем Д-оператор )() DO ′ н )()( OD′ ой, что если Д- оператор (D переводит вычисли- тельный процесс из состояния D так DO ′ )() T jD в со- стояние 1 T jD + такое, что T jD D⊆ , 1 T jD D +′ ⊆ , то Д-оператор )()( DOD′ переводит этот процесс из состояния , где , в состояние , где . При этом из следует . T iD T iD D′ ⊆ T iD 1+ 1 T iD D +⊆ 1 T T i jD D += 1 T T i jD D+ = Из определения следует, что )()( DOD′ выполняет операцию “откат вы- числительного процесса” (в дальнейшем откат). Для композиции этих Д-операторов выполняется ZDODDOD =′′ )()()()( . На использование Д-оператора )()( DOD′ на- кладывается следующее жесткое ограни- чение. Д-оператор предшеству- ет Д-оператору )()( DOD ′ )()( DOD′ , и в промежутке между выполнением первого и второго со- стояние оперативной памяти не может из- меняться. Покажем, что с помощью введенно- го Д-оператора может быть осуществлено прогнозирование с учетом его результата. Теорема 2. При использовании операции р-фильтрации в виде )())]((α)()()[( 2π DODPDDOD ′′ ло- гическое условие является прогно- зом результата выполнения Д-оператора , в случае – это логиче- ское условие прогнозом не является. 1α2 = )()( DOD ′ 0α2 = Доказательство. В соответствии с определением Д-операторов, после выпол- нения Д-оператора вычисли- тельный процесс перейдет из исходного состояния )()( DOD ′ T jD в состояние 1 T jD + такое, что OП OП 1j jD D D+′ ⊆ ≠ , а после выполнения пре- диката в состояние 2 T jD + такое, что OП OП 1 2j jD D+ += и 2 2{α } T jD +⊆ . Если , то выполняется Д- оператор 1α2 = (D)OD )( ′ , который, в соответст- вии с определением 7, вернет вычисли- тельный процесс в исходное состояние T jD . Таким образом, логическое условие , в соответствии с определением 4, яви- лось прогнозом результата выполнения Д- оператора ( ) 2α ( )D O D′ . Если , то Д-оператор 0α2 = ( ) ( )D O D′ , не выполняется и вычисли- тельный процесс остается в состоянии 1 T jD + таком, что OП OП 1j jD D+ ≠ , т.е. логическое усло- вие требованиям определения 4 не от- вечает и, соответственно, прогнозом не является. Теорема доказана. 2α Для остальных вариантов операции р-дизъюнкции доказательство выполняется аналогично. Заключение Учитывая отсутствие ограничений на объем и сложность структуры обраба- тываемых и анализируемых данных, САА\Д дополнена k-значными логичес- кими условиями. В результате чего полу- чена возможность разветвления вычисли- тельного процесса по неограниченному количеству направлений. Причем, трак- товка получаемых значений логических условий достаточно произвольна. Напри- мер, при сравнении двух структур данных может быть определено не только совпа- дение или несовпадение этих данных, а и степень их совпадения. И алгоритм может разветвляться по стольким направлениям, сколько уровней совпадения анализируе- мых данных нас интересует. То есть, алго- ритм может быть структурирован и разбит на модули в соответствии со спецификой обработки данных. Это особенно актуаль- но для описания алгоритмов, ориентиро- ванных на обработку больших объемов сложно организованных данных. Кроме того, всюду определенные логические ус- ловия обеспечивают наличие элементов защитного программирования. В процессе декомпозиции Д- операторов и, соответственно, данных бу- дут использоваться логические условия все меньшей значности. Этот процесс завер- шится, когда будет достигнут такой уро- вень детализации, который может быть 9 Паралельне програмування реализован на выбранном целевом языке программирования. Несмотря на отсутствие в числе ба- зовых операций САА\Д операции левого умножения условия на оператор, нам уда- лось реализовать прогнозирование вычис- лительного процесса, обеспечив, таким об- разом, изобразительные возможности аде- кватные, возможностям алгебры Глушко- ва. Направление дальнейших иссле- дований – преобразование алгоритмов, описанных средствами САА\Д, и их распа- раллеливание. 1. Данные в языках программирования: абст- ракция и типология. Сб. статей / Под ред. В. Агафонова. – М.: Мир, 1982 – 328 с. 2. Холл П. Вычислительные структуры: введе- ние в нечисленное программирование. – М.: Мир, 1978 – 214 с. 3. Шнейдерман Б. Психология программиро- вания: человеческие факторы в вычисли- тельных и информационных системах. – М.: Радио и связь, 1984 – 304 с. 4. Bastani F.B., Iyengar S.S. The effect of data structures on the logical complexity of pro- grams // CACM. – 1987. V. 30, N 3, – P. 250 – 259. 5. Методология и технология программиро- вания. – М.: Информприбор, 1989. – 40 с. 6. Акуловский В.Г. Основы алгебры алгорит- мов, базирующейся на данных // Проблеми програмування. – 2010. – № 2-3. – С. 89 – 96. 7. Акуловский В.Г. Некоторые аспекты форма- лизации данных и декомпозиция Д- операторов // Проблеми програмування. – 2009. – № 4 – C. 3 – 10. 8. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – Ки- ев: Наук. думка, 1978. – 319 с. 9. Ф.И. Андон, А.Е. Дорошенко, Г.Е. Цейтлин, Е.А. Яценко. Алгеброалгоритмические моде- ли и методы параллельного программирова- ния. – К.:Академперіодика, 2007. – 634 с. 10. Цейтлин Г.Е. Введение в алгоритмику. – Киев: Сфера, 1998. – 310 с. 11. Яблонский С.В. Введение в дискретную ма- тематику: учебн. Пособие для вузов / Под. Ред. В.А. Садовниченко. – 3-е изд., стер. – М.: Высш. шк., 2002. – 384 с. Об авторах: Дорошенко Анатолий Ефимович, доктор физико-математических наук, про- фессор, заведующий отделом теории ком- пьютерных вычислений Института про- граммных систем НАН Украины Акуловский Валерий Григорьевич, кандидат технических наук, доцент кафед- ры информационных систем и технологий Академии таможенной службы Украины. Место работы авторов: Институт программных систем НАН Украины, 03187, Киев просп. Академика Глушкова, 40, корп. 5. тел.: (044) 526 3559. e-mail: dor@isofts.kiev.ua Академия таможенной службы Украины. 49000, Днепропетровск, ул. Дзержинского 2 / 4. моб. тел.: 050 941 0566 e-mail: valeryakulovskiy@rambler.ru 10 http://mail.rambler.ru/mail/mail.cgi?mode=compose;mailto=valeryakulovskiy%40rambler.ru;83ec;enc=utf-8

Algebra of algorithms with the data and forecasting of computing process

Репозитарії

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