24446

Цепи Маркова. Стационарное распределение вероятностей цепи Маркова

Контрольная

Информатика, кибернетика и программирование

Марковские процессы это процессы которые в будущем и прошлом при фиксированном настоящем являются независимыми. Рассмотрим некоторый вероятностный процесс . Пространство X называют пространством состояний а его элементы называются состоянием процесса. Считаем что пространство состояний X состоит из неотрицательных целых чисел из этого следует что процесс дискретный.

Русский

2013-08-09

101.5 KB

60 чел.

1. Цепи Маркова. Стационарное распределение вероятностей цепи Маркова. 

Марковские процессы - это процессы, которые в будущем и прошлом, при фиксированном настоящем являются независимыми.

Рассмотрим некоторый вероятностный процесс . То есть семейство случайный величин, принимающих значения из пространства X, . Пространство X называют пространством состояний, а его элементы называются состоянием процесса.

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

Если структура Марковского процесса такова, что условное распределение случайной величины  зависти только от значения  и не зависти от всех предыдущих значений, то говорят, что случайный процесс обладает Марковскими свойствами. А так как состояния дискретные, то такой процесс называется ЦЕПЬЮ МАРКОВА.

Введем обозначение:

Это вероятность того, что процесс стартуя из стояния ,за один шаг оказывается в состоянии . Это называется переходной вероятностью.

     , для всех

Для определения (задания) процесса полностью должны быть заданы конечномерные распределения. Для Марковских процессов мы должны вычислить:

Если мы начальное распределение и ноль, то эта формула позволяет вычислить вероятность, следовательно, случайный процесс задан.

Матрицы переходных вероятностей:

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

- квадратная матрица

Элементы матрицы – это условные вероятности одношагового перехода.

Если сумма строки равна 1, то матрица называется стохастической.

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

За шагов процесс перейдет из состояния в состояние .

Эти вероятности удовлетворяют уравнению Колмогорова – Чемпена:

,  - промежуточное состояние между  и .

Док –во: для случайного состояния

Это уравнение позволяет находить многошаговые условные вероятности.

Стационарное распределение цепи Маркова.

В соответствии с эргодической теоремой мы можем записать систему алгебраический уравнений. Её решение даст нам единственное стационарное распределение вероятности.

 

Все выражаются через , от него зависит .

находим из условия нормировки:

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

 ПРОВЕРИТЬ

2. Принципы микропрограммного управления.  

Для управления операцией над информацией используется информационное устройство ЦП; Каналы  Вв./Выв; Устройство управления внешними устройствами.

 Функцией операционного устройства является выполнение заданного множества операций   F={f1,….fg} над входными данными D={d1,…dn} с целью вычисления другого множества R={r1,…..rq}  представляющих собой R=fg(D)  g=1,G  Функциональная и структурная организация устройств определяющая порядок функционирования и структуру устройств базируется на принципе микропрограммного управления , кот состоит в следующем – Реализуемое устройство рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации называемых микрооперациями.

Для управления порядком следования микроопераций используются  логические условия, которые в зависимости от значения слов, преобразуемых микрооперациями, принимают значения  true/false.  Процесс выполнения операции в устройстве описывается в форме алгоритма, представленного из терминов микроопераций и логических условий и называемого микропрограммой.

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

Микропрограмма используется как форма представления функции устройства на основе  которой определяется структура и порядок  функционирования устройства по времени. Эти пути можно рассматривать как принципы микропрограммного  управления. Из которых следует, что структура и порядок функционирования операционных устройств предопределяется алгоритмом выполнения операций.


 

А также другие работы, которые могут Вас заинтересовать

20696. Розв’язання систем нелінійних рівнянь. Метод Ньютона 18.5 KB
  0001; J = [diffy1'x1' diffy1'x2' diffy1'x3' ; diffy2'x1' diffy2'x2' diffy2'x3' ; diffy3'x1' diffy3'x2' diffy3'x3' ]; p=[2;2;2]; x1=p1; x2=p2; x3=p3; dp=[inf;inf;inf]; while maxabsdp1:3 eps dp=[0;0;0]; Fk=[0;0;0]; Jk=evalJ; for i=1:3 Fki=evalFi:; end dp=invJkFk; p=pdp; x1=p1; x2=p2; x3=p3; end p 2.
20697. Криптографічна система RSA 54.28 KB
  5 зашифруємо повідомлення Створемо ключ Зашифруємо файл Відповідно до завдання лабораторної роботи проведемо розрахунки Повідомлення CRDHQS RSA p=5 q=7 N=57=35 p1q1=24 D=5 edmodp1q1=1 e5mod24=1 E=5 Ключ24 e =5 3^5 mod 35=33 18^5 mod 35=23 4^5 mod 35=9 8^5 mod 35=8 17^5 mod 35=12 19^5 mod 35=24 Зашифроване повідомлення 33 23 9 8 12 24 Розшифруєм повідомлення використовуючи ключ d=5 33 33^5 mod 35=3 23^5 mod 35=18 9^5 mod 35=4 8^5 mod 35=8 12^5 mod 35=17 24^5 mod 35=19 Висновки:...
