<<
>>

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

Алгоритмическая система Маркова строится по тем же принципам, что и МТ, но носит более простой и интуитивно понятный характер.

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

Пусть Х – некоторый конечный алфавит, F(X) – слова алфавита, - пустое слово. Если , то выражения и называются формулами подстановки в алфавите Х:

- простая подстановка;

- окончательная подстановка.

Символы → и . не принадлежат Х.

Слова p и q могут быть пустыми.

Строка R входит в строку L, если L имеет вид L1RL2. Подстановка применима к слову, если строка соответствующая левой части подстановки входит в слово. Применение заключается в замене в преобразующем слове левой строки – правой:

Механизм работы НАМ:

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

1) Слово всегда просматривается слева направо. Схема подстановок просматривается, начиная с первой подстановки, и, если подстановку можно применить, то она применяется к самому левому вхождению этой строки в преобразуемое слово.

2) Работа алгоритма заканчивается если:

· ни одна из подстановок не применима,

· использована заключительная подстановка.

Может возникнуть ситуация, когда процесс не закончится никогда. В этом случае считают, что алгоритм не применим к слову.

Пример.

Х={x,y,z};

Нормальная схема подстановок:

xx ® y

xy ® x

yzy ® x

zz ®. z

yy ® x

Преобразуемое слово:

xxxyyyzzz →yxyyyzzz→yxyyzzz →yxyzzz→yxzzz→yxzz

Пример.

X={А,Б,В,Г,…,Я};

Нормальная схема подстановок:

Х®К

М®Р

КА®ЛОН

РУ®.С

Преобразуемое слово:

МУХА®МУКА®РУКА®РУЛОН®СЛОН

Пример 9:

X={a,b};

Нормальная схема подстановок:

a→.e

b→b

Преобразуемое слово:

bbbbbb - схема не применима.

Преобразуемое слово:

abab →bab

Пример.

Х={х,у,х-1-1};

Нормальная схема подстановок:

х х-1→е

х-1х→е

у у-1→е

у-1у→е

Преобразуемое слово:

ххухуу-1х-1ух→ ххухх-1ух→ ххуух

Пример 10:

Х={x1, …,xn};

Нормальная схема подстановок:

x1→e

x2→e

xn→e

Преобразуемое слово переписывается в пустое.

Пусть R и Q нормальные алгорифмы над алфавитом Х и pÎF(x). Запись означает, что или оба алгорифма R и Q не применимы к слову p, или оба применимы и .

Два алгорифма R и Q называют эквивалентными относительно алфавита Х, если каждый раз, когда pÎF(x) и хотя бы одно из слов R(p) или Q(p) определено и тоже принадлежит F(x).

Если для всех pÎF(x) , то R и Q называются полностью эквивалентными.

Пусть X={1}, а .

Тогда всякое натуральное число n можно записать в виде слова в алфавите :

Поставим в соответствие вектору (n1, n2, …nk), где n1, n2, …nk – натуральные числа, слово в алфавите вида , которое обозначим . Например, вектору соответствует слово 11111*1*111.

Пусть f: Nk→N – некоторая частичная функция и Rf обозначает алгорифм в алфавите такой, что

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

Функция f называется частично определимой по Маркову, если существует нормальный алгорифм Q над полностью эквивалентный Rf над . Если функция определена полностью, то ее называют просто вычислимой по Маркову.

Теорема: Простейшие функции O(x)=0, S(x)=x+1 и Im(x1,x2,…,xn)=xm вычислимы по Маркову.

Доказательство сводится к построению соответствующих алгорифмов.

1.Функцию O(x)=0 реализует следующий алгорифм R0:

={1,*}, ;

Нормальная схема подстановок:

*→* (1)

α11→ α1 (2)

α1→.1 (3)

е→ α (4)

Преобразуемое слово:

р=111…11.

Тогда по формуле (4) получаем р= α 11…11.

Применим формулу (2) и получим: р= α 11…11→ α 1…11→ α 1.

Применяем формулу (3) и получаем α 1→1.

Так как 1 – это в алфавите Х, то R0 и является искомым алгоритмом.

2. Функцию S(x)=x+1 реализует следующий алгорифм Rs:

={1,*}, ;

Нормальная схема подстановок:

*→* (1)

α1→.11 (2)

е→ α (3)

Преобразуемое слово:

р=111…11.

Тогда по формуле (3) получаем р= α 11…11 (n единиц).

Применим формулу (2) и получим: р= 111…11 (n+1 единица). Так как всякое натуральное число n можно записать в виде слова в алфавите :

, то мы реализовали алгоритм RS(n)=n+1.

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

3. Алгорифм RI имеет более сложную структуру, с ним можно ознакомиться самостоятельно в учебнике «Лекции по дискретной математике», авторы: Капитонова Ю.В. и др.

Теорема: Всякая частично рекурсивная функция частично рекурсивна по Маркову.

Обратная теорема: всякая частично вычислимая по Маркову функция является частично рекурсивной.

<< | >>
Источник: Викентьева О. Л.. Математическая логика и теория алгоритмов. Конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ. Пермь, 2007г.. 2007

Еще по теме 5.2.3. Нормальные алгорифмы Маркова:

  1. Непосредственные объекты преступлений - нормальное осуществление судопроизводства, жизнь, здоровье, законные интересы граждан. Эти преступления дискредитируют правоохранительные органы, подрывают авторитет закона и в ряде случаев способны привести к необратимым последствиям.
  2. Непосредственным объектом рассматриваемой группы преступлений является нормальная деятельность суда и других правоохранительных органов; дополнительные объекты - жизнь, здоровье, законные интересы граждан и организаций.
  3. Это, к примеру, многие представители правой части нормальной кривой.
  4. ПРЕСТУПЛЕНИЯ, ПОСЯГАЮЩИЕ НА НОРМАЛЬНУЮ ДЕЯТЕЛЬНОСТЬ ОРГАНОВ ПРАВОСУДИЯ (СТ. 294-298)
  5. Дезорганизация нормальной деятельности учреждений, обеспечивающих изоляцию от общества
  6. Проведение подобных исследований обусловлено, наряду с анализом ряда других вопросов, необходимостью обеспечить сохранность информационных ресурсов, а также нарастанием угроз национальной безопасности РФ в информационной сфере за счет получения несанкционированного доступа к информационным ресурсам и нарушения нормального функционирования информационных и телекоммуникационных систем [58]. В связи с этим анализ эффективности СЗИ сайтов органов власти, становится обязательным этапом создания лю
  7. Раздел 3. Нормальный закон распределения случайной величины
  8. 3.1. Нормальный закон распределения случайной величины
  9. 3.2. Построение кривой нормального распределения по эмпирическим данным
  10. 3.3. Проверка нормальности распределения результативного признака
  11. 1.5.1 Построение доверительного интервала для мате-матического ожидания, если дисперсия а заранее известна. Таблица стандартного нормального распределения.
  12. Нормально управляемая организация: основные характеристики
  13. Содержание дисциплины