Алгоритмика программ - часть 2
Алгебра, которой удовлетворяют перечисленные операции, называется булевой.
В алгебре алгоритмов используется алгебра множеств, элементами которой являются множества и операции над множествами (объединение, пересечение, дополнение, универсум и др.).
Основным объектами алгебры алгоритимки являются схемы алгоритмов и их суперпозиции, т.е. подстановки одних схем в другие. С подстановкой связана развертка, которая соответствует нисходящему процессу проектирования алгоритмов, и свертка, т.е. переход к более высокому уровню спецификации алгоритма. Схемы алгоритмов соответствуют конструкциям структурного программирования:
Последовательное выполнение операторов А и В записывается в виде композиции А*В; альтернативное выполнение операторов А и В (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 ) А}}, произвольные операторы представлены суперпозицией основных операций и констант.