Контрольная алгоритмизация и программирование 9 класс

Automata-Based Programming-это технология программирования (Nepeyvoda 2005) harv error: no target: CITEREFNepeyvoda2005 (help). Его определяющей характеристикой является использование конечных автоматов для описания поведения программ. Графы переходов конечных автоматов используются на всех этапах разработки программного обеспечения (спецификация. Реализация. Отладка и документирование). Технология программирования на основе автоматов была введена Анатолием Шалыто в 1991 году (Shalyto 1991) harv error: no target: CITEREFShalyto1991 (help). Switch-technology (Shalyto 1998) harv error: no target: CITEREFShalyto1998 (

help) был разработан для поддержки программирования на основе автоматов. Программирование на основе автоматов считается скорее методологией разработки программ общего назначения. Чем просто еще одной реализацией конечного автомата.

Автоматное программирование

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

При этом на основе анализа предметной области выделяются источники входных событий. Система управления (система взаимодействующих конечных автоматов) и объекты управления. Реализующие выходные действия.

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

Основные характеристики

В последние годы большое внимание уделяется развитию технологий программирования для встраиваемых систем и систем реального времени. Эти системы предъявляют особые требования к качеству программного обеспечения. Одним из наиболее известных подходов для этой области задач является синхронное программирование (Benveniste 2003) harv error: no target: CITEREFBenveniste2003 (help) (Shopyrin 2004) harv error: no target: CITEREFShopyrin2004 (help).

Одновременно с развитием синхронного программирования в Европев России создавался подход к разработке программного обеспечения для критически важных систем . Называемый автоматным программированием или государственным программированием (Shalyto 1998) harv error: no target: CITEREFShalyto1998 (help).

Термин В отличие от него. Предлагаемый подход основан на термине state (State-Driven Architecture). После введения термина входное действие, которое может обозначать входную переменную или событие, может быть введен термин автомат без выходов. После добавления термина выходное действиеможно использовать термин “автомат”. Это конечный детерминированный автомат.

Именно поэтому тот вид программирования. Который основан на этом термине. Был назван “автоматным программированием”. Таким образом. Процесс создания программного обеспечения можно было бы назвать “automata software design” (Shalyto 2000) harv error: no target: CITEREFShalyto2000 (help).

Особенностью этого подхода является то. Что автоматы. Используемые для разработки. Определяются с помощью графов переходов. Для того чтобы различать узлы этих графов. Был введен термин кодирование состояний. При многозначном кодировании состояний одна переменная может использоваться для различения состояний автомата. Число состояний равно числу значений. Которые эта переменная может принимать. Это позволило ввести термин наблюдаемость программы (то есть можно проверить значение переменной состояния).

Использование понятия “состояние” в отличие от понятий “события” и “переменные” позволяет более четко понять и конкретизировать задачу и ее части (подзадачи).

Необходимо отметить. Что использование автоматного программирования подразумевает отладку путем составления протоколов (протоколирования) в терминах автоматов.

Для этого подхода существует формальный и изоморфный метод преобразования графа переходов в исходный код программного обеспечения. Поэтому при использовании высокоуровневых языков программированияпроще всего использовать конструкцию . Аналогичную конструкции switch языка программирования Си. Именно поэтому первая реализация автоматного программирования получила название “Switch-технология”. Дополнительную информацию о программировании на основе автоматов можно найти в статье “Switch-технология”.

В настоящее время автоматное программирование разработано несколькими способами. Для различных типов решаемых задач и для различных типов вычислительных устройств.

Российское регистрационное свидетельство было выдано на ядро программирования на основе автоматов и на плагин программирования на основе автоматов для Eclipse IDE.

Логическое управление

В 1996 году Российский фонд фундаментальных исследований[1] в рамках издательского проекта №96-01-14066 поддержал публикацию книги (Shalyto 1998) harv error: no target: CITEREFShalyto1998 (help), в которой предлагаемая технология была описана применительно к логическим системам управления.

В таких системах нет событий. Но входные и выходные действия являются двоичными переменными и операционная система работает в режиме сканирования. Системы этого класса обычно реализуются на программируемых логических контроллерах, которые имеют относительно небольшой объем памяти а программирование должно осуществляться с использованием специализированных языков (например. Языка лестничных схем или функциональных блоков). Методы формальной генерации исходного кода для таких языков были разработаны для случаев. Когда спецификация разрабатываемого проекта представлена системой переходных графов взаимодействующих автоматов (Shalyto 1998) harv error: no target: CITEREFShalyto1998 (help).

Состояние-Программирование

Отныне автоматный подход был распространен на событийные (реактивные) системы (Haryl 1987) ошибка harv: нет цели: CITEREFHaryl1987 (help). В таких системах все указанные выше ограничения снимаются. Из названия этих систем видно. Что среди входных действий используются события. Выходные действия могут быть представлены произвольными функциями. В качестве среды может использоваться любая операционная система реального времени.

Автоматная реализация событийных систем была выполнена с помощью процедурного подхода к разработке программного обеспечения (Shalyto 2001a) harv error: no target: CITEREFShalyto2001a (help) (Shalyto 2001b) harv error: no target: CITEREFShalyto2001b (help), отсюда и название “state-based programming”.

При использовании этого метода выходные действия назначаются дугам, петлям или узлам переходных графов (в общем случае используются смешанные автоматы Мура-Мили (Shalyto 1998) harv error: no target: CITEREFShalyto1998 (help)). Это позволяет представить в компактной форме последовательности действий. Которые являются реакциями на соответствующие входные действия.

