Общие теоретические положения

Дискретный марковский процесс. Пять состояний.

 

Рис.. Граф состояний

Таблица переходов:

 

	1	2	3	4	5
1	0.1	0.2	0.3	0	0.4
2	0	0.5	0.1	0.4	0
3	0	0	0	0.7	0.3
4	0.2	0.1	0	0.3	0.4
5	0.1	0.2	0.4	0	0.3

Система уравнений:

 

                

 

Результат:

----------------Экспериментальная часть----------------

Матрица состояний имеет следующий вид:

0.1 0.3 0.6 0.6 1.0

0.0 0.5 0.6 1.0 1.0

0.0 0.0 0.0 0.7 1.0

0.2 0.3 0.3 0.6 1.0

0.1 0.3 0.7 0.7 1.0

Вероятности равны:

p1 = 0.11 p2 = 0.186 p3 = 0.165 p4 = 0.262 p5 = 0.277

----------------Теоретическая часть----------------

Изначальная матрица переходов имеет вид:

0.1 0.2 0.3 0.0 0.4

0.0 0.5 0.1 0.4 0.0

0.0 0.0 0.0 0.7 0.3

0.2 0.1 0.0 0.3 0.4

0.1 0.2 0.4 0.0 0.3

 Среднее значение рядка 1 = 1.0

Среднее значение рядка 2 = 1.0

Среднее значение рядка 3 = 1.0

 Транспонируем матрицу:

0.1 0.0 0.0 0.2 0.1

0.2 0.5 0.0 0.1 0.2

0.3 0.1 0.0 0.0 0.4

0.0 0.4 0.7 0.3 0.0

0.4 0.0 0.3 0.4 0.3

Умножаем матрицу на следующий вектор:

1.0

0.0

0.0

0.0

0.0

Вероятности равны:

p1= 0.1 p2= 0.2 p3= 0.3 p4= 0.0 p5= 0.4     

Вероятности равны:

p1= 0.05 p2= 0.2 p3= 0.21 p4= 0.29 p5= 0.25   

Вероятности равны:

p1= 0.088 p2= 0.189 p3= 0.135 p4= 0.314 p5= 0.274 

Вероятности равны:

p1= 0.099 p2= 0.1983 p3= 0.1549 p4= 0.2643 p5= 0.2835

Вероятности равны:

p1= 0.0912 p2= 0.2021 p3= 0.1629 p4= 0.267 p5= 0.2769

Вероятности равны:

p1= 0.0902 p2= 0.2014 p3= 0.1584 p4= 0.2749 p5= 0.2753

Вероятности равны:

p1= 0.0915 p2= 0.2013 p3= 0.1573 p4= 0.274 p5= 0.2762

 

Задание к работе:

 

Определить, существует ли стационарный режим для марковского случайного процесса, размеченный граф состояний которого изображен на рисунке. Если стационарный режим существует, то найти стационарное распределение вероятностей.

Указание. Проведите классификацию состояний системы и примените следствия из теоремы Маркова.

 

А2

А1

А5

А4

А3

А6

1

3

1

9

7

3

3

2

11

4

2

А1

А2

А3

А5

А4

7

3

4

2

1

5

6

1. а)                                                                                          б)

 

А2

А1

А5

А4

А3

А6

2

7

4

3

2

3

2

3

1

5

1

А1

А2

А3

А5

А4

1

3

5

1

3

7

1

2

2. а)                                                                          б)

 

А1

А2

А3

А4

А5

А6

3

7

2

3

3

9

8

5

1

А3

А5

А4

А1

А2

3

2

2

1

5

7

4

3

3. а)                                                                                          б)

 

А3

А5

А4

А1

А2

1

2

3

7

8

9

6

5

А1

А2

А3

А4

А5

А6

1

2

3

2

3

9

2

1

5

1

4. а)                                                                                          б)

 

 

             

6

А1

А2

А6

А4

А3

А5

3

2

3

2

5

1

3

А1

А3

А2

А4

А6

А5

2

4

9

6

4

3

5

4

7

7

5. а)                                                                                                         б)

 

 

