УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Преобразование итеративных алгоритмов в автоматные

А.А. Шалыто, Н.И. Туккель

Преобразование итеративных алгоритмов в автоматные

Аннотация

Для систем логического управления и событийных систем выделение состояний является естественным, так как они в значительной мере определяются физическими состояниями объектов управления [1].

Для вычислительных алгоритмов выделение состояний не столь естественно, однако и для этого класса задач автоматный подход может быть применен [2].

Автоматный подход позволяет унифицировать процесс построения структурированных программ с визуализацией их состояний, что имеет важное значение особенно для целей обучения [3]. Это не удается обеспечить при традиционном процедурном подходе, так как в нем в качестве базовых используются понятия "условие" и "действие", а не "состояние", и поэтому процедура визуализации алгоритма является неформальной.

Программы, построенные на основе явного выделения состояний, назовем автоматными.

В работе показано, что в отличие от теоремы структурирования программ, изложенной в работе [4], схема произвольного итеративного алгоритма (программы), может быть реализована одним оператором do-while, телом которого является один оператор switch. При этом оператор switch изоморфно реализует граф переходов конечного автомата, формально построенного по исходной схеме. Предложен метод преобразования итеративных алгоритмов в автоматные. Показано, что результат, получаемый при использовании этого метода проще, чем при применении метода Ашкрофта-Манны [5].

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

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

Преимущество автоматного подхода по сравнению с традиционным достигается за счет добавления к понятиям "входное и выходное воздействия" понятия "состояние", а по сравнению с методом Ашкрофта-Манны - за счет сокращения числа состояний.

Работа выполнена в Федеральном государственном унитарном предприятии "НПО "Аврора"" и на кафедре "Компьютерные технологии" Санкт-Петербургского государственного института точной механики и оптики (технического университета) при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 "Разработка технологии автоматного программирования".

Список литературы

1. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. СПб.: Наука, 2000.
2. Кузнецов Б.П. Психология автоматного программирования //BYTE/ Россия. 2000. № 11.
3. Казаков М.А., Столяр С.Е. Визуализаторы алгоритмов как элемент технологии преподавания дискретной математики и программирования //Телематика 2000. Тез. докл. Международной научно-метод. конф. СПб.: СПбГИТМО (ТУ), 2000.
4. Йодан Э. Структурное проектирование и конструирование программ. М.: Мир, 1979.
5. Aschcroft E., Manna Z. The translation of "goto" programm into "while" programm //Proceeding of 1971 IFIP Congress.