Начальная

Windows Commander

Far
WinNavigator
Frigate
Norton Commander
WinNC
Dos Navigator
Servant Salamander
Turbo Browser

Winamp, Skins, Plugins
Необходимые Утилиты
Текстовые редакторы
Юмор

File managers and best utilites

AlgStr / Библиотека / Понятия / Нормальный алгоритм. Эмулятор нормальных алгоритмов маркова


Сборник упражнений по алгоритмическим схемам (МТ и НАМ)

В данном сборнике отражены типичные задачи по алгоритмическим схемам «Машина Тьюринга» (МТ) и «Нормальные Алгоритмы Маркова» (НАМ), которые решаются на семинарских занятиях студентами 110 и 111 групп на 1 курсе ВМиК МГУ.

Для проверки своих решений можете прибегнуть к помощи интерактивного эмулятора нормальных алгоритмов Маркова, либо машины Тьюринга.

Принятые в тексте обозначения:

  • А  — исходный алфавит алгоритмической схемы.
  • P  — означает входное слово.
  • Λ — означает пустой символ для МТ или пустое слово для НАМ. При решении задач по алгоритмическим схемам всегда необходимо проверять граничные условия. Необходимо проверить, как алгоритм реагирует на пустые входные слова, и слова, не удовлетворяющие условию задачи.

Базовые задачи

  • Дан алфавит A = {a, b, c}. Перенести в начало все a.
  • Дан алфавит A = {a, b, c}. Упорядочить буквы в P  по алфавиту.
  • Дан алфавит A = {*, a, b, c}, P  = *Q , где *∉Q. Получить Q*.
  • Дан алфавит A = {a, b, c}. Если входное словоP  содержит букву a то написать a, иначе Λ
  • Дан алфавит A = {a, b, c}. Приписать к входному слову P  букву a: P  →P a.
  • Дан алфавит A = {a, b, c}. Приписать к входному слову P  слово aba: P  →P aba.
  • Дан алфавит A = {a, b, c}. Написать 1, если входное слово P  чётной длины, иначе написать 2.
  • Дан алфавит A = {a, b, c}. Удвоить последнюю букву входного слова P  = Qξ: P  → Q ξξ.
  • Дан алфавит A = {a, b, c}. Приписать к слову P  слева его первую букву.
  • Дан алфавит A = {a, b, c}. Переставить первую букву P  в его конец.
  • Дан алфавит A = {a, b, c}. Удвоить каждую букву P .
  • Дан алфавит A = {a, b, c}. Заменить последнее вхождение буквы a в P  на bb. Если a∉P , то оставить P  без изменений.
  • Дан алфавит A = {a, b, c} Удалить второе вхождение a.
  • Дан алфавит A = {a, b, c}. Если в P  входит буква a ещё раз, тогда написать a, иначе Λ.
  • Дан алфавит A = {a, b, c}. Приписать к концу P  столько палочек, сколько раз буква b входит в P . Пример: abcbb → abcbb|||.
  • Дан алфавит A = {|, >}, P  = |||...||>. Входное слово P  представляет собой запись некоторого числа n в палочной системе счисления, в конце которой стоит знак >. Дописать число n в палочной системе счисления после знака > (дописать n палочек). Пример: ||||> → ||||>||||.
  • Дан алфавит A = {|, −}, P  = |||...||−|||...||. Входное слово P  представляет собой запись некоторых чисел n и m в палочной системе счисления, разделённую знаком «−». Получить запись модуля разности n и m в палочной системе счисления. Пример: |−||| → ||.
  • Дан алфавит A = {|, *, =}, P  = |||...||*|||...||=. Входное слово P  содержит n палочек слева от знака * и m палочек справа. В конце стоит знак =. Дописать справа от знака = nm палочек. Пример: ||*|||= → ||*|||=||||||.
  • Дан алфавит A = {a, b, c}. Если P  = abc, то написать a, иначе Λ.
  • Дан алфавит A = {a, b}, входное слово P  чётной длины. Стереть правую половину слова P . Пример: babbaa → bab.
  • Дан алфавит A = {a, b}. Обратить входное слово P . Пример: babbaa → aabbab.
  • Дан алфавит A = {0, 1}. Входное слово P  представляет собой двоичную запись некоторого числа n. Написать число n + 1 в двоичной системе счисления. Пример: 1011 → 1100.
  • Дан алфавит A = {|}. Входное слово P  представляет собой запись некоторого числа n в палочной системе счисления. Написать двоичную запись числа n. Пример: ||||| → 101.
  • Дан алфавит A = {0, 1}. Входное слово P  представляет собой двоичную запись некоторого числа n. Написать в двоичной системе счисления остаток от деления n на двоичное число 112. Пример: 101 → 10.Примечание: Не смотря на то, что решение задачи в рамках двочиной системы счисления занимает не более 5 строк, поиск его достаточно нетривиален, поэтому в решении допускается переход из двоичной системы счисления в палочную и обратно.
  • Дан алфавит A = {a, b}. Удвоить входное слово P : P →P P . Пример: abb → abbabb.