А1

А3

А2

А4

А6

А5

А1

А2

А6

А4

А3

А5

1

3

1

5

2

6

9

3

2

11

3

6

5

2

8

7

3

2

5

4

а)                                                                                              б)

 

 

А1

А2

А3

А4

А5

6

3

3

1

2

5

7

2

А1

А3

А2

А4

А6

А5

2

7

6

3

6

5

3

4

5

7. а)                                                                          б)

 

 

А1

А2

А3

А4

А5

6

3

3

3

2

5

8

5

2

А1

А3

А2

А4

А6

А5

1

2

2

5

4

3

7

9

3

6

8. а)                                                                          б)

 

9

А4

А1

А2

А3

А5

А6

7

11

2

9

3

2

5

7

А5

А1

А2

А4

А3

8

7

3

2

1

5

2

4

9. а)                                                                          б)

 

 

А4

А1

А2

А3

А5

А6

3

5

8

4

9

7

7

А5

А1

А2

А4

А3

6

5

7

5

4

2

7

3

1

4

10. а)                                                                                       б)

 

 

Порядок выполнения работы:

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

 

Содержание отчета:

1. Тема.

2. Цель.

3. Задачи.

4. Материальное обеспечение.

5. Практическое задание.

Вопросы для самоконтроля:

 

1. Дайте определение матрице переходов в конечном графе?

2. Из чего состоит конечный автомат?

Практическая работа № 24

Тема: Решение задач по теории конечных автоматов. Таблицы

Цель: отработать навыки в решении задач в теории конечных автоматов, используя таблицы.

 

Материальное обеспечение: практическая работа

 

Общие теоретические положения

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

Задача. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов:

xj /ai	a0	a1	a2
x1	a1/y1	a1/y2	a1/y2
x2	a2/y3	a2/y3	a0/y1

В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ.

A = {a₀, a₁, a₂}; X = {x₁, x₂}; Y = {y₁, y₂, y₃}. Здесь M + 1 = 3; F = 2, G = 3.

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

= 2,

= 1,

=2.

Таким образом необходимо иметь два элементарных автомата Q1 и Q2, один входной канал a и два выходных канала z₁ и z₂ (каналы a и z называют еще физическими входами и выходами автомата соответственно).

2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.

Таблица кодирования состояний автомата

aj	Q1	Q2
a0	0	0
a1	0	1
a2	1	0

Таблица кодирования входных сигналов

xf	O1
x1	0
x2	1

Таблица кодирования выходных сигналов

yg	z1	z2
y1	0	0
y2	0	1
y3	1	0

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

xj /ai	00	01	10
0	01/00	01/01	01/01
1	10/10	10/10	00/00

3. Построим кодированные таблицы переходов и выходов. Эти таблицы определяют зависимости состояний элементарных автоматов и выходных сигналов в момент времени (t + 1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t, т.е.:

Кодированная таблица переходов и выходов имеет следующий вид:

t					t + 1
a	O1	Q2	z1	z2	O1	Q2
0	0	0	0	0	0	1
0	0	1	0	1	0	1
0	1	0	0	1	0	1
0	1	1	-	-	-	-
1	0	0	1	0	1	0
1	0	1	1	0	1	0
1	1	0	0	0	0	0
1	1	1	-	-	-	-

Порядок выполнения работы:

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

 

Содержание отчета:

1. Тема.

2. Цель.

3. Задачи.

4. Материальное обеспечение.

5. Практическое задание.

Вопросы для самоконтроля:

 

1. Дайте определение комбинационного автомата. Приведите примеры и таблицы истинности КА.

2. Реализуйте операции И, ИЛИ, НЕ на элементах ИЛИ-НЕ,

3. Занесите на карту Карно функцию 5 переменных (a, b, c, d, e).

           

Практическая работа № 25

 

Тема: Решение задач по теории конечных автоматов. Графы.

Цель: отработать навыки в решении задач в теории конечных автоматов, используя графы.

Материальное обеспечение: практическая работа

---

Дата добавления: 2019-02-22; просмотров: 222; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!