Методы и средства инженерии программного обеспечения


Алгоритмика программ - часть 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 ) А}},  произвольные операторы представлены суперпозицией основных операций и констант.


- Начало -  - Назад -  - Вперед -