НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ
Кафедра «Технологии программирования»



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Геном
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Статьи / Преобразование итеративных алгоритмов в автоматные (версия для печати)


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



С авторами можно связаться по адресу: mail@avrorasystems.com, "для Шалыто".
Статья опубликована в журнале Российской академии наук
"Программирование". - 2002. - № 5. - С. 12-26.

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

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

Отсюда можно скачать полный текст статьи в формате pdf (200 кб)

Аннотация

Для систем логического управления и событийных систем выделение состояний является естественным, так как они в значительной мере определяются физическими состояниями объектов управления [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.



© 2002—2014 По техническим вопросам сайта: vl.ulyantsev@gmail.com