Математическая энциклопедия » Что такое «Автомата Поведение»?

Значение слова, определение и толкование термина

Автомата Поведение

Avtomata Povedeniye

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

Специальным случаем является так наз. А. п. в случайной среде. Под средой здесь можно понимать вероятностный автомат [Автомата Поведение. Фото 1] преобразующий выходные сигналы рассматриваемого автомата [Автомата Поведение. Фото 2] в его входные сигналы. Так что можно считать, что автомат [Автомата Поведение. Фото 3] в случайной среде [Автомата Поведение. Фото 4] представляет собой автономную логич. сеть, построенную из автоматов [Автомата Поведение. Фото 5] путем соединения выхода каждого из этих автоматов со входом другого. Тогда поведение автомата [Автомата Поведение. Фото 6] в случайной среде [Автомата Поведение. Фото 7] можно рассматривать как функционирование указанной автономной логич. сети. Среда [Автомата Поведение. Фото 8] наз. стационарной, если она является автоматом с одним состоянием. Если рассматривать выходные сигналы автомата [Автомата Поведение. Фото 9] как различные "поощрения" или "наказания" автомата [Автомата Поведение. Фото 10] то естественно возникает задача построения автомата [Автомата Поведение. Фото 11] поведение к-рого в среде [Автомата Поведение. Фото 12] является оптимальным, т. е. дает наибольший возможный в данной среде выигрыш. Обычно предполагается, что выходной алфавит среды [Автомата Поведение. Фото 13] состоит из букв 0 и 1 и в ответ на выходные сигналы [Автомата Поведение. Фото 14] автомата [Автомата Поведение. Фото 15] буква 1 выдается, соответственно, с вероятностями [Автомата Поведение. Фото 16] При этом "поощрением" автомата [Автомата Поведение. Фото 17] считается только буква 1.

Если среда [Автомата Поведение. Фото 18] стационарна, то множество состояний автономной логич. сети совпадает с множеством состояний автомата [Автомата Поведение. Фото 19] Если, кроме того, выходная буква автомата [Автомата Поведение. Фото 20] однозначно определяется состоянием, то функционирование этой логич. сети может быть описано стохастич. матрицей [Автомата Поведение. Фото 21] переходов состояний. Как правило, рассматривают случаи, когда матрица [Автомата Поведение. Фото 22] эргодическая (см. Эргодичность). Тогда определена функция:

[Автомата Поведение. Фото 23]

где [Автомата Поведение. Фото 24] - сумма финальных вероятностей всех состояний, определяющих выходную букву [Автомата Поведение. Фото 25] При этом

[Автомата Поведение. Фото 26]

Если выходные сигналы автомата [Автомата Поведение. Фото 27] не зависят от воздействий среды и равновероятны, т. о.[Автомата Поведение. Фото 28][Автомата Поведение. Фото 29] то

[Автомата Поведение. Фото 30]

Функция [Автомата Поведение. Фото 31] является математич. ожиданием величины, наз. выигрышем автомата [Автомата Поведение. Фото 32] в среде [Автомата Поведение. Фото 33] Говорят, что автомат [Автомата Поведение. Фото 34] обладает целесообразным поведением в среде [Автомата Поведение. Фото 35] если [Автомата Поведение. Фото 36] Задача об оптимальном поведении в случайной среде ставится следующим образом. Требуется построить так наз. асимптотически оптимальную последовательность автоматов [Автомата Поведение. Фото 37] такую, что математич. ожидание выигрыша автомата [Автомата Поведение. Фото 38] с ростом пстремится к максимальному выигрышу в данной среде, равному величине [Автомата Поведение. Фото 39][Автомата Поведение. Фото 40] В рассматриваемом случае такую последовательность образуют так наз. автоматы с линейной тактике и при условии, что [Автомата Поведение. Фото 41] [Автомат с линейной тактикой [Автомата Поведение. Фото 42] с k- буквенным выходным алфавитом имеет kn состояний [Автомата Поведение. Фото 43] [Автомата Поведение. Фото 44] и следующие функции [Автомата Поведение. Фото 45] переходов и выходов:

[Автомата Поведение. Фото 46]

Впервые правила асимптотически оптимального поведения в стационарной случайной среде начали изучаться в математич. статистике. Однако получаемые там результаты естественно переводятся на язык теории автоматов.

Рассматривается А. н. и в более сложных средах, а также поведение коллективов автоматов в случайных средах. В последнем случае автоматы рассматриваются как игроки, а правила игры, в к-рой участвуют эти автоматы, выступают в роли среды.

Лит.:[1] Барздинь Я. М., Трахтенброт Б. А., Конечные автоматы (Поведение и синтез), М., 1970; [2] Цетлин М. Л., Исследования по теории автоматов и моделированию биологических систем, М., 1969: [3] Bobbins H., "Ргос. Nat. Acad. Sci. U.S.A.", 1956, v. 42, № 12, p. 920-923.

В. Б. Кудрявцев, Ю. И. Янов.

  • ВКонтакте

  • Facebook

  • Мой мир@mail.ru

  • Twitter

  • Одноклассники

  • Google+

См. также

  • (от лат. approximo - приближаюсь), замена одних матем. объектов (напр., чисел или функций) другими, более простыми и в том или ином смысле близкими к

  • редко применяемая единица времени, равная 1/60 с.