НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

АВТОМАТА ПОВЕДЕНИЕ

Расстановка ударений: АВТОМА`ТА ПОВЕДЕ`НИЕ

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

Специальным случаем является так наз. А. п. в случайной среде. Под средой здесь можно понимать вероятностный автомат , преобразующий выходные сигналы рассматриваемого автомата в его входные сигналы. Так что можно считать, что автомат в случайной среде представляет собой автономную логич. сеть, построенную из автоматов и путем соединения выхода каждого из этих автоматов со входом другого. Тогда поведение автомата в случайной среде можно рассматривать как функционирование указанной автономной логич. сети. Среда наз. стационарной, если она является автоматом с одним состоянием. Если рассматривать выходные сигналы автомата как различные «поощрения» или «наказания» автомата , то естественно возникает задача построения автомата , поведение к-рого в среде является оптимальным, т. е. дает наибольший возможный в данной среде выигрыш. Обычно предполагается, что выходной алфавит среды состоит из букв 0 и 1 и в ответ на выходные сигналы b1, ..., bk автомата буква 1 выдается, соответственно, с вероятностями р1, ..., pk . При этом «поощрением» автомата считается только буква 1.

Если среда стационарна, то множество состояний автономной логич. сети совпадает с множеством состояний автомата . Если, кроме того, выходная буква автомата однозначно определяется состоянием, то Функционирование этой логич. сети может быть описано стохастич. матрицей Q переходов состояний. Как правило, рассматривают случаи, когда матрица Q эргодическая (см. Эргодичность). Тогда определена функция:

где σi - сумма финальных вероятностей всех состояний, определяющих выходную букву bi . При этом

Если выходные сигналы автомата не зависят от воздействий среды и равновероятны, т. е. σ1 = σ2 =... = σk = 1/k, то

Функция W(, ) является математич. ожиданием величины, наз. выигрышем автомата в среде . Говорят, что автомат обладает целесообразным поведением в среде , если W(, ) < W0 . Задача об оптимальном поведении в случайной среде ставится следующим образом. Требуется построить так наз. асимптотически оптимальную последовательность автоматов 01, 2,... такую, что математич. ожидание выигрыша автомата n с ростом n стремится к максимальному выигрышу в данной среде, равному величине dmax = {2рi - 1, i = 1, ..., k}. В рассматриваемом случае такую последовательность образуют так наз. автоматы с линейной тактикой при условии, что dmax ≥ ½. [Автомат с линейной тактикой n с k-буквенным выходным алфавитом имеет kn состояний sij, i = 1, ..., k, j = 1, ..., n, и следующие функции φ и ψ переходов и выходов:

φ (sij, 1) = si, j + 1, если j = 1, 2, ..., n - 1, φ (sin, 1) = sin, φ (sij, 0) = si, j - 1, если j = 2, ..., n, φ (si1, 0) = si + 1, 1, ψ (sij, a) = bi, i = 1, ..., k, j = 1, ..., n.]

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

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

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

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


Источники:

  1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru