Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Анализ вероятностного автомата



Тема 13. Вероятностные автоматы

В отличие от детерминированных автоматов, где функции переходов и выходов взаимнооднозначны:

 

в вероятностных автоматах эти функции носят вероятностный характер и задают вероятности появления состояния в момент времени t + 1и вероятности появления выходной буквы. В вероятностном автомате действует механизм случайности: состояния автомата и выходные буквы появляются случайным образом:

Эта формула задает условную вероятность того, что в момент времени t + 1 автомат перейдет в состояние a(t+l), если в момент времени t автомат был в состоянии a(t), и поступила x(t).

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

1)Вероятностный автомат Мили:

P[a(t+ 1)y(t)/a(t),x(t)] = P[a(t+ 1)/a(t), x(t)]*P[y(t)/a(t) , x(t)].

Функция перехода функция выхода

 

2) Вероятностный автомат Мура:

P[a(t+ 1)y(t)/a(t),x(t)] = P[a(t+ 1)/a(t), x(t)]*P[y(t)/a(t)].

 

3) Y - детерминированный автомат: функция переходов вероятностная, функция выходов детерминированная:

4) А - детерминированный автомат. Автомат, у которого функция переходов детерминированная:

 

Способы задания вероятностных автоматов

Методы теории вероятностей

Основным математическим аппаратом для анализа поведения ВА является широко распространенный аппарат цепей Маркова.

Практическое значение вероятностных автоматов заключается в следующем:

1) Модель ненадежно работающих устройств вычислительных машин.

2) Модель работы процессора ЭВМ в многозадачном режиме.

3) Вероятностный автомат используется для получения последовательности случайных величин, чисел, событий и т.д.

 

Вероятностная функция, описывающая поведение ВА:

P[a(t+1)y(t)/a(t), x(t)]

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

1) Функция перехода автомата из одного состояния в другое.

2) Выходная функция.

Для задания поведения ВА необходимо таким образом задавать обе эти функции. 2способа задания этих функций:

1) Табличный. Таблицы переходов вероятностных автоматов и таблицы выходов.

Таблица переходов задает вероятности появления a в момент времени t+1 ,взависимости от aв момент времени tи x в момент времени t.Для вероятностного автомата необходимо столько таблиц переходов, сколько входных букв xi. Такое



2) Таблицы выходов. Вероятность появления выходной буквы в зависимости от состояния и входной буквы.

Допустим, имеем следующее описание автомата Мили:

 

Математическое описание ВА значительно сложнее, чем ДА.

Таблица выходов для автомата Мура упрощается (зависимость только от состояния).

Следующий способ задания вероятностного автомата - графический способ. Все данные указываются на графе.

Переходы случайны: на стрелках показываются вероятности переходов.

Графический способ часто используется для анализа работы вероятностных автоматов.

 

 

Анализ и синтез вероятностных автоматов

 

Анализ вероятностного автомата.

Исходные данные - некоторая схема вероятностного автомата.

2 этапаанализа:

1) Составить таблицу переходов, уточнив входные буквы, выходные буквы и т.д.

2) Известна таблица переходов, таблица выходов неизвестна. Найти вероятности появления выходных букв.

 

Пример: В качестве вероятностного автомата возьмем триггер RS типа.

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

Составим таблицы переходов.

Сперва определяем, какие входные и какие выходные данные:

Следовательно, имеем 4 таблицы переходов:

 

(имеем симметричный триггер)

Это одношаговые таблицы переходов.

Qi— состояние автомата.

Примечание: на самом деле оба плеча триггера не одинаковы, что приводит к тому, что на практике вероятность перехода отличается от 1/2.

 


Эта страница нарушает авторские права

allrefrs.ru - 2018 год. Все права принадлежат их авторам!