Алгоритмы Маркова
презентация к уроку по информатике и икт

Слайд 1

Слайд 2

Нормальные алгорифмы Маркова

Слайд 3

Нормальные алгорифмы Маркова Основная операция при работе алгоритмов Маркова – переработка слов в некотором алфавите А .

Слайд 4

Нормальные алгорифмы Маркова Алгоритм представляет собой совокупность строк определенного вида, порядок строк имеет важное значение. Формат строки: {a i } →{b j } [ • ]

Слайд 5

Включение слова в другое слово А = {а, б, в, ... я}. Слово Р = (параграф), Подслова Q = (ра), М = (граф).

Слайд 6

Частный случай марковских подстановок Подстановка пустых слов ( ^,Q ) , (Р, ^), (^, ^), где ^ = (...).

Слайд 7

Пример R = ( параграф ) , P = ( ра ); (R,P), ( ра → лил ); R → P‘ = ( палилграф ) .

Слайд 8

Определение Пара ( P,Q ) называется формулой марковской подстановки. Слово P называется левой частью формулы, слово Q – правой. P → ( • ) Q – заключительная подстановка; P → Q – подстановка не является заключительной

Слайд 9

Определение Упорядоченный набор формул марковских подстановок называется схемой нормального алгоритма Маркова заданного над алфавитом А: R 1 → (•) Q R 2 → Q или { Р2 → (•) Q ………… ..

Слайд 10

Правило построения последовательности слов Р = Р 0 →…→ Р i →Р i +1 →…→Р n = Q

Слайд 11

Процедура реализации нормального алгоритма Маркова В качестве Р 0 берется слово Р. I > 0 слово Р i построено, но процесс не завершился. Р i +1 = Р i , если в схеме НА нет формул, с левыми частями. Процесс построения последовательности завершен (это первый критерий останова марковского алгоритма).

Слайд 12

Процедура реализации нормального алгоритма Маркова 4. Если в схеме есть формулы с левыми частями, входящими в Р i то в качестве Р i +1 берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения её левой части в слово Р i . 5. Процесс построения последовательности является завершившимся, если на данном шаге была применена формула заключительной подстановки (это есть второй критерий останова марковского алгоритма), или продолжающимся в противном случае.

Слайд 13

Процедура реализации нормального алгоритма Маркова Если процесс построения упомянутой последовательности обрывается, то считается, что рассматриваемый нормальный марковског алгоритм применим к слову Р . Последний член последовательности Р n или Q называется результатом применения нормального марковского алгоритма к слову Р . В результате нормальный марковског алгоритм перерабатывает исходное слово Р в результирующее слово Q .

Слайд 14

Пример Марковский алгоритм задан следующей схемой над алфавитом: А = {а, b }. Введем алфавит: А = {1, 11, 111}. If (R mod 3 = 0) Then (Q = 1) else _Q = ^.

Слайд 15

Марковский алгоритм имеет следующую схему: 111 → ^ 11 → (•) ^ 1 → (•) ^ ^ → (•) 1

Слайд 16

Результирующие слова R = 111 111 1 → 1111 → 1 → ^ = Q; R' = 111 111 → 111 → ^ → 1 = Q' ; R'' = 111 11 → 11 → ^ = Q'' ; R'" = 111 111 11 → 11 111 → 11 → ^ = Q'".

Слайд 17

СПАСИБО ЗА ВНИМАНИЕ