Задачи для самостоятельных работ

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

  • Дан алфавит A = {a, b, c}. Если во входное слово P  входит буква b, то заменить все вхождения букв b на с.
  • Дан алфавит A = {a, b, c}. Заменить во входном слове P  все вхождения ba, на a.
  • Дан алфавит A = {a, b}. Заменить во входном слове P  все стоящие на чётных позициях вхождения b на bab. Пример: abaababb → ababaababbab.
  • Дан алфавит A = {a, b}. Удалить во входном слове P  два последних вхождения буквы a. Пример: aabaababb → aababbb.

cmcmsu.info

Нормальные алгоритмы Маркова Википедия

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

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

Описание

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

Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида L→D{\displaystyle L\to D}, где L{\displaystyle L} и D{\displaystyle D} — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида L→⋅D{\displaystyle L\to \cdot D}, где L{\displaystyle L} и D{\displaystyle D} — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы →{\displaystyle \to } и →⋅{\displaystyle \to \cdot } не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите |∗abc{\displaystyle |*abc} может служить схема

{|b→ba|ab→bab→∗|→b∗∗→c|c→cac→c|c→⋅{\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.}

Процесс применения нормального алгоритма к произвольному слову V{\displaystyle V} в алфавите этого алгоритма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V′{\displaystyle V'} — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V{\displaystyle V}, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V′{\displaystyle V'}, то работа алгорифма считается завершённой, и результатом этой работы считается слово V′{\displaystyle V'}. Иначе среди формул подстановки, левая часть которых входит в V′{\displaystyle V'}, выбирается самая первая. Если эта формула подстановки имеет вид L→⋅D{\displaystyle L\to \cdot D}, то из всех возможных представлений слова V′{\displaystyle V'} в виде RLS{\displaystyle RLS} выбирается такое, при котором R{\displaystyle R} — самое короткое, после чего работа алгорифма считается завершённой с результатом RDS{\displaystyle RDS}. Если же эта формула подстановки имеет вид L→D{\displaystyle L\to D}, то из всех возможных представлений слова V′{\displaystyle V'} в виде RLS{\displaystyle RLS} выбирается такое, при котором R{\displaystyle R} — самое короткое, после чего слово RDS{\displaystyle RDS} считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову |∗||{\displaystyle |*||} последовательно возникают слова |b∗|{\displaystyle |b*|}, ba|∗|{\displaystyle ba|*|}, a|∗|{\displaystyle a|*|}, a|b∗{\displaystyle a|b*}, aba|∗{\displaystyle aba|*}, baa|∗{\displaystyle baa|*}, aa|∗{\displaystyle aa|*}, aa|c{\displaystyle aa|c}, aac{\displaystyle aac}, ac|{\displaystyle ac|} и c||{\displaystyle c||}, после чего алгорифм завершает работу с результатом ||{\displaystyle ||}. Другие примеры смотрите ниже.

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.

Примеры

Пример 1

Использование алгоритма Маркова для преобразований над строками.

Алфавит:

{ а...я, А...Я, "пробел", "точка" }

Правила:

  1. А → апельсин
  2. кг → килограмм
  3. М → магазинчике
  4. Т → том
  5. магазинчике →. ларьке (заключительная формула)
  6. в том ларьке → на том рынке

Исходная строка:

Я купил кг Аов в Т М.

При выполнении алгоритма строка претерпевает следующие изменения:

  1. Я купил кг апельсинов в Т М.
  2. Я купил килограмм апельсинов в Т М.
  3. Я купил килограмм апельсинов в Т магазинчике.
  4. Я купил килограмм апельсинов в том магазинчике.
  5. Я купил килограмм апельсинов в том ларьке.

На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).

