А. А. Шалыто Санкт-петербург

Скачать 0.71 Mb.

Название	А. А. Шалыто Санкт-петербург
страница	2/11
Дата публикации	02.09.2013
Размер	0.71 Mb.
Тип	Задача

100-bal.ru > Информатика > Задача

1 2 3 4 5 6 7 8 9 10 11

Глава 1.автоматное и генетическое программирование

В настоящей главе приводятся общие концепции автоматного и генетического программирования. Рассматривается понятие «система со сложным поведением» и обосновывается применение автоматного подхода для описания систем этого типа. Приводятся примеры задач, в которых генетические алгоритмы успешно применяются для автоматизированного построения конечных автоматов.

1.1.Основные концепции автоматного программирования

В настоящем разделе описывается понятие «системы со сложным поведением» и приводятся основные идеи автоматного программирования.

1.1.1. Системы со сложным поведением

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

Будем считать, что система обладает «нетривиальным» поведением, если в ответ на возникновение некоторого события она, в зависимости от предыстории, может совершить одно из нескольких действий.

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

Вместо этого в последнее время предлагается описывать системы со сложным поведением, приписывая каждой из них некоторое множество управляющих состояний. В этих состояниях поведение системы является простым и может быть описано явно. Связь управляющих состояний с действиями и механизм переходов между состояниями удобно описывать с помощью конечных автоматов с выходами [22]. При этом все поведение системы оказывается сосредоточенной в автомате или системе взаимодействующих автоматов. Такой подход к описанию поведения называют автоматным [12].

Будем считать, что система обладает сложным поведением, если она описывается автоматом, или системой взаимодействующих автоматов с достаточно большим числом состояний и переходов.

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

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

Если в системах логического управления [23] в качестве входных воздействий используются опрашиваемые программой двоичные входные переменные и предикаты, соответствующие определенным состояниям автоматов, взаимодействующих с рассматриваемым автоматом, то для «реактивных» систем это понятие расширено. Во-первых, в качестве входных переменных применяются любые подпрограммы (функции), возвращающие двоичные значения, а, во-вторых, введены события, не только обеспечивающие возможность выполнения переходов в автоматах, но и инициирующие запуск автоматов. События могут также инициировать реализацию выходных воздействий в случае, когда состояние автомата не изменяется.

Другое отличие «реактивных» систем от систем логического управления состоит в том, что в них в качестве выходных воздействий применяются не двоичные переменные, а произвольные подпрограммы.

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

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

В качестве примера системы со сложным поведением, управляемой автоматами, приведем систему управления дизель-генератором [17]. На Рис. 1. изображена схема взаимодействия автоматов, которые образуют эту систему.

Схема взаимодействия автоматов, управляющих системой со сложным поведением

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

Парадигма автоматного программирования [16] состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления. Автоматизированный объект управления представляет собой объект управления, интегрированный с системой управления в одно устройство. При этом система управления обладает сложным поведением и представляется в виде системы взаимодействующих конечных автоматов, а объект управления обладает простым поведением и реализуется традиционными методами.

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

1 2 3 4 5 6 7 8 9 10 11

Похожие:

	Новые поступления 2 Сельское хозяйство 2 Общие вопросы сельского хозяйства 2 Агрофизический научно-исследовательский институт (Санкт-Петербург). Материалы координационного совещания Агрофизического института,...		Специальная /коррекционная/ общеобразовательная школа (VII вида)... Субъект Российской Федерации Санкт-Петербург, в лице Комитета по Образованию Санкт-Петербурга. Место нахождения Учредитель -1: 190000,...
	Экскурсионные туры в карелию Санкт- петербург приозерск – ладожское озеро валаам – сортавала – парк «рускеала» олонец александро-свирский монастырь старая ладога...		Dhl открывает новое сервисное отделение в Санкт-Петербурге Санкт-Петербург, 20 марта 2008 г Санкт-Петербург, 20 марта 2008 г. Компания dhl, мировой лидер в области экспресс-доставки и логистики, расширяет свое присутствие...
	Методическое пособие для врачей Санкт-Петербург 2007 В. Г. Беспалов, д м н., старший научный сотрудник, руководитель группы химиопрофилактики рака фгу "нии онкологии им. Н. Н. Петрова...		Реферата «г. Санкт-Петербург, как символ новой культуры, великое... Актуальность темы. Санкт-Петербург один из основных смысловых образов русской культуры. Это город-программа, город-концепция, имеющий...
	Патентам и товарным знакам (19) Санкт-Петербург, ул. Политехническая, 29, Санкт-Петербургский гту (цпи), С. В. Козыреву		Реальное и виртуальноЕ в медиапространстве современности Санкт-Петербургский Гуманитарный университет профсоюзов, г. Санкт-Петербург, Россия
	За 2011 год Санкт-Петербург 2011г Показатели административных правонарушений по районам Санкт-Петербурга в 2010 году 47		Программа по формированию навыков безопасного поведения на дорогах... Адрес: 191187, Санкт-Петербург, ул. Гагаринская, 3, Европейский Университет в Санкт-Петербурге
	Гбоу школа №619 Калининский район Санкт-Петербург Министерства образования и науки Российской Федерации, Комитета по образованию Санкт-Петербурга и школьным Положением «Об информационном...		Программа по формированию навыков безопасного поведения на дорогах... Санкт-Петербургский городской дворец творчества юных, спб гбоу лицей искусств «Санкт-Петербург»
	Лабораторные работы на уроках биологии с использованием цифрового микроскопа Государственное бюджетное образовательное учреждение гимназия №42 Приморского района Санкт-Петербурга (гбоу гимназия №42 Приморского...		Налогообложение субъектов малого бизнеса в Республике Казахстан (на примере тоо «Рэтро-2») Государственной комиссии по защите магистерских диссертаций в Санкт-Петербургском университете управления и экономики по адресу:...
	Алексей Береснев администрирование gnu/Linux с нуля санкт-Петербург «бхв-петербург» 2007 Прилагаемый компакт-диск содержит требования и проверочные тесты для экзаменов lpi-101, lpi-102, а также свободно распространяемое...		Классический санкт-петербург (5 дней / 4 ночи) Санкт-Петербургу, Петропавловская крепость, Петергоф (ансамбль фонтанов Нижнего парка), Эрмитаж, Дворцовая площадь, Царское Село...

Школьные материалы