Расширенная алгебра алгоритмов

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

Full description

Saved in:

Bibliographic Details
Date:	2007
Main Author:	Акуловский, В.Г.
Format:	Article
Language:	Russian
Published:	Інститут програмних систем, журнал "Проблеми програмування" 2007
Subjects:	Теоретичні та методологічні основи програмування
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/296
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Расширенная алгебра алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2007. — N 3. — С. 3-15. — Библиогр.: 12 назв. — рус.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860193717346893824
author	Акуловский, В.Г.
author_facet	Акуловский, В.Г.
citation_txt	Расширенная алгебра алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2007. — N 3. — С. 3-15. — Библиогр.: 12 назв. — рус.
collection	DSpace DC
description	Предложен формальный аппарат (расширенная система алгоритмических алгебр), ориентированный на детальную разработку алгоритмов с учетом особенностей языка, на котором будет реализован алгоритм, с использованием трехзначной логики и декларативных знаний совместно с процедурными. Показаны возможности формального преобразования алгоритмов и построения производных алгоритмических конструкций. Приведены примеры использования формального аппарата.
first_indexed	2025-12-07T18:07:44Z
format	Article
fulltext	Теоретичні та методологічні основи програмування © В.Г. Акуловский, 2007 ISSN 1727-4907. Проблеми програмування. 2007. № 3 3 УДК 519.681 В.Г. Акуловский РАСШИРЕННАЯ АЛГЕБРА АЛГОРИТМОВ Предлагается формальный аппарат (расширенная система алгоритмических алгебр), ориентированный на детальную разработку алгоритмов с учетом особенностей языка, на котором будет реализован алго- ритм, с использованием трехзначной логики и декларативных знаний совместно с процедурными. По- казаны возможности формального преобразования алгоритмов и построения производных алгоритми- ческих конструкций. Приведены примеры использования формального аппарата. Введение Система алгоритмических алгебр, разработанная В.М. Глушковым и его уче- никами [1–3], называемая обычно алгебра алгоритмов Глушкова (в дальнейшем ал- гебра алгоритмов), хорошо зарекомендо- вала себя при решении весьма широкого класса задач, подтверждая, таким образом, перспективность использования алгебраи- ческого аппарата в рамках прикладной теории алгоритмов (алгоритмики, в терми- нах Г.Е. Цейтлина [4]). Данная теория, как и любая другая, развивается, а предлагае- мая работа – очередной шаг в направлении её развития. Предпосылками к выполнению данной работы явилось следующее. Первым побудительным мотивом послужили критические оценки архитек- туры современных ЭВМ, высказанные в ряде публикаций, в частности Кнута [5] и разработчика трехзначной ЭВМ «СЕ- ТУНЬ» Н.П. Брусенцова [6]. Последний утверждает [7]: “… ущербность современных компьютеров обусловлена тем, что логические выводы, которыми они оперируют, исчерпываются дискретной двоицей – "да", "нет", а иные модальности аксиоматически отсечены "законом исключенного третьего", что не согласуется с тем, как устроен и функцио- нирует природный мир. В тоже время трехзначная логика не только вполне кор- ректна и адекватна действительности, но является даже более удобной и привычной для людей формой мышления”. Это ут- верждение иллюстрируется примером ветвления по знаку величины Х (рисунок). В рассматриваемом примере троич- ное ветвление по знаку величины Х опи- Рисунок. Ветвление по знаку x>0 x=0 x<0 Вход sign(x) а – Троичная схема x=0 x<0 x>0 Вход x>0 x<0 да да нет нет б – Двоичная схема Теоретичні та методологічні основи програмування 4 сано заданием единственной трехзначной операции sign(Х) и выполняется за один шаг, в то время как такое же ветвление, осуществляемое средствами двузначной логики, связано с необходимостью двух операций и выполняется, вообще говоря, за два шага. Поскольку преимущество трехзнач- ной логики в приведенном примере, оче- видно, то можно с достаточной уверенно- стью рассчитывать на то, что многие ал- горитмические построения в трехзначной логике могут быть реализованы более ком- пактно и эффективно, обеспечивая качес- тво создаваемых алгоритмов и программ. Учитывая, что нечто выразимое в трехзначной логике выразимо и в двузнач- ной, можно использовать преимущества трехзначной логики в разработках для со- временных (двухзначных) ЭВМ. Появле- ние же трехзначных компьютеров, когда и если это произойдет, позволит повысить качество реализации алгоритмов, пос- троенных с использованием трехзначной логики. Во-вторых. Известно, что качество разрабатываемого алгоритма в существен- ной мере зависит от соответствия средств его описания специфике решаемой задачи. В-третьих. Известно также, что чем детальнее, с учетом всех нюансов, разра- ботан алгоритм, тем меньше проблем воз- никает на последующих этапах разработки программного изделия. При этом чем де- тальнее разрабатывается алгоритм, тем больше открывается возможностей для формальных его преобразований. Однако возможности его детализации определя- ются в существенной мере соответствием, используемых средств разработки алгорит- ма, изобразительным возможностям целе- вого языка, т.е. языка программирования, на котором этот алгоритм будет записан. В-четвертых. Исторически в про- граммировании сложилась ситуация, при которой в большинстве случаев использу- ются процедурные знания, т. е. знания, растворенные в алгоритмах. А декларатив- ные знания − знания, отделенные от алго- ритма, используются в системах, основан- ных на знаниях (экспертные системы, ло- гическое программирование и т.п.). Представляется интересным и пер- спективным использование декларативных знаний совместно с процедурными в рам- ках единого формального аппарата, так как это позволит расширить область примене- ния этого формального аппарата на новые классы задач и упростить (в некоторых случаях) решение задач традиционных. Исходя из приведенных предпосы- лок, можно сказать, что основной задачей, решаемой в данной работе, является разра- ботка расширенной алгебры алгоритмов, которая обеспечивает следующие допол- нительные возможности: использование преимуществ трех- значной логики при разработке алгоритмов (следует отметить, что трехзначная логика использовалась в алгебре алгоритмов, од- нако в данной работе мы попытаемся испо- льзовать её возможности в полной мере); построение алгоритмических кон- струкций, ориентированных на конкрет- ные приложения, с приемлемым качеством их реализации; детализация алгоритмов до уровня, на котором программисту уже практически не приходится принимать алгоритмиче- ских решений, в частности, за счет учета особенностей целевого языка программи- рования; использование декларативных зна- ний в задачах, где в этом возникает по- требность или где это просто удобней. При этом, естественно, необходимо сохранить положительные свойства ал- гебры алгоритмов, в частности, возможно- сти преобразования алгоритмов с целью их оптимизации. 1. Система алгоритмических алгебр Для разработки алгебраической системы В.М. Глушковым была предло- жена известная абстрактная модель функ- ционирования ЭВМ, которая представляет собой схему взаимодействия двух ав- томатов управляющего – U и операцион- ного – O. Выходные сигналы А управляю- щего автомата U отождествляются с опе- Теоретичні та методологічні основи програмування 5 раторами, которые изменяют состояние операционного устройства O. Выходные сигналы операционного автомата O, пред- ставляют собой значения различных эле- ментарных логических условий α, опреде- ленных на операционном устройстве. Множество М состояний операционного автомата O называется информационным множеством. Уточним данную модель следую- щим образом. Разобъем множество М на два подмножества М=MS ∪ MD, где MS – статическая составляющая, которая постоянно определена и которая может интерпретироваться, как оператив- ная память; MD – динамическая составляющая, которая отражает динамические измене- ния состояния множество М, не фикси- руемые в памяти. Эта составляющая оп- ределена (доступна для анализа) только сразу после выполнения некоторых опера- торов и не определена во всё остальное время. MD может интерпретироваться, как регистровая память. Таким образом, возникает необхо- димость включить в рассмотрение два ви- да операторов (изменяющих состояние MS и изменяющих состояние MD), посту- пающих на вход операционного устрой- ства О. Для описания алгоритмов рассмот- рим двухосновную алгебраическую сис- тему, основами которой являются множе- ство операций и множество логических условий. Пусть < U, W, Ω > - САА, где U – множество операторов; W – множество логических условий; Ω – сиг- натура операций, состоящая из логических операций – Ω1, принимающих значения на множестве W и операций – Ω2, прини- мающих значения на множестве операто- ров U. Выделим на множестве операторов два подмножества UUU ′′∪′= , где опе- раторы из множества U ′ изменяют стати- ческую составляющую MS множество М состояний операционного автомата O, пе- реводя его в новое состояние: ,)( mmA ′= MSmm ∈,∀ ′ , UA ′∈∀ ; а операторы из множества U ′′ изменяет его динамическую составляющую МD: ,)( mmA ′=′ MSm∈∀ , MDm ∈∀ ′ , U ′′′∈A∀ и только после выполнения этих операторов эта составляющая MD определена. Можно сказать (в программистской терминологии), что оператор UA ′∈ отли- чается от оператора UA ′′′∈ тем, что пер- вый выполняет операции присваивания, а второй таких операций не содержит. Множество операторов U вклю- чают пустой оператор E, не изменяющий состояния информационного множества, т. е. ,)( mmE = Mm∈∀ . Для того чтобы ввести понятие не- определенного оператора N присоединим к информационному множеству М специ- альное неопределенное состояние ν. Будем трактовать неопределенный оператор как ошибочный (недопустимый), выполнение которого N(m) = ν переводит операцион- ный автомат O в состояние, после пере- хода в которое его дальнейшее функцио- нирование будем считать неопределенным. Множество логических условий ра- зобъем на два подмножества ,FPW ∪= где P – множество всюду определенных на множестве М предикатов, результатом вычисления которых является логическая переменная α, характеризующая текущее состояние операционного автомата О. Со- стояние операционного автомата О при вычислении предиката p Pp∈∀ не изменя- ется, т. е. mmmp == )()( α , Mm∈∀ . F – множество логических условий, такое, что для любого оператора Ux∈ , результат применения которого x(m)m =′ к текущему состоянию m )m(m, M∈′ выполняется )m(m)( ′= ff для любого Ff ∈ . Другими словами, условия множе- ства F сохраняют свои значения незави- симо от действия операторов множества U и называются фиксирующими, так как по- зволяют сохранить (зафиксировать) теку- щее состояние операционного автомата О. Отметим, что фиксирующие логи- ческие условия не являются чем-то прин- ципиально новым в программировании, так как они, по видимому, всегда исполь- Теоретичні та методологічні основи програмування 6 зовались на практике под именами “флаж- ки”, ”признаки” и т.п. В данном случае это средство только формализовано в соот- ветствующем контексте. (В дальнейшем для краткости и там где это не затруднит понимания, вместо термина фиксирующее логическое условие будем использовать термин – “фиксирую- щее условие”, а в некоторых случаях про- сто – “условие”). Элементы множества P и F прини- мают истинные значения трехзначной ло- гики Е3 = {0, 1, µ}, где 0 – ложь, 1 – ис- тина, µ – промежуточное значение. (Отме- тим, что вместо традиционного термина – неопределенность будем использовать термин промежуточное значение, так как это значение в работе не трактуется как неопределенное). На множестве Е3 введено отноше- ние порядка < так, что 0 < µ < 1. К логическим операциям системы Ω1 относятся следующие обобщенные операции со своими таблицами истинно- сти [8]: α¬ − инверсия, обобщение опера- ции отрицания (табл. 1); αr − циклическое отрицание (табл. 2); дизъюнкция и конъюнкция =∨ βα ),,max( βα= ),min( βαβα =∧ (табл. 3). Обобщенные булевы операции удо- влетворяют всем законам булевой алгебры, кроме закона исключенного третьего и за- кона противоречия. Очевидно, однако, выполняется за- кон исключенного четвертого ∨∨αα r 1∨ =α rv и закон аналогичный закону проти- воречия 0∧∧ =ααα rrr . Кроме этих операций определим три операции левого умножения Левое умножение ppppBBBB ′ предиката P∈ p на оператор UB ′′′∈ представляет собой условие α, характеризующее со- стояние M, которое было бы получено после выполнения оператора UB ′∈ , од- нако статическое состояние MS операци- онного автомата O при этом остается не- изменным, так как: ,)( )())((p(m)B mmm mmpmBp =′∪= =′∪=′=′ α MD.mMS,m ∈′∀∈∀ Смысл оператора состоит в прогнозирова- нии вычислительного процесса. Таблица 1 α α¬ 0 1 µ µ 1 0 Таблица 2 α αr 0 µ µ 1 1 0 Таблица 3 α β βα ∨ βα ∧ 0 0 0 0 0 µ µ 0 0 1 1 0 µ 0 µ 0 µ µ µ µ µ 1 1 µ 1 0 1 0 1 µ 1 µ 1 1 1 1 Теоретичні та методологічні основи програмування 7 Левое умножение фиксирующего усло- вия на предикат pf где P∈ p , а Ff∈ . Для фиксации текущих значений состояния M операционного автомата вве- дем операцию левого умножения фикси- рующего условия на предикат следующим образом: mmf ′== )((m) α [ p ] , MSmMm ∈∀,∈∀ ′ , где }{∪ fmm =′ , а )(mf α= . То есть, текущее значение состоя- ния операционного автомата O фиксиру- ется как элемент множества MS, позволяя сохранять историю вычислительного про- цесса. Левое умножение фиксирующего усло- вия на оператор fb x Для управления состоянием фик- сирующих условий присоединим к мно- жеству U элементарный оператор xb , ко- торый изменяет состояние условия Ff ∈ в результате применения операции левого умножения этого оператора на фиксирующее условие mmfb x ′=)( , MSmm ∈′∀ , , где =′m }{∪ fm , xf = , 3Ex ∈ . Таким образом, может быть уста- новлено произвольное состояние фикси- рующего логического условия в границах, определяемых значностью логики. Воз- можность управления состоянием фикси- рующих логических условий является до- полнительным средством управления хо- дом всего вычислительного процесса. Для операторов из U введем следующие операции Композиция А∗∗∗∗В (последователь- ное выполнение). Композиция оператора А и В UBA ∈,∀ означает последователь- ное выполнение сначала оператора А и затем оператора В. Иными словами: m)mB(B(A(m))B)(m)(A ′′=′== , MS∈,,∀ mmm ′′′ . Эта операция обладает свойством ассоциативности (AB)C=A(BC) и для нее выполняются тождества AE=EA=A, где Е тождественный оператор, AN=NA=N, (1) где N неопределенный оператор. (Символ ∗ между операторами в очевидных случаях будем опускать, т. е. ABBA = ). Операция αααα3 – дизъюнкция [αααα] (A ∨∨∨∨ B∨∨∨∨ С). Эта операция ориентирована на использование трехзначных логических условий:      = = = = ,(m) если ),( ;0(m) если ),( 1;(m) если ),( )( µα α α mC mB mA mD т. е., выполняется один из трех возможных операторов, который выбирается в соот- ветствии со значением логического усло- вия α, принимающего истинные значения трехзначной логики Е3. αααα −−−− итерация }{Aα (соответствует программной конструкции WHILE). Опе- рация α-итерации оператора А по усло- вию α, примененная к некоторому со- стоянию информационного множества Mm∈ , состоит сначала в проверке усло- вия α. Затем, если α истинно, применя- ется оператор А и вновь проверяется ус- ловие α. Этот циклический процесс, со- стоящий в проверке условия α и выпол- нении оператора А при истинном α, осу- ществляется до тех пор, пока условие α не станет ложным, чем в этом случае завер- шается выполнение α-итерации. Для этой операции выполняются такие тождест- венные соотношения: { } { } ααα ¬= AA (2) { } Ν=Eα , (3) где E – тождественный, а N – неопреде- ленный оператор. { } Ε=A0 , (4) где 0 – тождественно ложное условие, а Е – тождественный оператор. { } Ν=A1 , где 1 – тождественно истинное условие, а N – неопределенный оператор. Теоретичні та методологічні основи програмування 8 В последнем случае следует обра- тить внимание на тот факт, что сущест- вует достаточно широкий класс систем управления (например, системы управле- ния нижнего уровня иерархических АСУ ТП, реализуемые на программируемых контроллерах), для которых оператор ви- да }{A1 , называемый бесконечным циклом, не только применим, но и необходим. По- этому, введем дополнительную операцию цикла Aα , которая полностью экви- валентна операции α − итерация, но для которой выполняется соотношение NA ≠ 1 . В качестве логического условия α в операторе α3 – дизъюнкция и α − итерация могут выступать p-предикат, f – фикси- рующее условие и операции левого умно- жения pB ′ и pf. Отметим, что операция левого умножения pf может использовать- ся не только в указанных операциях, но и как самостоятельная конструкция, с помо- щью которой формируется значение фик- сирующего условия. Результатом данного раздела (и ос- новным результатом всей работы) является расширенная система алгоритмических алгебр (САА-Р), возможности которой ре- шать выше поставленные задачи демонст- рируются в следующих разделах. 2. Производные операции САА-Р Очевидно, что качество разрабаты- ваемых алгоритмов, учитывая их многооб- разие, несомненно и существенно зависит от изобразительных возможностей, пре- доставляемых средствами их разработки. Предлагаемая САА-Р позволяет строить производные операции, учитывающие специфику разрабатываемых алгоритмов и целевого языка программирования. Про- демонстрируем это на примерах наиболее широко используемых конструкций: αααα – дизъюнкция (соответствует программной конструкции ЕСЛИ...ТО…. .....ИНАЧЕ) вводится, как частный слу- чай α3 – дизъюнкции: [α] (A ∨ B) = [α] (A ∨ B∨ ∨ E), таким образом .∈∀ ;0)(),( ;1)(),( ))(∨]([ Mm mеслиmB mеслиmA mBA    = = = α α α Эту операцию удобно использовать в тех случаях, где возможности трехзнач- ной логики излишни, например, при срав- нении двух величин на равенство. αααα-фильтрация (последовательная фильтрация) [ ]( )Aα , которая соответству- ет программной конструкции ЕСЛИ... …ТО... и является частным случаем α - дизъюнкции: ( ) )∨]([][ EAA αα = и обеспечивает выполнения оператора А только при истинном значении α. Для этой операции справедливы такие тожде- ственные соотношения: ( ) ( )AA ][)]([][ ααα = , (5) ( ) EA =¬ )]([][ αα . (6) continue – ( ) }][{ BcontinueA βα , операция позволяет перейти к следующей итерации цикла до завершения предыду- щей, т. е., эта операция адекватна одно- именному оператору языков программи- рования. Воспользовавшись операцией последовательной фильтрации, получаем }{ }{ )]([)]([ BАBcontinueА ββ αα ¬= , где фильтрующее условие β позволит пропус- тить оператор B и перейти к очередной итерации. break – })]([{ BbreakA βα , опе- рация соответствует одноименному опера- тору в языках программирования и позво- ляет прервать в любой момент выполнение цикла, потребность, в чем возникает дос- таточно часто. Для реализации осуществляемого оператора воспользуемся вспомогатель- ным фиксирующим условием f: }{ }{ )]([)]([ 0 ∧ 1 BfbAfbBbreakA f ∨= ββ αα . В построенной конструкции усло- вие f устанавливается в исходное истинное состояние для входа в цикл. В цикле при Теоретичні та методологічні основи програмування 9 истинном условии β (условии завершения цикла) α – дизъюнкция приводит к уста- новке условия f в состояние ложь, в ре- зультате чего оператор В не будет выпол- нен и цикл завершится (по условию f∧α ), а в противном случае (при лож- ном β) выполняется оператор В и цикли- рование продолжается. Переключатели − удобные во многих случаях производные операции, которые позволяют сократить размер и сделать более понятным алгоритм, содер- жащий вложенные α – дизъюнкции, кото- рый запишем следующим образом: .∏ ,..., ,..., )...)∨]([∨... ...∨]([∨]([∨]([ 21 21 332211       = k k kk AAA EA AAA αααα ααα Аналогично строится операция для более общего случая вложенных α3- дизъюнкций: . ,...,, ,...,, ,...,, )...)A∨]([∨... ...∨∨]([∨]([ ∏ 21 21 21 k 322211           =∨ ∨ k k k kk BBB AAAEA AAAA ααα α αα При построении производных опе- раций необходимо учитывать возможно- сти целевых языков реализовывать новые операции. В противном случае, вновь соз- данная удобная алгоритмическая конст- рукция при её реализации на некотором языке программирования может столь существенно понизить эффективность по- лученного программного продукта, что его использование окажется неприемле- мым. Проиллюстрируем справедли- вость этого утверждения следующим примером. В работе [4] приведена производ- ная операция цикла вида }{ ,][ AB α где контроль условия циклирования осущест- вляется в середине цикла. Реализация такого оператора не вы- звала бы никаких затруднений при его реализации на Ассемблере (по крайней ме- ре, для процессора 80х86), но она отсутст- вует в большинстве современных языков программирования. Реализация данной операции в виде }{ }{BAAAB αα =][ имеет тот недостаток, что оператор A записыва- ется дважды. Если же оператор А доста- точно объемен, а операция используется достаточно часто, то это может привести к такому увеличению алгоритма, а в послед- ствии и программы, что возникшие из- держки сделают применение этой конст- рукции недопустимой. В связи с этим рассмотрим возмож- ность реализации данного оператора дру- гим (одним из возможных) способом и за- пишем его в виде }{ }{ )∨]([][ 01 fbABfbAB f αα = . Данная реализация выполняется следующим образом. Мы ввели служеб- ное фиксированное условие f и, используя элементарные операторы 1b и 0b , устанав- ливаем соответственно истинное и лож- ное значения этого условия. Оператор 1b устанавливает исходное истинное значе- ние условия f (параметр цикла) для входа в цикл. В котором выполняется оператор B и при истинном условии α операция α-дизъюнкция выполняет оператор A. Цикл выполняется до тех пор, пока усло- вие α не примет значение ложь. В этом случае оператор A не будет выполнен, а условие f будет установлено в ложное со- стояние оператором 0b , что и приведет к завершению цикла. В данном случае некоторая гро- моздкость полученного выражения не должна смущать, так как дополнительно используемые операторы элементарны по определению и не могут оказать сущест- венного влияния на эффективность созда- ваемого оператора. Реализовать его мож- но практически на любом языке програм- мирования. Производные операции, приведен- ные в этом разделе, демонстрируют воз- можности, предлагаемого формального аппарата, создавать удобные для различ- ных приложений алгоритмические конст- рукции (операции), а так же конструкции, Теоретичні та методологічні основи програмування 10 адекватные возможностям языков про- граммирования. При этом показана воз- можность, не только строить такие конст- рукции, но и строить их с учетом эффек- тивности реализации на целевом языке программирования. И хотя, приведенные операции, могут использоваться для ре- шения практических задач, главным ре- зультатом следует считать иллюстрацию практически неограниченных возможно- стей конструирования новых операций. 3. Эквивалентные преобразования элементарных алгоритмических конструкций Повышение качества любой про- граммы, достигается наиболее результа- тивно на этапе разработки алгоритма этой программы. А наиболее эффективным средством преобразования является фор- мальный аппарат, с помощью которого описывается алгоритм. Таким аппаратом является расширенная алгебра алгоритмов с развитой системой соотношений, позво- ляющей осуществлять глубокие эквива- лентные преобразования. Эквивалентными, в данном случае, считаются такие, и только такие алгорит- мические конструкции, которые описыва- ют действия, приводящие к одинаковым результатам. В данной работе будем рассматри- вать соотношения, характеризующие об- щие свойства регулярных схем (РС), и продемонстрируем возможности эквива- лентных преобразований, широко исполь- зуемых элементарных алгоритмических конструкций (некоторые аспекты этой проблемы рассмотрены в [9]). Рассмотрим возможность разложе- ния операции α − дизъюнкции на последо- вательные фильтры: .)(][)]([)∨]([ BABA ααα ¬= Отличие правой части выражения от левой заключается в том, что в правой части логическое условие α проверяется дважды. И после выполнения оператора А, в случае истинности последовательно- го фильтра по условию α, этот оператор может повлиять на состояние логическо- го условия, нарушив эквивалентность вы- полнения. Наложив ограничение на опе- ратор А такое, что он не изменяет логиче- ского условия α, обеспечим эквивалент- ность преобразования. Если выполнить такое ограничение не удается оператор можно переписать в виде ,)А](α[)B(]α¬[=)B∨A](α[ наложив аналогичные ограничения на опе- ратор В. Исходя из этого, можно сделать следующий вывод. В том случае, когда на условие α влияет один из двух операторов A или B, указанное ограничение можно снять за счет выбора порядка следования этих операторов. Такое разложение применимо и для более общего случая операции α3- дизъюнкция, которую запишем в виде )C](α[)B(]α[)A(]α[=)C∨B∨A](α[ rrr , с аналогичными ограничениями на вхо- дящие в выражение операторы и на поря- док их следования. В том случае, когда в качестве ло- гического условия фигурирует фиксирую- щее условие f, никаких ограничений на разложение α3-дизъюнкции и α − дизъ- юнкции на последовательные фильтры не накладывается, так как фиксирующие ус- ловия по определению не зависят от вы- полнения операторов и, таким образом: ),(][)(][)B∨]([ BfAfAf ¬= )]([)(][)(][)C∨B∨]([ CfBfAfAf rrr = . Рассмотрим возможности пре- образования следующих вложенных α-дизъюнкций и α − итераций: 1. =∨∨ ))](]([[ СBAαα разложив α-дизъюнкции по последова- тельным фильтрам, получаем ( ) ( ) ( ) =¬¬= CBA ][)]]([[)]]([[ ααααα , преобразовав выражение в соответствии с соотношениями (5, 6) получаем ( ) ( ) =¬= CEA ][][ αα , исключив, тождественный оператор в со- ответствии с (1) и свернув фильтры в α-дизъюнкцию получаем такой эквива- лентный результат: ).С∨A](α[= Теоретичні та методологічні основи програмування 11 2. )]([))](]([[ ABAAB ∨∧=∨∨ ββ αα . Эквивалентность такого преобра- зования становится очевидной, если обра- тить внимание на тот факт, что оператор В выполняется только при истинности ус- ловий α и β, а оператор А во всех ос- тальных случаях. 3. )]([))]([]([ ВАВАА ∨∨=∨∨ ββ αα . В данном случае доказательство аналогично предыдущему случаю, так как оператор В выполняется только при лож- ных значениях условий α и β, а оператор А во всех остальных случаях. 4. }{ }{ }{ )]([ АА ββα α= . Доказательством эквивалентности является утверждение о том, что условие α проверяется однократно, т. е. по завер- шению выполнения оператора А оба ло- гические условия α и β принимают лож- ное значение. Докажем справедливость этого утверждения от противного. Пола- гая, что по завершению вложенного цикла условие α истинно и применяя последова- тельно соотношения (2, 4, 3) получаем }{ }{ }{ }{ }{ }{ }{ ,0 NЕААА ===¬= ααβαβα β т. е. конструкция вырождается в неопре- деленный (ошибочный) оператор и, таким образом, эквивалентнось преобразования доказана. 5. }{ }{( ) }{ }{BАBA ββββ αα )]([∨][ = . В данном случае доказательством служит тождественное соотношение (2), в соответствии с которым выполнение в цикле оператора А (при истинном α) при- ведет к невыполнению в цикле оператора B, а при ложном α будет пропущено вы- полнение в цикле оператора A. Данный раздел иллюстрирует воз- можности преобразования РС за счет ис- пользования соотношений, характери- зующих их общие свойства, без привле- чения соотношений, отражающих специ- фику предметной области. Открытой и весьма актуальной остается проблема ав- томатизации формальной трансформации регулярных схем. 4. Примеры использования расширенной алгебры алгоритмов Продемонстрируем некоторые возможности построенной алгебраиче- ской системы на простейших примерах, которые выбраны таким образом, чтобы иллюстрировать эти возможности, не за- громождая процесс восприятия сложно- стями алгоритмов как таковых. Пример 1. Первой рассмотрим задачу обра- ботки массивов, которая иллюстрирует использование операции α3 – дизъюнкция. Пусть ∗= nxxxX ...21 ∗= nyyyY ...21 исходное состояние двух произвольных числовых последовательностей (массивов чисел), где  – сдвоенный указатель, пе- ремещающийся по массиву, причем ука- затель может перемещаться отдельно; * – маркер, отмечающий конец массива. Необходимо сравнить одноименные элементы массивов X и Y и больший эле- мент скопировать на место меньшего. Совпадающие элементы из массива уда- ляются. Для простоты будем полагать, что все указатели синхронно перемещаются по обоим массивам. Введем следующие элементарные операторы: ⇒ C – синхронно перемещает указа- тели на один шаг по массивам X и Y; КОП(x,y) – копирует элемент, находя- щийся справа от указателей из массива Х в массив Y; КОП(y,x) – копирует элемент, находящийся справа от указателей из мас- сива Y в массив Х; СДВИГ(X,Y) – пере- мещает часть массивов X и Y (включая маркер ), находящуюся справа от указа- теля на одну позицию влево, удаляя, та- ким образом, совпадающие элементы; и предикаты: СРАВН(x,y) – значения которого для элементов, расположенных слева от указателей, трактуются следующим обра- зом: 1 – элемент массива Х больше эле- мента массива Y, 0 – элемент массива Х Теоретичні та методологічні основи програмування 12 меньше элемента массива Y, µ – сравни- ваемые элементы равны; d() – истинное, когда указатель достигает маркеров конца массивов. Алгоритм обработки массивов ОБР(X,Y) запишем таким образом: [ ] ( )( ∨ ⇒    = yxКОПyxСРАВНCY)ОБР(X, d ,),(() ( ) ( ) ) }YXСДВИГxyКОП ,, ∨∨ . Для детализации построенной ре- гулярной схемы разработаем алгоритм реализации оператора СДВИГ(X,Y). Для чего введем следующие элементарные операторы: C r – синхронно перемещает указа- тели \| на один шаг по массивам X и Y; ⇐ С – возвращает указатели \| к указа- телям ; ТРАНСП(x,y) – синхронно переме- щает в массивах X и Y элементы, распо- ложенные справа от указателей  (включая маркер ), на место элементов располо- женных слева от указателей \|; и предикат: d(∗\|) − принимающий истинное зна- чение, когда указатель \| выходит за грани- цу (за маркер) массива. Запишем регулярную схему в виде ( ) ⇐      = СyxТРАНСПCY)СДВИГ(X, d ,* → \|)(* . Подставив, полученный оператор в исходное выражение, получаем результи- рующую регулярную схему: ( ) ( )             ⇐→ \|)( ,∨,∨ СyxТРАНСПCxyКОП d . Полученный алгоритм представляет собой циклическую процедуру обработки массивов X и Y, где после сравнения од- ноименных элементов больший из них ко- пируется на место меньшего. В случае ра- венства элементов необработанные части массивов сдвигаются на одну позицию влево удаляя, таким образом, совпадаю- щие элементы в обоих массивах. Цикл прекращает свою работу, когда указатель  достигает конца массива. Этот пример демонстрирует пре- имущества трехзначной логики при раз- работке данного алгоритма, так как легко представить, что использование двузнач- ной логики приведет к вложенности кон- струкций и, таким образом, затруднит по- нимание алгоритма. Пример 2. Возможность разработки средства- ми САА-Р алгоритмов использующих декларативные знания (некоторые аспек- ты этой задачи рассмотрены в [10]) про- демонстрируем на примере системы кон- троля за состоянием некоего гипотетиче- ского парового котла. В качестве базовой выберем наи- более простую и распространенную про- дукционную модель представления зна- ний [11], в которых знания (используется простейший вариант) представляются с помощью правил вида ЕСЛИ условие ТО реакция. При этом в качестве фактов (посы- лок) будем использовать фиксирующие условия, а в качестве правил последова- тельные фильтры. Допустим, что система вводит дан- ные с датчиков давления и температуры, анализирует введенную с них информацию и реализует алгоритм управления в соот- ветствии со следующими правилами: правило № 1 ЕСЛИ «аварийная ситуация » И «давление превысило норму» ТО «открыть аварийный клапан» правило № 2 ЕСЛИ «нормальная ситуа- ция» И «температура нормальная» ТО «закрыть клапан» правило № 3 ЕСЛИ «предаварийная си- туация» И «температура растет» ТО «аварийная ситуация» правило № 4 ЕСЛИ «температура превы- сило норму» И «давление растет» ТО «предаварийная си- туация» [ ] ( )( ∨,),( ⇒ )( yxКОПyxСРАВНCY)ОБР(X, d    = Теоретичні та методологічні основи програмування 13 правило № 5 ЕСЛИ «давление нормаль- ное» ИЛИ «давление ниже нормы» ТО «нормальная ситуа- ция» Для построения регулярной схемы будем использовать следующие элемен- тарные операторы: ВВОД(DТ)-ввод информации с дат- чиков давления и температуры; предикаты, принимающие значения в следующей трактовке и сохраняемые таким фиксирующими условиями: сост_d = 1 – давление превысило норму, 0 – давление ниже нормы, µ – дав- ление нормальное, фиксирующее условие – sd; изм_d = 1 – давление растет, 0 – давление не изменяется, µ – давление па- дает, фиксирующее условие – id; сост_t = 1 – температура превысила норму, 0 – температура ниже нормы, µ – температура нормальная, фиксирующее условие – st; изм_t = 1 – температура растет, 0 – температура не изменяется, µ – температу- ра снижается, фиксирующее условие –it; Регулярную схему алгоритма рабо- ты системы запишем в таком виде: ПРАВИЛА itbitbitbtизм stbstbstbtcocт idbidbidbdизм sdbsdbsdbdсост DTВВОДКОТЕЛ * )∨](_[ )](_[ )](_[ )∨∨](_[ )( 01 01 01 01 1 µ µ µ µ ∨ ∨∨ ∨∨ = Смысл регулярной схемы состоит в следующем. Контроль работы котла осу- ществляется непрерывно, поэтому в дан- ном случае использован бесконечный цикл (цикл по тождественно истинному усло- вию, о необходимости и возможности ис- пользования которого упоминалось вы- ше). В цикле прежде, чем использовать правила, собираются факты о состоянии объекта управления. Для этого после ввода данных (оператор ВВОД(DТ)), использу- ются операции 3α – дизъюнкция, с помо- щью которых фиксируется состояние объ- екта управления. Далее обрабатываются правила. Детализуем оператор ПРАВИЛА, для чего введем следующие операторы: ОКЛ – открыть клапан; ЗКЛ – закрыть клапан; и промежуточные фиксирующие условия: авс – аварийная ситуация; предавс – предаварийная ситуация; норм – нормальная ситуация. Регулярная схема выглядит таким образом: )}.](∨[)](∨[* )](∧[ )](∧[ )](∧{[ 11 1 нормbdsdsпредавсbidst авсbitпредавс ЗКЛtsнорм ОКЛsdавсПРАВИЛА k rrr r = Работа алгоритма заключается в следующем. После установки исходных состояний фиксирующих логических ус- ловий в цикле выполняется последова- тельность α-фильтров. Каждый из фильт- ров ведет к выполнению (невыполнению) некоторого действия (оператора) или к ус- тановке (не установке) истинного значения промежуточного фиксирующего условия. Условием завершения цикла (условие k) является факт невыполнения ни одного из правил, включенных в цикл. Воспользовавшись операцией лево- го умножения предиката на фиксирующее условие, заменив ею операцию 3α – дизъ- юнкция, и подставив оператор ПРАВИЛА, получаем окончательный вид РС: .}]∨[]∨[* ]∧[ )](∧[)](∧{[* ]_[]_[* ]_[]_[* *)( 1 нормdsdsпредавсidst авсitпредавс ЗКЛtiнормОКЛsdавс k ittизмsttсост iddизмsddсост DTВВОДКОТЕЛ rrr r = Теоретичні та методологічні основи програмування 14 Таким образом, построен алгоритм системы слежения, в котором органично сочетается использование декларативных и процедурных знаний. Такое сочетание обладает, по крайней мере, одним очевид- ным преимуществом. Использование зна- ний, представленных в форме правил, мо- жет существенным образом повысить по- нятность и читабельность программной документации. Это облегчит взаимодейст- вие специалистов (заказчиков, технологов) из разных предметных областей с разра- ботчиками программного обеспечения. Кроме того, можно рассчитывать, на то, что правила могут использоваться в каче- стве спецификации алгоритмов (или их основных фрагментов), что позволит ре- шать (по крайней мере, частично) пробле- му верификации алгоритмов и программ. Заключение Основным результатом данной ра- боты является расширенная система алго- ритмических алгебр (САА-Р) – <U, W, Ω>, построенная на основе детализации абст- рактной модели функционирования ЭВМ, в которой информационное множество M операционного автомата О разбито на два подмножества статическое MS и динами- ческое MD. Принципиально важными особен- ностями построенной САА-Р является сле- дующее. Введена операция α3-дизъюнкция 2 Ω∈ , позволяющая полностью исполь- зовать возможности трехзначной логики, обеспечивая компактность записи и эффек- тивность некоторых классов алгоритмов. Выделено подмножество операто- ров U∈U′′ , меняющих динамическую со- ставляющую MD информационного мно- жества M и оставляющих статическую со- ставляющую MS неизменной. С помощью операторов из подмножества U∈U′′ реали- зуется операция левого умножения усло- вия на оператор 1Ω∈′pB , ( PpUB ∈′′∈′ , ), т.е. прогнозирование вычислительного процесса. Множество логических W условий разбито на множество предикатов P и множество фиксирующих логических ус- ловий F, причем последние сохраняют свои значения не зависимо от действия любого из операторов UA∈ . Введенная операция левого умножение фиксирующе- го условия на предикат 1Ω∈pf ( FfPp ∈∈ , ) сохраняет состояние логиче- ского условия, характеризующее текущее состояние вычислительного процесса (со- храняет предысторию), которое может быть использовано на последующих эта- пах вычислительного процесса. А опера- ция умножения фиксирующего условия на оператор 1 x Ω∈fb ( FfUb x ∈′∈ , ), позволяет задать требуемое значение фиксирующе- му условию. Таким образом, создано до- полнительное средство управления вычис- лительным процессом, расширяющее, в частности, возможности построения про- изводных алгоритмических конструкций. Кроме того, фиксирующее условие может трактоваться как элемент декларативных знаний (факт) и в этом качестве позволяет расширить область применения САА-Р на класс задач, в которых удобно использо- вать декларативные знания совместно с процедурными. Построенная расширенная алгебра алгоритмов обеспечивает вышеуказанные возможности, сохраняя при этом способ- ность формального преобразования алго- ритмов с целью их оптимизации, и откры- вает достаточно широкие перспективы для дальнейшего развития. Ближайшей перспективой развития САА-Р является следующее. Апробация формального аппарата на примере реше- ния конкретных практических задач. Раз- работка “библиотеки” производных опера- ций и эквивалентных преобразований ал- горитмических конструкций. Использова- ние более развитых моделей представ- ления знаний и алгоритмов логического вывода. Учитывая, что проектирование управляющих структур неразрывно связа- но с проектированием структур данных [12], в качестве следующего основного Теоретичні та методологічні основи програмування 15 этапа развития САА-Р назовем включение в рассмотрение данных. Поскольку аппарат САА-Р позволя- ет сочетать использование декларативных и процедурных знаний, то перспективным представляется направление развития, при котором знания, представленные в виде правил, используются не только для реше- ния внешних по отношению к алгоритму задач, а и как средство управления собст- венно вычислительным процессом. 1. Глушков В.М. Теория автоматов и фор- мальные преобразования микропрограмм. // Кибернетика. – 1965. – № 5. – С. 1–10. 2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – Киев: Наук. думка, 1978. – 319 с. 3. Ющенко Е.Л., Цейтлин Г.Е.,Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий. – М.: Финансы и статистика, 1989. – 208 с. 4. Цейтлин Г.Е. Введение в алгоритмику. – Киев: “Сфера”, 1998. – 310 с. 5. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы. – М.: Мир, 1977. – Т.2. – 822 с. 6. Брусенцов Н.П., Владимирова Ю.С. Ком- пьютеризация булевой алгебры // Докл. Академии наук, 2004. – Т. 395.– № 1. 7. Брусенцов Н.П. Кибернетика – ожидания и результаты. Политехнические чтения. Вып. 2. – М.: Знание, 2002. – С. 104 – 105. 8. Поспелов Д.А. Логические методы анализа и синтеза схем. Изд. 3–е, перераб. и доп. – М.: Энергия, 1974. – 368 с. 9. Акуловський В.Г., Костенко В.В. Перетво- рення елементарних алгоритмічних конс- трукцій за допомогою засобів алгебри ал- горитмів // Вісн. АМС України. − 2006. – № 3. – С. 93 – 99. 10. Акуловський В.Г., Костенко В.В. Розробка алгоритмів на основі продукційної моделі подання знань // Вісн. АМС України. − 2006. – № 2. – С. 41– 46. 11. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. – СпБ: Питер. – 2001. – 384 с. 12. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985. – 406 с. Получено 18.04.2007 Об авторе: Акуловский Валерий Григорьевич, кандидат технических наук, доцент кафед- ры информационных систем и технологий. e-mail: akulovski@rambler.ru Место работы автора: Академия таможенной службы Украины. 49000, Днепропетровск, ул. Дзержинского 2/4. Тел/факс. канцелярии (общий отдел) – (0562) 45 5596; дом.тел. (0562) 67 5004; моб. тел. 80509410566. e-mail: academy@amsu.dnp.ukrpack.net
id	nasplib_isofts_kiev_ua-123456789-296
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Russian
last_indexed	2025-12-07T18:07:44Z
publishDate	2007
publisher	Інститут програмних систем, журнал "Проблеми програмування"
record_format	dspace
spelling	Акуловский, В.Г. 2008-02-22T19:19:07Z 2008-02-22T19:19:07Z 2007 Расширенная алгебра алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2007. — N 3. — С. 3-15. — Библиогр.: 12 назв. — рус. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/296 Предложен формальный аппарат (расширенная система алгоритмических алгебр), ориентированный на детальную разработку алгоритмов с учетом особенностей языка, на котором будет реализован алгоритм, с использованием трехзначной логики и декларативных знаний совместно с процедурными. Показаны возможности формального преобразования алгоритмов и построения производных алгоритмических конструкций. Приведены примеры использования формального аппарата. ru Інститут програмних систем, журнал "Проблеми програмування" №3 С. 3-15 Теоретичні та методологічні основи програмування Расширенная алгебра алгоритмов 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/296
work_keys_str_mv	AT akulovskiivg rasširennaâalgebraalgoritmov

Расширенная алгебра алгоритмов

Institution

Similar Items