Пример 2

Данный алгоритм преобразует двоичные числа в «единичные» (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.

Алфавит:

{ 0, 1, | }

Правила:

  1. 1 → 0|
  2. |0 → 0||
  3. 0 → "" (пустая строка)

Исходная строка:

101

Выполнение:

  1. 0|01
  2. 0|00|
  3. 00||0|
  4. 00|0|||
  5. 000|||||
  6. 00|||||
  7. 0|||||
  8. |||||

См. также

Прочие абстрактные исполнители и формальные системы вычислений

Языки, основанные на нормальных алгоритмах

Ссылки

Примечания

wikiredia.ru

Нормальный алгоритм

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

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

Описание

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

Примером схемы нормального алгоритма в пятибуквенном алфавите | * abcможет служить схема

Процесс применения нормального алгоритма к произвольному слову Vв алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. ПустьV' — слово, полученное на предыдущем шаге работы алгорифма (или исходное словоV, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы вV', то работа алгоритма считается завершённой, и результатом этой работы считается словоV'. Иначе среди формул подстановки, левая часть которых входит вV', выбирается самая верхняя. Если эта формула подстановки имеет вид, то из всех возможных представлений словаV' в видеRLSвыбирается такое, при которомR— самое короткое, после чего работа алгоритма считается завершённой с результатомRDS. Если же эта формула подстановки имеет вид, то из всех возможных представлений словаV' в видеRLSвыбирается такое, при которомR— самое короткое, после чего словоRDSсчитается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову | * | | последовательно возникают слова | b* | ,ba| * | ,a| * | ,a|b* ,aba| * ,baa| * ,aa| * ,aa|c,aac,ac| иc| | , после чего алгорифм завершает работу с результатом | | . Другие примеры смотрите ниже.

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Варианттезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языкеРефал.

Примеры

Пример 1

Использование алгоритма Маркова для преобразований над строками:

Правила:

  1. «А» → «апельсин»

  2. «кг» → «килограмм»

  3. «М» → «магазинчике»

  4. «Т» → «том»

  5. «магазинчике» →• "ларьке" (заключительная формула)

  6. «в том ларьке» → «на том рынке»

Исходная строка:

«Я купил кг Аов в Т М.»

При выполнении алгоритма строка претерпевает следующие изменения:

  1. «Я купил кг апельсинов в Т М.»

  2. «Я купил килограмм апельсинов в Т М.»

  3. «Я купил килограмм апельсинов в Т магазинчике.»

  4. «Я купил килограмм апельсинов в том магазинчике.»

  5. «Я купил килограмм апельсинов в том ларьке.»

На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).

Пример 2

Данный алгоритм преобразует двоичные числав «единичные», то есть на выходе получается строка из N единичек, если на входе у нас было N в двоичной системе. Например, 101 преобразуется в 5 единиц:

Правила:

  1. «|0» → "0||"

  2. «1» → "0|"

  3. «0» → ""

Исходная строка:

«101»

Выполнение:

  1. «0|01»

  2. «00||1»

  3. "00||0|"

  4. "00|0|||"

  5. "000|||||"

  6. "00|||||"

  7. "0|||||"

  8. "|||||"

См. также

Прочие абстрактные исполнители и формальные системы вычислений

  • Машина Тьюринга(автоматное программирование)

  • Машина Поста(автоматное программирование)

  • Рекурсивная функция (теория вычислимости)

  • Лямбда-исчисление(функциональное программирование)

  • Brainfuck(императивное программирование)

studfiles.net

Нормальный алгоритм Маркова Википедия

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

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

Описание

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

Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида L→D{\displaystyle L\to D}, где L{\displaystyle L} и D{\displaystyle D} — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида L→⋅D{\displaystyle L\to \cdot D}, где L{\displaystyle L} и D{\displaystyle D} — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы →{\displaystyle \to } и →⋅{\displaystyle \to \cdot } не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите |∗abc{\displaystyle |*abc} может служить схема