Одной из особенностей такого подхода к программированию для реактивных систем является то. Что централизация логики программы достигается ликвидацией логики в обработчиках событий и формированием системы взаимодействующих автоматов. Которые вызываются из этих обработчиков (Tukkel 2001) harv error: no target: CITEREFTukkel2001 (help). Автоматы в такой системе могут взаимодействовать по вложенности. По способности вызывать друг друга и с помощью обмена номерами состояний.

Еще одной важной особенностью этого подхода является то. Что автоматы в нем используются трижды: для спецификации. Для реализации (они остаются в исходном коде) и для составления протокола. Который выполняется. Как было сказано выше. В терминах автоматов. Последнее позволяет проверить правильность функционирования автоматной системы. Протоколирование выполняется автоматически на базе созданной программы и может быть использовано для отладки программ со сложным поведением.

Также такой подход позволяет эффективно документировать решения. Принимаемые в процессе проектирования. Особенно связанные с формализацией поведения программы (Tukkel 2002) harv error: no target: CITEREFTukkel2002 (help).

Все это позволило основать Фонд открытой проектной документации (Shalyto 2003) harv error: no target: CITEREFShalyto2003 (help), в контексте которого разрабатываются многие проекты по совершенствованию автоматизированного программирования ( Automata programminghomepage) harv error: no target: CITEREFAutomata_programming_homepage (help).

Государство на основе объектно-ориентированное программирование

Композитный подход. Основанный как на объектно-ориентированной. Так и на автоматной парадигмах программирования (Shalyto 2004) harv error: no target: CITEREFShalyto2004 (help), (Shalyto 2005) harv error: no target: CITEREFShalyto2005 (help), может быть весьма полезен для решения задач из очень большого спектра. Этот подход получил название “объектно-ориентированное программирование на основе состояний”.

Главная особенность этого подхода состоит в том, что . Как и в машинах Тьюринга, управляющие (автоматические) состояния выделяются явно. Количество этих состояний заметно меньше. Чем количество состояний всех других объектов (например. Состояний времени выполнения).

Термин “пространство состояний” был введен в программировании. Этот термин означает совокупность управляющих состояний объекта. Таким образом. Такой подход обеспечивает более понятное поведение по сравнению со случаем. Когда такое пространство не выделено явно.

Описан минимальный набор документов. Наглядно и наглядно описывающих структурную (статическую) и поведенческую (динамическую) стороны программного проекта (Tukkel 2003) harv error: no target: CITEREFTukkel2003 (help).

Из опыта адаптации предложенного подхода (Tukkel 2001) harv error: no target: CITEREFTukkel2001 (help) можно сделать вывод. Что применение автоматов делает поведение программ более ясным. Так как использование объектов делает структуру программ более ясной. Наличие качественной проектной документации значительно облегчает дальнейший рефакторинг программы (изменение ее структуры при сохранении функциональности) (Кузнецов 2003) harv error: no target: CITEREFKuznetsuv2003 (help).

Вычислительные алгоритмы

Автоматный подход может быть использован для реализации вычислительных алгоритмов. Было показано (Tukkel 2002) harv error: no target: CITEREFTukkel2002 (help), что произвольный итерационный алгоритм может быть реализован с помощью конструкции . Эквивалентной оператору циклаdo ... while, внутри которого есть один switchоператор. Реализующий автомат.

Автоматный подход очень эффективен для реализации некоторых алгоритмов дискретной математики, например. Алгоритма разбора дерева (Корнеев 2004).

Предложен новый государственный подход к созданию визуализаторов алгоритмов. Такое программное обеспечение визуализации широко используется на кафедре компьютерных технологий Санкт-Петербургского государственного университета информационных технологий. Механики и оптики для студентов. Обучающихся программированию и дискретной математике (Казаков 2005) harv error: no target: CITEREFKazakov2005 (help) (Корнеев 2005) harv error: no target: CITEREFKorneev2005 (help). Такой подход позволяет представить логику визуализатора в виде системы взаимодействующих конечных автоматов. Эта система состоит из пар автоматов. Каждая из которых содержит “прямой” и “обратный” автоматы. Что обеспечивает пошаговое выполнение алгоритмов вперед и назад соответственно.

Приборостроение

Для поддержки программирования автоматов разрабатываются различные программные средства. Одним из таких инструментов является UniMod (Gurov 2004) harv error: no target: CITEREFGurov2004 (help) (Gurov 2005) harv error: no target: CITEREFGurov2005 (help) (UniMod) harv error: no target: CITEREFUniMod (help). Этот инструмент основан на следующих концепциях: UML, Switch-технология, Eclipse IDE, язык программирования Java, открытый исходный код (http://unimod.sourceforge.net/). Все это позволяет говорить об унимоде как о реализации исполняемого UML.

Некоторые примеры использования инструмента UniMod приведены в разделе (UniMod Examples) harv error: no target: CITEREFUniMod_Examples (help).

Сборник статей по автоматному программированию

В Университете ИТМО были опубликованы сборники статей по автоматному программированию . Бюллетень (ifmo.ru 2008) harv error: no target: CITEREFifmo.ru2008 (help) содержит 28 статей по различным проблемам автоматного программирования.

Первая книга о программировании на основе автоматов

В 2009 году в Санкт-Петербурге была опубликована первая книга о программировании на основе автоматов (Polikova2009) harv error: no target: Citerefpolikova2009 (help).

См. также