Алгоритмика программ
На протяжении многих лет Цейтлин Г.Е. занимается разработкой теоретических аспектов алгоритмов, представляемых блок–схемами, как способа детализации и
реализации алгоритмов. Аппарат блок–схем пополнен математическими формулами, свойственными математике, которые используются при аналитических преобразованиях и обеспечивают улучшение качества алгоритмов [40–42].
Построение и исследование алгебры алгоритмов впервые осуществил В.М. Глушков в рамках проектирования логических структур ЭВМ. В результате была построена теория систем алгоритмических алгебр (САА), которая затем была положена в основу обобщенной теории структурированных схем алгоритмов и программ, называемой теперь алгоритмикой [41].
Объектами алгоритмики являются модели алгоритмов и программ, представляемые в виде схем. Метод алгоритмики базируется на компьютерной алгебре и логике и используется для проектирования алгоритмов прикладных задач. Построенные алгоритмы описываются с помощью ЯП и реализуются соответствующими системами программирования в машинное представление.
В рамках алгоритмики разработаны специальные инструментальные средства реализации алгоритмов, которые базируются на современных объектно–ориентированных средствах и методе моделирования UML. Тем самым обеспечивается полный цикл работ по практическому применению разработанной теории алгоритмики при реализации прикладных задач, начиная с постановки задачи, формирования требований и разработки алгоритмов до получения программ решения этих задач.
Алгебра алгоритмов. Под алгеброй алгоритмов АА= {A, W} понимается основа А и сигнатура W операций над элементами основы алгебры. С помощью операции сигнатуры может быть получен произвольный элемент q Î AА, который называется системой образующих алгебры. Если из этой системы не может быть исключен ни один элемент без нарушения ее свойств, то такая система образующих называется базисом алгебры.
Операции алгебры удовлетворяют следующим аксиоматическим законам: ассоциативности, коммутативности, идемпотентности, закону исключения третьего, противоречия и др.
Алгебра, которой удовлетворяют перечисленные операции, называется булевой.
В алгебре алгоритмов используется алгебра множеств, элементами которой являются множества и операции над множествами (объединение, пересечение, дополнение, универсум и др.).
Основным объектами алгебры алгоритимки являются схемы алгоритмов и их суперпозиции, т.е. подстановки одних схем в другие. С подстановкой связана развертка, которая соответствует нисходящему процессу проектирования алгоритмов, и свертка, т.е. переход к более высокому уровню спецификации алгоритма. Схемы алгоритмов соответствуют конструкциям структурного программирования:
Последовательное выполнение операторов А и В записывается в виде композиции А*В; альтернативное выполнение операторов А и В (fu (А, В)) означает, если u истинно, то выполняется А иначе В; цикл (u (А, В)) выполняется, пока не станет истинным условие u (u – логическая переменная). С помощью этих элементарных конструкций строиться более сложная схема P алгоритма:
P ::= ((u1 ) А1}},
А1 ::= { (u2 ) А2 * D}
А2 ::= А3 * C,
А3 ::= { (u ) А, B}, u::= u2 Ù u1.
Проведя суперпозицию путем свертки приведенной схемы алгоритма P, получается формула:
P ::= ( u1 ) (u2 ) ( (u2 Ù u1) А, В ) * С * D).
Важным результатом является сопоставительный анализ аппарата алгебры алгоритмики и следующих известных алгебр.
Алгебра Дейкстры АД = {АСС, L(2), СИГН} – двухосновная алгебра, основными элементами которой являются множество АСС операторов, представленных структурными блок–схемами, множество L(2) булевых функций в сигнатуре СИГН, в которую входят операции дизъюнкции, конъюнкции и отрицания, принимающие значения из L(2). С помощью специально разработанных механизмов преобразования АД в алгебру алгоритмики установлена связь между альтернативой и циклом, т.е. ((u ) А} = ((u ) Е, А * ((u ) А}}, произвольные операторы представлены суперпозицией основных операций и констант.
Операция фильтрации Ф (u ) = ((u ) Е, N} в АД представлена суперпозицией тождественного Е и неопределенного N операторов и альтернативы алгебры алгоритмики, где N – фильтр разрешения выполнения операций вычислений. Оператор цикла while do также представлен суперпозицией операций композиции и цикла в алгебре алгоритмики.
Алгебра схем Янова АЯ включает в себя операции построения неструктурных логических схем программ. Схема Янова состоит из предикатных символов множества P{p1, p2,…), операторных символов множества A{a1, a2,…} и графа переходов. Оператором в данной алгебре есть пара A{p}, состоящая из символов множества А и множества предикатных символов. Граф перехода представляет собой ориентированный граф, в вершинах которого располагаются преобразователи, распознаватели и один оператор останова. Дуги графа задаются стрелками и помечаются они знаками + и –.
Преобразователь имеет один преемник, а распознаватель – два. Каждый распознаватель включает в себя условие выполнения схемы, а преобразователь представляет операторы, включающие логические переменные, принадлежащие множеству {p1, p2,…).
Каждая созданная схема АЯ отличается большой сложностью, требует серьезного преобразования при переходе к представлению программы в виде соответствующей последовательности действий, условий перехода и безусловного перехода. В работе [86] разработана теория интерпретации схем Янова и доказательство эквивалентности двух операторных схем исходя из особенностей алгебры алгоритмики.
Для представления схемы Янова аппаратом алгебры алгоритмики сигнатура операций АЯ вводятся композиции А* В и операции условного перехода, который в зависимости от условия u выполняет переход к следующим операторам или к оператору помеченному меткой (типа goto). Условный переход трактуется как бинарная операция P (u, F), которая зависит от условия u и разметок схемы F. Кроме того, производится замена альтернативы и цикла типа while do.
В результате выполнения бинарных операций получается новая схема F’, в которой установлена P (u) вместо метки и булевы операции конъюнкции и отрицания. Эквивалентность выполненных операций преобразования обеспечивает правильность неструктурного представления.
Система алгебр Глушкова АГ = {ОП, УС, СИГН}, где ОП и УС – множество операторов суперпозиции, входящих в сигнатуру СИГН, и логических условий, определенных на информационном множестве ИМ, СИГН = {СИГНад È Прогн.}, где
СИГНад – сигнатура операций Дейкстры, а Прогн. – операция прогнозирования. Сигнатура САА включает в себя операции алгебры АД, операции обобщенной трехзначной булевой операции и операцию прогнозирования (левое умножение условия на оператор u = (А* u’), порождающая предикат u = УС такой, что u(m) = u’( m’), m’ = А (m), А ÎОП. ИМ – множество обрабатываемых данных и определения операций из множеств ОП и УС. Сущность операция прогнозирования состоит в проверке условия u в состоянии m оператора А и определения условия u’, вычисленного в состоянии m’ после выполнения оператора А.Данная алгебра ориентирована на аналитическую форму представления алгоритмов и оптимизацию алгоритмов по выбранным критериям.
Алгебра булевых функций и связанные с ней теоремы о функциональной полноте и проблемы минимизации булевых функций также сведены до алгебры алгоритмики. Этот специальный процесс отличается громоздкостью, и рассматриваться не будет, можно только отослать к главному источнику [86].
Алгебра алгоритмики и прикладные подалгебры. Алгебра алгоритимки пополнена двухуровневой алгебраической системой и механизмами абстрактного описания данных (классами алгоритмов). Под многоосновной алгоритмической системой (МАС) понимается система S ={{Di÷ iÎI }; СИГН0 , СИГНn }, где Di –основы или сорта, СИГН0 , СИГНn – совокупности операций и предикатов, определенных на Di .Если они пусты, то определяются многоосновные модели – алгебры. Если сорта интерпретируются как множество обрабатываемых данных, то МАС представляет собой концепцию АТД, в виде подалгебры, широко используемую в объектно–ориентированном программировании.Тем самым устанавливается связь с современными тенденциями развития современного программирования.
Практическим результатом исследований алгебры алгоритмики является построение оригинальных инструментальных систем проектирования алгоритмов и программ на основе современных средств поддержки ООП.
Читателям данной темы предоставляется возможность познакомиться более подробно с приведенными источниками.
