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

Слайд 1

Слайд 2

Теория нормальных алгоритмов была разработана советским математиком Андреем Андреевичем Марковым в конце 1940-х годов. При изучении разрешимости некоторых задач алгебры, он предложил новую модель вычислений, которую назвал нормальными алгорифмами . Андрей Андреевич Марков (младший) (22.09.1903-11.10.1979) – советский математик, сын известного русского математика А.А.Маркова, основоположник советской школы конструктивной математики, автор понятия нормального алгоритма (1947 г.)

Слайд 3

Нормальные алгорифмы Маркова (НАМ) — это строгая математическая форма записи алгоритмов обработки символьных строк, которую можно использовать для доказательства разрешимости или неразрешимости различных задач. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите. При этом исходные данные и результат работы алгоритма являются словами в этом алфавите.

Слайд 4

Марков предположил, что любой алгоритм можно записать как НАМ . В отличие от машин Тьюринга НАМ — это "чистый” алгоритм, который не связан ни с каким "аппаратным обеспечением” (лентой, кареткой и т.п.). НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задается алфавитом и системой подстановок .

Слайд 5

Алфавитом будем называть любое непустое множество. Его элементы называются буквами , а любая последовательность букв – словами в данном алфавите Для удобства рассуждений допускается пустое слово , которые обозначим  Слова будем обозначать буквами Р, Q, R и с индексами

Слайд 6

Формулой подстановки называется запись вида α→β (читается «α заменить на β»), где α и β – любые слова (возможно, и пустые). При этом α называется левой частью формулы, а β – правой частью . Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Условно это можно изобразить так:

Слайд 7

Правила выполнения НАМ Прежде всего, задается некоторое входное слово Р. Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р , т.е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р′. На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т.е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р′, после чего выполняется соответствующая подстановка и получается новое слово Р′′. И так далее: Р → Р′ → Р′′ → …  Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой. Необходимые уточнения: 1. Если на очередном шаге была применена обычная формула (α→β), то работа НАМ продолжается. 2. Если же на очередном шаге была применена заключительная формула (α ו  β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову.

Слайд 10

Марковской подстановкой (Р, Q ) называется следующая операция над словами: в заданном слове R находят первое вхождение слова Р и, не изменяя остальных частей слова R , заменяют в нем это вхождение словом Q Рассмотрим упорядоченную пару слов (Р, Q)

Слайд 11

Замечание: 1) Полученное слово называется результатом применения марковской подстановки (Р, Q) к слову R 2) Если первого вхождения слова Р в слово R нет (и, следовательно, вообще нет ни одного вхождения Р в R) , то считается что марковская подстановка (Р, Q) не применима к слову R

Слайд 12

Частными случаями марковских подстановок являются подстановки с пустыми словами: (  , Q ), ( P,  ), (  ,  )

Слайд 13

Для обозначения марковской подстановки (Р, Q ) используют запись Р  Q Эту запись называют формулой подстановки (Р, Q ) Различают простые подстановки Р  Q и заключительные подстановки Р ו  Q

Слайд 14

Пример Данное слово: 5 21421 Подстановка: 21  3 Результат подстановки: 5343

Слайд 15

Пример Данное слово: 5 21421 Подстановка: 21 ו   Результат подстановки: 5421

Слайд 16

Пример Данное слово: 5 21421 Подстановка: 25  7 Результат подстановки: Не применима

Слайд 17

Создавать - лучше, чем уничтожать, а дарить - лучше, чем принимать