{|b→ba|ab→bab→∗|→b∗∗→c|c→cac→c|c→⋅{\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.}

Процесс применения нормального алгоритма к произвольному слову V{\displaystyle V} в алфавите этого алгоритма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V′{\displaystyle V'} — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V{\displaystyle V}, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V′{\displaystyle V'}, то работа алгорифма считается завершённой, и результатом этой работы считается слово V′{\displaystyle V'}. Иначе среди формул подстановки, левая часть которых входит в V′{\displaystyle V'}, выбирается самая первая. Если эта формула подстановки имеет вид L→⋅D{\displaystyle L\to \cdot D}, то из всех возможных представлений слова V′{\displaystyle V'} в виде RLS{\displaystyle RLS} выбирается такое, при котором R{\displaystyle R} — самое короткое, после чего работа алгорифма считается завершённой с результатом RDS{\displaystyle RDS}. Если же эта формула подстановки имеет вид L→D{\displaystyle L\to D}, то из всех возможных представлений слова V′{\displaystyle V'} в виде RLS{\displaystyle RLS} выбирается такое, при котором R{\displaystyle R} — самое короткое, после чего слово RDS{\displaystyle RDS} считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгорифма с указанной выше схемой к слову |∗||{\displaystyle |*||} последовательно возникают слова |b∗|{\displaystyle |b*|}, ba|∗|{\displaystyle ba|*|}, a|∗|{\displaystyle a|*|}, a|b∗{\displaystyle a|b*}, aba|∗{\displaystyle aba|*}, baa|∗{\displaystyle baa|*}, aa|∗{\displaystyle aa|*}, aa|c{\displaystyle aa|c}, aac{\displaystyle aac}, ac|{\displaystyle ac|} и c||{\displaystyle c||}, после чего алгорифм завершает работу с результатом ||{\displaystyle ||}. Другие примеры смотрите ниже.

Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.

Примеры

Пример 1

Использование алгоритма Маркова для преобразований над строками.

Алфавит:

{ а...я, А...Я, "пробел", "точка" }

Правила:

  1. А → апельсин
  2. кг → килограмм
  3. М → магазинчике
  4. Т → том
  5. магазинчике →. ларьке (заключительная формула)
  6. в том ларьке → на том рынке

Исходная строка:

Я купил кг Аов в Т М.

При выполнении алгоритма строка претерпевает следующие изменения:

  1. Я купил кг апельсинов в Т М.
  2. Я купил килограмм апельсинов в Т М.
  3. Я купил килограмм апельсинов в Т магазинчике.
  4. Я купил килограмм апельсинов в том магазинчике.
  5. Я купил килограмм апельсинов в том ларьке.

На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).

Пример 2

