РАЗДЕЛ 2
АЛГЕБРА АЛГОРИТМИЧЕСКИХ СТРУКТУР
2.1. Алгебраические методы в разработке и анализе алгоритмических структур
С развитием автоматной теории алгоритмов была доказана возможность формальных
преобразований алгоритмов. Для проведения достаточно тонких и глубоких
эквивалентных преобразований алгоритмов была предложена алгебра алгоритмов,
которая позволила производить эквивалентные преобразования. Этот алгебраический
аппарат, предназначен для решения задач, связанных с автоматизацией
проектирования ЭВМ, был предложен В.М. Глушковым в виде микропрограммных алгебр
[119]. С помощью этой системы появилась возможность производить эквивалентные
преобразования большого класса алгоритмов, которые меняют лишь форму
представления, а последовательность выполнения операторов остается неизменной.
А также производить более глубокие преобразования, меняющие форму записи
алгоритмов, последовательность выполнения операторов в них.
В общем случае системы алгоритмических алгебр (САА) являются порождающей
двухосновной алгеброй, имеющей в качестве основной алгебру A(Y). В.М. Глушков
[120] доказал, что произвольный алгоритм (в частности программа или
микропрограмма ЭВМ) может быть представлен в виде регулярной схемы алгоритма
(РСА). Для любых алгоритмов существует метод регуляризации, позволяющий перейти
к их представлению посредством РСА. Она означает по существу следующее. Каков
бы ни был исходный язык алгоритмов (ГСА, ЛСА, сети Петри и т. д.), его всегда
можно предварительно погрузить в САА с последующей организацией обработки на
основе единых, унифицированных правил. Аналогичным образом на заключительном
этапе можно организовать переход от РСА к произвольным выходным языкам.
Математический аппарат РСА получил широкое распространение для проектирования
систем различного уровня и назначения [121]. Однако, если алгоритм сложный,
иерархический, имеет множество параллельных и итерационных участков,
наглядность представления ухудшается. Это приводит к невозможности работы в
системе пользователей, неподготовленных в области алгоритмического
представления систем и программирования. В случае использования метода
представления моделей в РСА этот недостаток можно устранить путем перевода
алгоритмов в язык описания моделей, который обладает более высокой
наглядностью.
Кроме рассмотренных, построены системы алгоритмических алгебр (САА) с
замкнутыми логическими условиями, для которых разработана конечная полная
система аксиом с применением единственного вывода правила подстановки.
Произвольная операторная схема алгоритма всегда может быть описана в терминах
автоматных РСА, так как класс операторов, представимых схемами Янова, строго
включается в класс операторов, представимых регулярными схемами [122].
Применение САА для реализации структурных программ сопряжено с определенными
трудностями в связи с необходимостью априорного представления алгоритмов и
программ в структурной форме, обладающей чаще всего некоторой избыточностью.
Необходимость в модификации языковых средств САА возникает в реальной
практической ситуации, связанной с применением САА для решения конкретных задач
с минимальными затратами.
Цейтлин Г.Е. [123] модифицировал САА за счет дополнительных операций, что
позволило исследовать и параллельные схемы алгоритмов и прирастить
преобразования (для перехода к обработке операторов, а не логических условий).
Техника формальных преобразований в CAA носит достаточно сложный и громоздкий
характер. Это определяет необходимость автоматизации доказательства
соотношений (теорем) в CAA, представленных в виде аксиоматической теории.
Поэтому процесс исследования CAA должен проводиться в соответствии с
рассмотренными системами тождеств путем использования в том или ином случае
надлежащей аксиоматики, которая приведет к конечному результату с минимальными
затратами ресурсов.
Важным этапом в развитии САА является разработка модифицированных систем
алгоритмических алгебр (МСАА). Модификации CAA позволяет построить такой
математический аппарат, при использовании которого итерации имели бы
циклическую глубину qЈ1 и упрощают технику тождественных преобразований [85].
Системный анализ и исследование операций, разработка математического
обеспечения АСУ, автоматизация проектирования и обработки больших массивов
информации приводят к математическим моделям, среди которых существенное место
занимают автоматы. Автоматы используются для формального описания реальных
объектов, которые при формализации могут быть адекватно представлены в виде
дискретных схем [124]. Развитие прикладной теории автоматов и теории
программирования привело к необходимости изучения способов тождественных
преобразований алгоритмов или к нахождению их эквивалентности. С развитием
автоматной теории алгоритмов [119], в которой алгоритмы представляются в виде
абстрактного автомата, была доказана возможность формальных преобразований
алгоритмов. Для проведения достаточно тонких и глубоких эквивалентных
преобразований алгоритмов была предложена алгебра алгоритмов, которая позволила
производить преобразования так же, как и в обычной алгебре при анализе. Этот
алгебраический аппарат, предназначенный для решения задач, связанных с
автоматизацией проектирования ЭВМ и программирования, был предложен В.М.
Глушковым и представлен в виде системы микропрограммных алгебр [122]. С помощью
системы микропрограммных алгебр появилась возможность производить эквивалентные
преобразования программ и алгоритмов двух классов. Первый класс составляют
преобразования, которые меняют лиш
- Київ+380960830922