Применение теории автоматов

Содержание

Ключевае слова:
Автомат
Программирование
Визуализатор
Нейронные сети
Микроконтроллеры
Документооборот

Программирование

Возникает вопрос, почему же конечно-автоматная модель теории автоматов особенно актуальна сейчас, когда существует огромное количество, как языков программирования, так и сред для разработки ПО? Имеют место две проблемы:

Примеры RAD: Borland Delphi и C++ , обеспечивающие ускоренную разработку приложений за счет использования объектно-ориентированного и визуального программирования. Они позволяют не только программировать в привычном смысле слова, но и фактически рисовать программы (как интерфейс, так и реализацию), используя визуальные компоненты VCL.

Любой визуальный объект VCL характеризуется рядом свойств, методов и событий. Казалось бы, простой манипуляцией перечисленными атрибутами возможно заставлять разрабатываемую программу делать то, что требует от нее программист-разработчик. Но это далеко не так.

Давно стало ясно, что VCL имеет тенденцию скрывать точную реализацию определенных объектов, тем самым не давая посторонним менять умалчиваемое поведение кода. Как показывает практика, поведение кода программы, созданной с помощью средств RAD, не всегда предсказуемо даже для очень опытного программиста, не говоря уже о начинающем. Программа, несмотря на «очевидность» авторского кода, всегда стремится пойти своим путем, попадая в такие замысловатые обработчики событий, о существовании которых можно даже и не догадываться.

В современном мире объемы и сложность разрабатываемых приложений возрастают с каждым днем, поэтому такой подход резко увеличивает время тестирования и отладки ПО.

Управлять поведением кода дает возможность механизм теории автоматов еще сорокалетней давности.

Стили программирования различаются по базовым понятиям, в качестве которых используются такие понятия как «событие», «подпрограмма», «функция», «класс» («объект») и т. д. Стиль программирования, основанный на явном выделении состояний и применении автоматов для описания поведения программ, назван «автоматное программирование», а соответствующий стиль проектирования программ — «автоматное проектирование». Автоматное программирование можно рассматривать не только как самостоятельный стиль программирования, но и как дополнение к другим стилям, например, к объектно-ориентированному, т.к. речь идет не только и не столько об использовании конечных автоматов в программировании, сколько о методе создания программ в целом, поведение которых описывается автоматами. Т.е. как отдельный компонент, так и программа в целом может быть реализована как автомат.

В автоматном программировании существует два направления: SWITH-технология и КА (конечно-автоматная) технология. Switch-технология — технология разработки систем логического управления на базе конечных автоматов, охватывающая процесс проектирования, реализации, отладки, верификации (проверки), документирования и сопровождения.

Кодирование/программирование автоматов в рамках КА-технологии основано на следующих принципах:

Рассмотрим эти технологии подробнее:

1) SWITH-технология. Основные положения: предлагается сделать понятие «состояние» первичным, а алгоритмы представлять в виде графов переходов (диаграмм состояний), т.е. представлять программу как систему взаимодействующих конечных автоматов, описываемых графами переходов. Состояния кодируются для того, чтобы их различать.
Графы в наглядной для человека форме отражают переходы между состояниями, а также «привязку» выходных воздействий и других автоматов к состояниям и/или переходам.

Внутри программы автоматы могут взаимодействовать:

Ни число автоматов, вложенных в состояние, ни глубина вложенности не ограничены. Основной критерий оптимальности реализации управляющих автоматов – возможность преобразования графа переходов в программный код. <><><>Известно большое число инструментальных средств для генерации программ, реализующих графы переходов:

Практика показала, что для многих классов программ только 20–30% программного кода строится вручную.

На основе SWITCH-технологии уже разработаны приложения для: устройства продажи газированной воды, банкомата (см. пример 1), светофора, системы управления пассажирским лифтом, система управления автомобильной сигнализации (см. пример 2), автоматизированной системы оплаты мобильного телефона, устройства обмены валюты, устройства для продажи проездных билетов и т.д.

2) КА-технология позволяет реализовать идею параллелизма. Технологии разработки программ “сверху вниз”, “снизу вверх”, структурный подход таких возможностей или не имеют, или они ограничены. Даже в технологии объектно-ориентированного программирования (ООП) вопросы параллельной работы объектов вынесены за ее рамки. Использование других технологий, базирующихся на известных параллельных моделях, сопряжено с трудностями, связанными если не с ограничениями области их применения, то с проблемами последующей реализации на программном и/или аппаратном уровнях.

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

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

3) Основное отличие рассматриваемых технологий заключается в реализации логики автоматных программ. В SWITCH-технологии она реализуется переводом автоматного описания в программный код языка программирования, в КА-технологии реализуется прямое исполнение автоматов путем интерпретации его исходного табличного представления. Это более короткий и наглядный путь реализации автоматов, хотя и более медленный, если рассматривать уровень отдельного компонентного автомата сети автоматов.

Вывод: Автоматное программирование используется в настоящее время при проектировании программного обеспечения систем автоматизации ответственных объектов управления (автомат управления криогенно-вакуумной установкой, дизель-генератором). Конечный автомат работает по принципу «шаг в сторону – недопустимо». Реализовать непредусмотренные действия конечный автомат не даст ни пользователю (исходный вариант кода), ни самой программе (модифицированный вариант кода).

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


См. также
Предыдущий раздел - Актуальность теории автоматов
Следующий раздел - Реализация визуализаторов алгоритмов дискретной математики и программирования


X