Данный алгоритм преобразует двоичные числа в «единичные» (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.

Алфавит:

{ 0, 1, | }

Правила:

  1. 1 → 0|
  2. |0 → 0||
  3. 0 → "" (пустая строка)

Исходная строка:

101

Выполнение:

  1. 0|01
  2. 0|00|
  3. 00||0|
  4. 00|0|||
  5. 000|||||
  6. 00|||||
  7. 0|||||
  8. |||||

См. также

Прочие абстрактные исполнители и формальные системы вычислений

Языки, основанные на нормальных алгоритмах

Ссылки

Примечания

wikiredia.ru

Нормальные алгоритмы Маркова Википедия

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

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

Описание[ | код]

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

Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида L→D{\displaystyle L\to D}, где L{\displaystyle L} и D{\displaystyle D} — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида L→⋅D{\displaystyle L\to \cdot D}, где L{\displaystyle L} и D{\displaystyle D} — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы →{\displaystyle \to } и →⋅{\displaystyle \to \cdot } не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите |∗abc{\displaystyle |*abc} может служить схема

{|b→ba|ab→bab→∗|→b∗∗→c|c→cac→c|c→⋅{\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.}

Процесс применения нормального алгоритма к произвольному слову V{\displaystyle V}

ru-wiki.ru

7.4. Нормальные алгоритмы маркова

Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.

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

Рассмотрим два слова NиМв некотором алфавитеА.ЕслиNявляется частьюМ, то говорят, чтоNвходит вМ.

Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., гдеN, М, S, Т,... -слова в этом алфавите. Любую подстановкуN-Mможно применить к некоторому словуКследующим способом: если вКимеется одно или несколько вхождений словаN,то любое из них может быть заменено словомМ,и, наоборот, если имеется вхождениеМ,то его можно заменить словомN.

Например, в алфавите А = {а, b, с}имеются словаN=ab, М = bcb, К = abcbcbab, Заменив в словеКсловоNнаМ,получимbcbcbcbabилиabcbcbbcb,и, наоборот, заменивМнаN,получимaabcbabилиаbсаbаb.

Подстановка ab - bcbнедопустима к словуbacb,так как ниab,ниbcbне входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называютассоциативным исчислением.Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

Слова P1иР2в некотором ассоциативном исчислении называются смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки.

Последовательность слов Р, P1, Р2, ..., Мназывается дедуктивной цепочкой, ведущей от словаР ксловуМ,если каждое из двух рядом стоящих слов этой цепочки - смежное.

Слова РиМназывают эквивалентными, если существует цепочка отРкМи обратно.

Пример

Алфавит Подстановки

{а, b, с, d, е} ас - сa, abac - abace

ad - da; eca - ae

bc - cb; eda - be

bd - db; edb - be

Слова abcdeиacbde- смежные (подстановкаbc-cb). Словаabcde-cadbeэквивалентны.

Может быть рассмотрен специальный вид ассоциативного исчисления, в котором подстановки являются ориентированными: N → М (стрелка означает, что подстановку разрешается производить лишь слева направо). Для каждого ассоциативного исчисления существует задача: для любых двух слов определить, являются ли они эквивалентными или нет.

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

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

Пример

Алфавит: Система подстановок В:

А = {а, b, с}cb - cc

сса - аb

ab – bса

Предписание о применении подстановок: в произвольном слове Рнадо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.

Так, применяя систему подстановок Виз рассмотренного примера к словамbabaacиbсaсаbсполучаем:

babaac→bbcaaac→ остановка

bcacabc → bcacbcac→bcacccac→bсасаbс→ бесконечные процесс (остановки нет), так как мы получили исходное слово.

Предложенный А.А.Марковым способ уточнения понятия алгоритма основан на понятии нормального алгоритма, который определяется следующим образом. Пусть задан алфавит Аи система подстановокВ.Для произвольного словаР подстановки изВподбираются в том же порядке, в каком они следуют вВ..Если подходящей подстановки нет, то процесс останавливается. В противном случае берется первая из подходящих подстановок и производится замена ее правой частью первого вхождения ее левой части вР.Затем все действия повторяются для получившегося словаP1. Если применяется последняя подстановка из системыВ, процесс останавливается.

Такой набор предписаний вместе с алфавитом Аи набором подстановокВопределяют нормальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда применена последняя подстановка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.

Приведем пример нормального алгоритма, описывающего сложение -натуральных чисел (представленных наборами единиц).

Пример

Алфавит: Система подстановок В:

А = (+, 1) 1 + → + 1

+ 1 → 1

1 → 1

Слово Р: 11+11+111

Последовательная переработка слова Рс помощью нормального алгоритма Маркова проходит через следующие этапы:

Р = 11 + 11 + 111 Р5= + 1 + 111111

Р1= 1 + 111 + 111 Р6= ++ 1111111

Р2= + 1111 + 111 Р7= + 1111111

Р3= + 111 + 1111 Р8= 1111111

Р4= + 11 + 11111 Р9= 1111111

Нормальный алгоритм Маркова можно рассматривать как универсальную форму задания любого алгоритма. Универсальность нормальных алгоритмов декларируется принципом нормализации: для любого алгоритма в произвольном конечном алфавите Аможно построить эквивалентный ему нормальный алгоритм над алфавитомА,

Разъясним последнее утверждение. В некоторых случаях не удается построить нормальный алгоритм, эквивалентный данному в алфавите А,если использовать в подстановках алгоритма только буквы этого алфавита. Однако, можно построить требуемый нормальный алгоритм, производя расширение алфавитаА(добавляя к нему некоторое число новых букв). В этом случае говорят, что построенный алгоритм является алгоритмом над алфавитомА,хотя он будет применяться лишь к словам в исходном алфавитеA.

Если алгоритм Nзадан в некотором расширении алфавитаА,то говорят, чтоN есть нормальный алгоритм над алфавитомА.

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

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

I. Суперпозиция алгоритмов.При суперпозиции двух алгоритмовАиВвыходное слово первого алгоритма рассматривается как входное слово второго алгоритмаВ. Результат суперпозицииСможет быть представлен в видеС(р)=В(А(р)),

II. Объединение алгоритмов.Объединением алгоритмовАиВв одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое словор,содержащееся в пересечении областей определения алгоритмовАиВ,в записанные рядом словаА(р) и В(р).

III. Разветвление алгоритмов.Разветвление алгоритмов представляет собой композициюDтрех алгоритмовА, В и С,причем область определения алгоритмаD является пересечением областей определения всех трех алгоритмовА, Ви С, а для любого словариз этого пересеченияD(p)=А(р),еслиС(р)=е, D(p)=B(p),еслиС(р) = е,гдее -пустая строка.

IV. Итерация алгоритмов.Итерация (повторение) представляет собой такую композицию С двух алгоритмовАиВ,что для любого входного словарсоответствующее словоС(р)получается в результате последовательного многократного применения алгоритмаАдо тех пор, пока не получится слово, преобразуемое алгоритмомВ.

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

Существует строгое доказательство того, что по возможностям преобразования нормальные алгоритмы Маркова эквивалентны машинам Тьюринга.

studfiles.net

Майер Р.В. Задачи, алгоритмы, программы

АЛГОРИФМЫ МАРКОВА

Задача 1.

Напишите программу, позволяющую автоматически реализовать нормальный алгоритм Маркова, обрабатывающий входное слово с помощью системы подстановок. Например, дано слово из алфавита {a,b,c,d}, следует расположить буквы в алфавитном порядке.

Нормальная система подстановок осуществляется так: сначала выполняется первая подстановка (x[1] заменяется на y[1]), слово переписывается. Затем - снова первая подстановка; если невозможно - вторая; если вторая не проходит, то третья. Слово переписывается. Снова первая подстановка, если невозможно - вторая; если невозможно - третья. Слово переписывается. Система подстановок, позволяющая расположить буквы в алфавитном порядка, представлена ниже:

slovo:='dabadbcadcbd'; ------------ x[1]:='ba'; y[1]:='ab'; x[2]:='ca'; y[2]:='ac'; x[3]:='da'; y[3]:='ad'; x[4]:='cb'; y[4]:='bc'; x[5]:='db'; y[5]:='bd'; x[6]:='dc'; y[6]:='cd';

Для автоматического выполнения нормальногой алгоритм Маркова используется программа ПР-1. Результат работы программы - на рис. 1.

1 daabdbcadcbd | подстановка 1 2 daabdbacdcbd | подстановка 2 3 daabdabcdcbd | подстановка 1 4 adabdabcdcbd | подстановка 3 5 aadbdabcdcbd | подстановка 3 6 aadbadbcdcbd | подстановка 3 7 aadabdbcdcbd | подстановка 1 8 aaadbdbcdcbd | подстановка 3 9 aaadbdbcdbcd | подстановка 4 10 aaabddbcdbcd | подстановка 5 11 aaabdbdcdbcd | подстановка 5 12 aaabbddcdbcd | подстановка 5 13 aaabbddcbdcd | подстановка 5 14 aaabbddbcdcd | подстановка 4 15 aaabbdbdcdcd | подстановка 5 16 aaabbbddcdcd | подстановка 5 17 aaabbbdcddcd | подстановка 6 18 aaabbbcdddcd | подстановка 6 19 aaabbbcddcdd | подстановка 6 20 aaabbbcdcddd | подстановка 6 21 aaabbbccdddd | подстановка 6

Рис. 1. Перестановка букв по алфавиту

Задача 2.

Дана последовательность скобок. С помощью нормальной системы подстановок Маркова определите правильность скобочной структуры.

Чтобы реализовать нормальную систему подстановок Маркова, в программу ПР-1 следует вставить код:

slovo:='()()(())(()())(())'; -------------- x[1]:='**'; y[1]:='*'; x[2]:='()*'; y[2]:='*'; x[3]:='*()'; y[3]:='*'; x[4]:='(*)'; y[4]:='*'; x[5]:='()'; y[5]:='*';

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

1 *()(())(()())(()) | подстановка 5 2 *(())(()())(()) | подстановка 3 3 *(*)(()())(()) | подстановка 5 4 **(()())(()) | подстановка 4 5 *(()())(()) | подстановка 1 6 *(*())(()) | подстановка 5 7 *(*)(()) | подстановка 3 8 **(()) | подстановка 4 9 *(()) | подстановка 1 10 *(*) | подстановка 5 11 ** | подстановка 4 12 * | подстановка 1

Рис. 2. Определение правильности скобочной структуры.

Задача 3.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, переводящий число из двоичной системы счисления в унарную.

Чтобы решить эту задачу, в программу ПР-1 следует вставить код:

slovo:='10011'; ---------- x[1]:='|0'; y[1]:='0||'; x[2]:='1'; y[2]:='0|'; x[3]:='0|'; y[3]:='|';

Результат решения задачи -- на рис. 3.

1 0|0011 | подстановка 2 2 00||011 | подстановка 1 3 00|0||11 | подстановка 1 4 000||||11 | подстановка 1 5 000||||0|1 | подстановка 2 6 000|||0|||1 | подстановка 1 7 000||0|||||1 | подстановка 1 8 000|0|||||||1 | подстановка 1 9 0000|||||||||1 | подстановка 1 10 0000|||||||||0| | подстановка 2 11 0000||||||||0||| | подстановка 1 12 0000|||||||0||||| | подстановка 1 13 0000||||||0||||||| | подстановка 1 14 0000|||||0||||||||| | подстановка 1 15 0000||||0||||||||||| | подстановка 1 16 0000|||0||||||||||||| | подстановка 1 17 0000||0||||||||||||||| | подстановка 1 18 0000|0||||||||||||||||| | подстановка 1 19 00000||||||||||||||||||| | подстановка 1 20 0000||||||||||||||||||| | подстановка 3 21 000||||||||||||||||||| | подстановка 3 22 00||||||||||||||||||| | подстановка 3 23 0||||||||||||||||||| | подстановка 3 24 ||||||||||||||||||| | подстановка 3

Рис. 3. Перевод числа из двоичной системы в унарную

Задача 4.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, складывающий два числа.

В программу ПР-1 следует вставить код:

slovo:='8eight+5five'; ------------- x[1]:='1one'; y[1]:='|'; x[2]:='2two'; y[2]:='||'; x[3]:='3three'; y[3]:='|||'; x[4]:='4four'; y[4]:='||||'; x[5]:='5five'; y[5]:='|||||'; x[6]:='6six'; y[6]:='||||||'; x[7]:='7seven'; y[7]:='|||||||'; x[8]:='8eight'; y[8]:='||||||||'; x[9]:='9nine'; y[9]:='|||||||||'; x[10]:='|+|'; y[10]:='||'; x[11]:='||||||||||'; y[11]:='10'; x[12]:='0|||||||||'; y[12]:='9'; x[13]:='0||||||||'; y[13]:='8'; x[14]:='0|||||||'; y[14]:='7'; x[15]:='0||||||'; y[15]:='6'; x[16]:='0|||||'; y[16]:='5'; x[17]:='0||||'; y[17]:='4'; x[18]:='0|||'; y[18]:='3'; x[19]:='0||'; y[19]:='2'; x[20]:='0|'; y[20]:='1'; x[21]:='|||||||||'; y[21]:='9'; x[22]:='||||||||'; y[22]:='8'; x[23]:='|||||||'; y[23]:='7'; x[24]:='||||||'; y[24]:='6'; x[25]:='|||||'; y[25]:='5'; x[26]:='||||'; y[26]:='4'; x[27]:='|||'; y[27]:='3'; x[28]:='||'; y[28]:='2'; x[29]:='|'; y[29]:='1';

Результат решения задачи - на рис. 4.

slovo:='8eight+5five'; ---------------- 1 8eight+||||| | подстановка 5 2 ||||||||+||||| | подстановка 8 3 ||||||||||||| | подстановка 10 4 10||| | подстановка 11 5 13 | подстановка 18

Рис. 4. Сложение двух чисел

Задача 5.

Напишите программу, автоматически реализующий нормальный алгоритм Маркова, умножающий два числа.

В программу ПР-1 следует вставить код:

slovo:='1111*111'; ---------- x[1]:='*11'; y[1]:='A*1'; x[2]:='*1'; y[2]:='A'; x[3]:='1A'; y[3]:='A1B'; x[4]:='BA'; y[4]:='AB'; x[5]:='B1'; y[5]:='1B'; x[6]:='A1'; y[6]:='A'; x[7]:='AB'; y[7]:='B'; x[8]:='B'; y[8]:='1';

Результат работы программы - на рис. 5. Другой пример решения задачи:

slovo:='1111*111'; ----------- x[1]:='1*'; y[1]:='X'; x[2]:='_1'; y[2]:='1_Z'; x[3]:='Z1'; y[3]:='1Z'; x[4]:='1X'; y[4]:='X_'; x[5]:='X'; y[5]:=''; x[6]:='_'; y[6]:=''; x[7]:='Z'; y[7]:='1';
slovo:='1111*111'; ------------- 1 1111A*11 | подстановка 1 2 1111AA*1 | подстановка 1 3 1111AAA | подстановка 2 4 111A1BAA | подстановка 3 5 11A1B1BAA | подстановка 3 6 1A1B1B1BAA | подстановка 3 7 A1B1B1B1BAA | подстановка 3 8 A1B1B1B1ABA | подстановка 4 9 A1B1B1BA1BBA | подстановка 3 10 A1B1B1AB1BBA | подстановка 4 11 A1B1BA1BB1BBA | подстановка 3 12 A1B1AB1BB1BBA | подстановка 4 13 A1BA1BB1BB1BBA | подстановка 3 14 A1AB1BB1BB1BBA | подстановка 4 15 AA1BB1BB1BB1BBA | подстановка 3 16 AA1BB1BB1BB1BAB | подстановка 4 17 AA1BB1BB1BB1ABB | подстановка 4 18 AA1BB1BB1BBA1BBB | подстановка 3 ............................... 56 1111BBBBBBBB | подстановка 8 57 11111BBBBBBB | подстановка 8 58 111111BBBBBB | подстановка 8 59 1111111BBBBB | подстановка 8 60 11111111BBBB | подстановка 8 61 111111111BBB | подстановка 8 62 1111111111BB | подстановка 8 63 11111111111B | подстановка 8 64 111111111111 | подстановка 8

Рис. 5. Умножение целых чисел

Задача 6.

Имеется число в четверичной системе счисления. Предложите систему нормальных подстановок, которая переводит это число в двоичную систему счисления. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*3021032'; ------------ x[1]:='*0'; y[1]:='00*'; x[2]:='*1'; y[2]:='01*'; x[3]:='*2'; y[3]:='10*'; x[4]:='*3'; y[4]:='11*'; x[5]:='*'; y[5]:=' ';
Задача 7.

Дано двоичное число. Предложите систему нормальных подстановок, которая инвертирует все 0 и 1. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*011010101'; ----------- x[1]:='*0'; y[1]:='1*'; x[2]:='*1'; y[2]:='0*'; x[3]:='*'; y[3]:=' ';
Задача 8.

Дано число в унарной системе счисления от 1 до 15. Предложите систему нормальных подстановок, которая представляет его как сумму степеней числа 2. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='|||||||||||||_'; ------------- x[1]:='||||||||'; y[1]:='8+'; x[2]:='||||'; y[2]:='4+'; x[3]:='||'; y[3]:='2+'; x[4]:='|'; y[4]:='1+'; x[5]:='+_'; y[5]:=' ';
Задача 9.

Имеется слово 'BAB_BA_AA_BABB_ABA'. Создайте нормальный алгоритм Маркова, который символы 'A' переносит влево, символы 'B' - вправо, а пробелы оставляет посередине. Промоделируйте на компьютере. (Ответ: 1) 'BA' => 'AB'; 2) 'B_' => '_B'; 3) '_A' => 'A_').

Задача 10.

Имеется слово 'abcbacbdacdb'. Создайте нормальный алгоритм Маркова, который кодирует это слово. Промоделируйте на компьютере. (Ответ: 1) 'a' => '00-'; 2) 'b' => '01-'; 3) 'c' => '10-'; 4) 'd' => '11-'; 5) 'e' => '111-').

Тексты программ находятся в zip-архиве, файл gl-15.pas.

ВВЕРХ

Майер, Р. В. Задачи, алгоритмы, программы / Р. В. Майер [Электронный ресурс]. - Глазов: ГГПИ, 2012 // Web-site http://maier-rv.glazov.net .

komp-model.narod.ru


 

..:::Новинки:::..

Windows Commander 5.11 Свежая версия.

Новая версия
IrfanView 3.75 (рус)

Обновление текстового редактора TextEd, уже 1.75a

System mechanic 3.7f
Новая версия

Обновление плагинов для WC, смотрим :-)

Весь Winamp
Посетите новый сайт.

WinRaR 3.00
Релиз уже здесь

PowerDesk 4.0 free
Просто - напросто сильный upgrade проводника.

..:::Счетчики:::..