20698. Розподіл ключів, протокол Діфф-Хеллмана 57.93 KB
  При роботі алгоритму кожна сторона: генерує випадкове натуральне число a закритий ключ спільно з віддаленою стороною встановлює відкриті параметри p і g зазвичай значення p і g генеруються на одній стороні і передаються іншій де p є випадковим простим числом g є первісних коренем по модулю p обчислює відкритий ключ A використовуючи перетворення над закритим ключем A = ga mod p обмінюється відкритими ключами з видаленою стороною обчислює загальний секретний ключ K використовуючи відкритий ключ видаленої сторони B і свій закритий ключ a...
20699. Еліптичні криві в криптографії 168.01 KB
  1КІ08 Морозов Артем Еліптична крива над полем K це множина точок проективної площини над K що задовольняють рівнянню разом з точкою на нескінченності. Отже кількість точок на кривій парна 1 точку дає по дві точки можуть давати інші елементи поля і треба не забути про точку на нескінченності. Додавання точок виконується наступним чином: 1 Нейтральний елемент групи: для будьякої точки . 3 Якщо то сумою точок та є 4 Якщо то 5 Якщо то .
20700. Генерування випадкових чисел 89.26 KB
  1КІ08 Морозов Артем Мета роботи: Усвідомити важливість проблеми генерування випадкових чисел під час вирішення задач захисту інформації ознайомитися з деякими способами генерування псевдовипадкових чисел усвідомити сильні і слабкі сторони алгоритмічних методів генерування випадкових чисел. Генератор випадкових чисел англ. Широко використовуються комп'ютерні системи для генерації випадкових чисел але часто вони малоефективні.
20701. Cтенографічний захист інформації 165.67 KB
  Для запуску програми необхідно задати: 1 звуковий файл формату МРЗ; 2 впроваджуваний файл будьякого формату; 3 пароль; 4 коефіцієнт стиснення; 5 рівень скритності. На першому етапі роботи програми впроваджуваний файл стискається з заданим користувачем коефіцієнтом стиснення. Блоксхема алгоритму роботи програми Puff представлена ​​на рисунку. Відповідно до класифікації методів впровадження інформації всі розглянуті в статті програми реалізують форматні методи.
20702. Гамування 75.04 KB
  Відкрите повідомлення MYNAMEІSARTEM Зашифруемо повідомлення Ключ k=i36mod 26 MYNAMEISARTEM 1 2 3 4 5 лат. Зашифроване повідомлення Шифрування Ci=tigimod N 16 8 4 2 1 k=i36 1 2 3 4 5 21 0 1 1 1 0 7 1 0 1 1 0 16 0 0 0 1 0 20 1 0 1 1 0 15 0 1 0 1 0 16 0 0 0 1 0 14 1 0 0 1 0 11 0 0 0 0 0 15 0 1 0 1 0 15 0 1 0 1 0 8 1 0 1 1 1 9 1 1 1 0 1 17 0 0 1 0 1 11 0 1 1 1 1 Висновки: В даній лабораторній роботі було розглянуто принципи гамування створено гаму і зашифровано за допомогою неї повідомлення.
20703. Шифри заміни 14.03 KB
  Ключ k=i27mod 33; i позиція букви у вхідному алфавіті k позиція букви у вихідному алфавіті Вхідний алфавіт: а б в г ґ д е є ж з и і ї й к л м н о п р с т у ф х ц ч ш щ ь ю я Відкрите повідомлення: Морозов Зашифроване повідомлення: Єіліціи 2. Ключ 0 1 2 3 4 5 0 ж р ш в щ г 1 о у м х ф і 2 ч а п л к з 3 д ц ь ю н ґ 4 ї и я б т с 5 е є й Відкрите повідомлення: Морозов Зашифроване повідомлення: 12100110251003 Висновки: Шифри заміни почали використовувати ще до н.е але попри те вони є популярними і на даний...
20704. Шифри перестановки 19.62 KB
  Ключ Сонечко 5 4 3 1 6 2 4 С о н е ч к о 1 2 4 4 3 5 6 м е н і т р и н а д ц я т и й м и н а л о я п а с я г н я т а з а с е л о м Виписуємо у порядку зростання цифр кожен стовбець :мнйяял еампто тяаяа ндиаам іцнсз ртлгс иионе 2 Побудова шкали рознесення і по ній шкалу набору для шифрування з подвійною перестановкою Ключ: Сонечко веселе с о н е ч к о 5 4 3 1 6 2 4 В 3 М Я Т А С л О Е 7 Е Ц И П Я Е М С 21 Н Д Й Я Г С е 7 І А М О Н А л 16 т Н И Л Я З е 7 р И н А т А Маршрут запитуваннязчитування Змінюємо рядки у відповідності зростання цифр е...