Алгебра алгоритмов с данными и прогнозирование вычислительного процесса

Развивается алгебраический аппарат, ориентированный на описание алгоритмов с данными, за счет использования k-значных логических условий и прогнозирования вычислительного процесса...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Дорошенко, А.Е., Акуловский, В.Г.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Інститут програмних систем НАН України 2011
Schlagworte:	Теоретичні та методологічні основи програмування
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/50965
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса / А.Е. Дорошенко, В.Г. Акуловский // Пробл. програмув. — 2011. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859954388534034432
author	Дорошенко, А.Е. Акуловский, В.Г.
author_facet	Дорошенко, А.Е. Акуловский, В.Г.
citation_txt	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса / А.Е. Дорошенко, В.Г. Акуловский // Пробл. програмув. — 2011. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — рос.
collection	DSpace DC
description	Развивается алгебраический аппарат, ориентированный на описание алгоритмов с данными, за счет использования k-значных логических условий и прогнозирования вычислительного процесса
first_indexed	2025-12-07T16:18:29Z
format	Article
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
id	nasplib_isofts_kiev_ua-123456789-50965
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Russian
last_indexed	2025-12-07T16:18:29Z
publishDate	2011
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Дорошенко, А.Е. Акуловский, В.Г. 2013-11-07T15:34:55Z 2013-11-07T15:34:55Z 2011 Алгебра алгоритмов с данными и прогнозирование вычислительного процесса / А.Е. Дорошенко, В.Г. Акуловский // Пробл. програмув. — 2011. — № 3. — С. 3-10. — Бібліогр.: 11 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/50965 519.681 Развивается алгебраический аппарат, ориентированный на описание алгоритмов с данными, за счет использования k-значных логических условий и прогнозирования вычислительного процесса ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Алгебра алгоритмов с данными и прогнозирование вычислительного процесса Article published earlier
spellingShingle	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса Дорошенко, А.Е. Акуловский, В.Г. Теоретичні та методологічні основи програмування
title	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса
title_full	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса
title_fullStr	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса
title_full_unstemmed	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса
title_short	Алгебра алгоритмов с данными и прогнозирование вычислительного процесса
title_sort	алгебра алгоритмов с данными и прогнозирование вычислительного процесса
topic	Теоретичні та методологічні основи програмування
topic_facet	Теоретичні та методологічні основи програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/50965
work_keys_str_mv	AT dorošenkoae algebraalgoritmovsdannymiiprognozirovanievyčislitelʹnogoprocessa AT akulovskiivg algebraalgoritmovsdannymiiprognozirovanievyčislitelʹnogoprocessa

Алгебра алгоритмов с данными и прогнозирование вычислительного процесса

Institution

Ähnliche Einträge