Начальная

Windows Commander

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

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

File managers and best utilites

Нормальные алгоритмы Маркова. Эмулятор алгоритмов маркова


RGR_6

Балтийский Федеральный Университет им.И.Канта

Факультет Высшей Школы Педагогики

Кафедра педагогики и образовательных технологий

Расчетно-графическая работа №6

по дисциплине: «Теоретические основы информатики»

Тема: «Нормальные алгоритмы Маркова и машины Тьюринга»

Вариант №15

Выполнила: студентка 2 курса

направления «Педагогическое образование»

Скобликова Мария

Проверил: Колесников Александр Васильевич, профессор

Калиниград, 2014г

Содержание

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

    1. Определение понятия «Нормальный алгоритм Маркова»…………………..3

    2. Решение задачи с помощью нормальных алгоритмов Маркова………….3-5

  2. Машина Тьюринга

2.1 Математическая модель машины Тьюринга…………………………..........6

    1. Решение задачи с помощью машины Тьюринга…………………..……...6-9

  1. Анализ результатов и выводы…………………………………….………….10

  2. Список используемой литературы……………...............................................11

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

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

Понятие «нормальный алгоритм» было введено в 1947 г. Советским ученым А.А. Марковым в качестве одного из уточнений представления об алгоритме. Он предполагал, что нормальный алгоритм, являясь алгоритмом в некотором алфавите, порождает некоторый детерминированный процесс переработки только одного слова и только в одном алфавите.

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

Нормальный алгоритм Маркова – указание использовать упорядоченный список правил подстановки:

где αi и βi - слова в алфавите Vт.

Слово αi часто называют левой, а βi - правой частью правил.

Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:

k>=1

В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» ( ). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой.

Записать алгоритм в виде НАМ – значит предъявить такой набор формул.

1.2 Решение задачи с помощью нормальных алгоритмов Маркова

Дано:

A={a,b,c}.

Условие:

Если в слове P не менее двух символов, то переставить два первых символа.

Решение:

  1. Построение протокола

*ba .ab

*ab .ba

*ac .ca

*ca .ac

*bc .cb

*cb .bc

** .

*

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

** могут появиться в случае, если слово содержит одну букву, или же первые две буквы одинаковые.

  1. Графическое представление алгоритма

  1. Результаты отладки на эмуляторе

Пусть нам дано входное слова abc, тогда имеем:

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

2. Машина Тьюринга

2.1 Математическая модель машины Тьюринга

Математическая модель машины Тьюринга имеет вид:

Т=<Vt; Q; D; ; ;  ,

где:

VT= {ai; a2; ... an}

- символы внешней памяти;

Q = {qo, qi; q2; ... qm}

- символы внутренней памяти;

D = {П; Л; С}

- символы перемещения головки;

: Q  Vt => Vt

- функция выхода машины Тьюринга;

: Q  Vt => Q

- функция переходов машины Тьюринга.

: Q  Vt => D

- функция перемещения головки машины Тьюринга.

2.2 Решение задачи с помощью машины Тьюринга

Дано:

A={a,b}

Условие:

Удвоить слово P

Решение:

Для того, чтобы обозначить конец слова, введём в данный нам алфавит ещё один символ - c.

1) Построение таблицы

Теку

щее

состо

яние

Символы

a

b

c

#

Комментарий

q0

q0аП

q0 bП

-

q1cЛ

Установка символа «c» в конец слова

q1

q1 аЛ

q1 bЛ

-

q2 #П

Переход обратно к началу слова

q2

q3#П

q4#П

q7 #Л

-

Определяет букву, над которой находится головка

q3

q3аП

q3bП

q3cП

q5 аЛ

Копирование буквы а

q4

q4 аП

q4 bП

q4 cП

q6bЛ

Копирование буквы b

q5

q5 аЛ

q5 bЛ

q5 cЛ

q2 аП

Копирование буквы а

q6

q6 аЛ

q6 bЛ

q6 cЛ

q2 bП

Копирование буквы b

q7

q8 #П

q9#П

-

q11#П

Перенос слова на ячейку вправо

q8

-

-

-

q10аЛ

Перенос слова на ячейку вправо

q9

-

-

-

q10bЛ

Перенос слова на ячейку вправо

q10

-

-

-

q7 #Л

Перенос слова на ячейку вправо

q11

qk aС

qk bС

-

q11 #П

Передвижение головки в начало слова

2) Построение протокола

q0 а q0 аП

q0 b q0 bП

q0 # q1 cЛ

q1 а q1 аЛ

q1 b q1 bЛ

q1 # q2 #П

q2 а q3 #П

q2 b q4 #П

q2 c q7 #Л

q3 а q3 аП

q3 b q3 bП

q3 c q3 cП

q3 # q5 аЛ

q4 а q4 аП

q4 b q4 bП

q4 c q4 cП

q4 # q6 bЛ

q5 а q5 аЛ

q5 b q5 bЛ

q5 c q5 cЛ

q5 # q2 аП

q6 а q6 аЛ

q6 b q6 bЛ

q6 c q6 cЛ

q6 # q2 bП

q7 а q8 #П

q7 b q9 #П

q7 # q11 #П

q8 # q10 аЛ

q9 # q10 bЛ

q10 # q7 #Л

q11a qk a C

q11b qk b C

q11 # q11# П

3) Построение графа

Граф представлен на следующей странице

Пусть нам дана последовательность ab, тогда имеем следующий вычислительный процесс:

  1. Результаты отладки на эмуляторе

Для начала отмечу, что данный эмулятор Машины Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q={q0,q1,…,qM}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние: попав в него, автомат заканчивает работу ( именно поэтому в эмуляторе состояний (q) больше, чем в моих таблице, протоколе, графе).

Пусть нам дано входное слово abba, тогда имеем:

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

3. Анализ результатов и выводы

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

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

Данные средства используются в информатике для уточнения понятия «алгоритм».

  1. Список используемой литературы

  1. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебно-методическое пособие) - М.: МГУ, 2006. – 47 с.

  2. Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.

  3. Сайта К. Полякова «Преподавание, наука и жизнь» [Электронный ресурс]. – Режим доступа: http://kpolyakov.narod.ru/index.htm, свободный. – Загл. с экрана (дата обращения: 15.11.2014).

studfiles.net

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

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

ru-wiki.org

Практикум 1 курса | [email protected]

1 семестр

Алгоритмы и алгоритмические языки

  • Программа
  • Материалы к курсу
  • Обеспечение
  • Варианты заданий по практикуму
  • Варианты контрольных работ

Основная литература

  • Э. З. Любимский, В. В. Мартынюк, Н. П. Трифонов. Программирование. — М.: Наука, 1980.
  • В. Г. Абрамов, Н. П. Трифонов, Г .Н. Трифонова. Введение в язык Паскаль. — М.: Наука, 1988.
  • К. Йенсен, Н. Вирт. Паскаль. Руководство для пользователя — М.: Финансы и статистика, 1989. Версия в формате djvu.
  •  В. Н. Пильщиков, В. Г. Абрамов, А. А. Вылиток, И. В. Горячая. Машина Тьюринга и алгоритмы Маркова. Решение задач (737.94 Кбайт) — М.: МГУ, 2016 ( Издание 2006 г. (541.64 Кбайт))
  • Сборник упражнений по алгоритмическим схемам (МТ и НАМ).
  • В. Н. Пильщиков. Сборник упражнений по языку Паскаль. — М.: 2002.
  • В. П. Иванников, Л. С. Корухова, В. Н. Пильщиков. Письменный экзамен по курсу «Алгоритмы и алгоритмические языки». — М.: 2002.
2 семестр

Архитектура ЭВМ и язык ассемблера

  • Программа
  • Материалы к курсу
  • Обеспечение
    •  MASM 4.0 (82.88 Кбайт). Компилятор MASM 4.0 с библиотекой ввод-вывода, описанной в книге В. Н. Пильщикова «Программирование на языке ассемблера IBM PC».
  • Варианты заданий по практикуму

Основная литература

cmcmsu.info

НОУ ИНТУИТ | Лекция | Нормальные алгоритмы Маркова

Аннотация: Определение нормального алгоритма Маркова и его выполнение. Возможности нормальных алгоритмов Маркова и тезис Маркова. Методика разработки нормальных алгоритмов Маркова.

Определение нормального алгоритма и его выполнение

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

Для определения НАМ вводится произвольный алфавит - конечное непустое множество символов, при помощи которых описывается алгоритм и данные. В алфавит также включается пустой символ, который мы будем обозначать греческой буквой \lambda. Под словом понимается любая последовательность непустых символов алфавита либо пустой символ, который обозначает пустое слово.

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

  1. ab\to bd
  2. db\to ba
  3. bba\to abb
  4. c\to \lambda

В качестве данных алгоритма берется любая непустая строка символов. Работа НАМ состоит из последовательности совершенно однотипных шагов. Шаг работы алгоритма может быть описан следующим образом:

  1. В упорядоченной последовательности подстановок ищем самую первую подстановку, левое слово которой входит в строку данных.
  2. В строке данных ищем самое первое (левое) вхождение левого слова найденной подстановки.
  3. Это вхождение в строке данных заменяем на правое слово найденной подстановки (преобразование данных).

Шаг работы алгоритма повторяется до тех пор, пока

  • либо не возникнет ситуация, когда шаг не сможет быть выполнен из-за того, что ни одна подстановка не подходит ( левое слово любой подстановки уже не входит в строку данных ) - правило остановки ;
  • либо не будет установлено, что процесс подстановок не может остановиться.

В первом случае строка данных, получившаяся при остановке алгоритма, является выходной (результатом) и алгоритм применим к входным данным, а во втором случае алгоритм не применим к входным данным.

Так, определенный выше в примере нормальный алгоритм Маркова преобразует слово cdbacab в слово bbddd следующим образом (над стрелкой преобразования мы пишем номер применяемой подстановки, а в преобразуемой строке подчеркиваем левое слово применяемой подстановки ):

cdbac\underline{ab}\stackrel{1}{\to}
c\underline{db}acbd\stackrel{2}{\to} \underline{c}baacbd\stackrel{4}{\to}
baa\underline{c}bd\stackrel{4}{\to} ba\underline{ab}d\stackrel{1}{\to}
b\underline{ab}dd\stackrel{1}{\to} bbddd,

а при преобразовании слова abbc этот же алгоритм будет неограниченно работать, так как имеет место цикличное повторение данных:

\underline{ab}bc\stackrel{1}{\to} 
b\underline{db}c\stackrel{2}{\to}
\underline{bba}c\stackrel{3}{\to}
\underline{ab}bc\stackrel{1}{\to}\dots

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

Возможности нормальных алгоритмов и тезис Маркова

Прежде всего рассмотрим возможности реализации арифметических операций с помощью нормальных алгоритмов Маркова. Сначала обратим внимание на одно обстоятельство, связанное с работой любого НАМ: нужно либо вводить дополнительное правило остановки работы нормального алгоритма (иначе в примере увеличения числа на 1 алгоритм продолжит работу и снова будет увеличивать полученный результат еще на 1 и т.д. неограниченное число раз), либо перед началом работы нормального алгоритма добавлять к входной строке специальные символы, отличные от других символов строки, которые учитываются подстановками алгоритма в начале его работы и которые удаляются в конце работы алгоритма. Мы будем придерживаться второго способа, как и одна из наиболее успешных реализаций нормальных алгоритмов Маркова в виде языка программирования Рефал. В качестве добавляемого символа возьмем символ "@".

Пример 1. Рассмотрим простейшую операцию увеличения десятичного числа на 1. В этом случае почти всегда необходимо увеличить последнюю цифру на 1, а последняя цифра отличается тем, что после нее идет символ "@". Поэтому первыми подстановками должны быть подстановки типа

\mbox{<цифра> }@\ \to\ \mbox{ <цифра + 1>}.

Но если это цифра 9, то ее нужно заменить 0 и увеличение на 1 перенести в предыдущий разряд. Этому отвечает подстановка

9@\ \to\ @0.

Наконец, если число начинается с 9 и перед этой цифрой нужно поставить 1, то этому будет отвечать подстановка

@@\ \to\ 1,

а если это не так, то в конце работы алгоритма символы @ надо стереть, что выполнит подстановка

@\ \to\ \lambda.

Таким образом, мы получаем следующий НАМ увеличения десятичного числа на 1:

1.\text{ } 0@ \to 1 \qquad \ 9.\ 8@\to 9\\
2.\text{ } 1@ \to 2 \qquad 10.\ 9@ \to @0\\
3.\text{ } 2@ \to 3 \qquad 11.\ @@ \to 1\\
\text{ } ............... \qquad 12.\ @\to \lambda

Приведем работу построенного алгоритма для чисел 79 и 99:

@7\underline{9@}\stackrel{10}{\to}@\underline{7@}0\stackrel{8}{\to} \underline{@}80\stackrel{12}{\to}80,\\
@9\underline{9@}\stackrel{10}{\to}@\underline{9@}0\stackrel{10}{\to} \underline{@@}00\stackrel{11}{\to}100.

Аналогичным образом разрабатывается нормальный алгоритм Маркова для уменьшения числа на 1 (см. упражнение 1.3.1).

Пример 2. Прежде, чем перейти к другим арифметическим операциям, рассмотрим как довольно типичный пример, используемый часто в других алгоритмах, алгоритм копирования двоичного числа. В этом случае прежде всего исходное и скопированное числа разделим символом "*". В разрабатываемом алгоритме мы будем копировать разряды числа по очереди, начиная с младшего, но нужно решить 2 проблемы: как запоминать значение символа, который мы копируем, и как запоминать место копируемого символа. Для решения второй проблемы используем символ "!", которым мы будем определять еще не скопированный разряд числа, после которого и стоит этот символ. Для запоминания значения копируемого разряда мы будем образовывать для значения 0 символ "a", а для значения 1 - символ "b". Меняя путем подстановок эти символы "a" или "b" с последующими, мы будем передвигать разряды "a" или "b" в начало копируемого числа (после "*"), но для того, чтобы пока не происходило копирование следующего разряда справа, мы перед передвижением разряда временно символ "!" заменим на символ "?", а после передвижения сделаем обратную замену. После того как все число окажется скопированным в виде символов "a" и "b", мы заменим эти символы на 0 и 1 соответственно. В результате нормальный алгоритм копирования двоичного числа можно определить следующей последовательностью подстановок:

\begin{displaymath}
\begin{array}{ll}
1.\ 0@\ \to\ 0!*\\
2.\ 1@\ \to\ 1!*\\
\end{array}
\bigg\} \mbox{ начальные пометки копир. разряда и копии числа\qquad\qquad\qquad\qquad\qquad\quad\ }
\end{displaymath}
\begin{displaymath}
\begin{array}{ll}
 3.\ 0!\ \to\ ?0a\\
4.\ 1!\ \to\ ?1b\\
\end{array}
 \bigg\} \mbox{ копирование разряда с заменой пометки разряда\qquad\qquad\qquad\qquad\qquad\quad\ }
\end{displaymath}
\begin{displaymath}
\begin{array}{ll}
5.\ a0\ \to\ 0a\\
6.\ a1\ \to\ 1a\\
7.\ b0\ \to\ 0b\\
8.\ b1\ \to\ 1b\\
\end{array}
\Bigg\} \mbox{\ передвижение скопированного разряда\qquad\qquad\qquad\qquad\qquad\quad\ }
\end{displaymath}
\begin{displaymath}
\begin{array}{ll}
 9.\ a*\ \to\ *a\\
10.\ b*\ \to\ *b\\
\end{array}
\bigg\} \mbox{\ остановка передвижения скопированного
разряда\qquad\qquad\qquad\qquad\qquad\quad\ }
\end{displaymath}
\begin{displaymath}
\begin{array}{ll}
11.\ ?\ \to\ !
\end{array} \qquad\qquad\mbox{обратная замена пометки
разряда\qquad\quad\qquad\qquad\qquad\qquad\qquad}\\
\end{displaymath}
\begin{displaymath}
\begin{array}{ll}
12.\ a\ \to\ 0\\
13.\ b\ \to\ 1\\
\end{array}
\quad\ \bigg\} \mbox{\ обратная замена скопированного
разряда\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ }
\end{displaymath}
\begin{displaymath}
\begin{array}{ll}
 14.\ @!\ \to\ \lambda\end{array}
\mbox{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad}
\end{displaymath}

Продемонстрируем работу алгоритма для числа 10:

@1\underline{0@}\stackrel{1}{\to} @1\underline{0!}*\stackrel{3}{\to} @1?0\underline{a*}\stackrel{9}{\to} @1\underline{?}0*a\stackrel{11}{\to} @\underline{1!}0*a\stackrel{4}{\to} @?1\underline{b0}*a\stackrel{7}{\to} @?10\underline{b*}a\stackrel{10}{\to} @\underline{?}10*ba\stackrel{11}{\to} @!10*\underline{b}a\stackrel{13}{\to} @!10*1\underline{0}\stackrel{12}{\to} \underline{@!}10*10\stackrel{14}{\to} 10*10

Для построения алгоритма сложения двух чисел можно использовать идею уменьшения одного числа на 1 с последующим увеличением другого числа на 1 и повторением этого до тех пор, пока уменьшаемое число не исчезнет после того, как станет равным 0. Но можно использовать и более сложную идею поразрядного сложения с переносом 1 в разряд слева. Построение этих алгоритмов, а также алгоритмов вычитания, умножения и деления выделено для самостоятельной работы в упражнениях 2 - 9 (см. 1.3).

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

Вместе с тем построение алгоритма в последнем приведенном примере подсказывает следующую методику разработки НАМ:

  1. Произвести декомпозицию (разбиение на части) строящегося алгоритма. В примере это следующие части:
    1. разделение исходного числа и копии;
    2. копирование разряда;
    3. повторение предыдущей части до полного копирования всех разрядов.
  2. Решение проблем реализации каждой части. В примере это следующие проблемы:
    1. запоминание копируемого разряда - разряд 1 запоминается как символ "a", а разряд 0 - как символ "b";
    2. запоминание места копируемого разряда - пометка еще не скопированного символа дополнительным символом "!" с заменой его на символ "?" при передвижении копируемого разряда и обратной заменой после передвижения.
  3. Если часть для реализации является сложной, то она также подвергается декомпозиции.
  4. Сборка реализации в единый алгоритм.

Упражнения

  1. Определите нормальный алгоритм, который уменьшает число на единицу.
  2. Определите нормальный алгоритм сложения двух двоичных чисел методом уменьшения одного числа на 1 и увеличением другого числа на 1 до тех пор, пока уменьшаемое число не станет равным 0.
  3. Определите нормальный алгоритм логического сложения двух двоичных чисел.
  4. Определите нормальный алгоритм логического умножения двух двоичных чисел.
  5. Определите нормальный алгоритм сложения по модулю 2 двух двоичных чисел.
  6. Определите нормальный алгоритм поразрядного сложения двух двоичных чисел.
  7. Определите нормальный алгоритм вычитания двоичных чисел.
  8. Определите нормальный алгоритм умножения двух двоичных чисел столбиком.
  9. Определите нормальный алгоритм деления двух двоичных чисел с определением частного и остатка.
  10. Определите нормальный алгоритм вычисления наибольшего общего делителя двух двоичных чисел.
  11. Определите нормальный алгоритм вычисления наименьшего общего кратного двух двоичных чисел.

www.intuit.ru

Нормальный алгоритм - Gpedia, Your Encyclopedia

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

См. также

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

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

Ссылки

Примечания

www.gpedia.com

definition of Нормальный_алгоритм and synonyms of Нормальный_алгоритм (Russian)

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

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

  Описание

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

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

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

\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 в алфавите этого алгорифма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть V' — слово, полученное на предыдущем шаге работы алгорифма (или исходное слово V, если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в V', то работа алгорифма считается завершённой, и результатом этой работы считается слово V'. Иначе среди формул подстановки, левая часть которых входит в V', выбирается самая первая. Если эта формула подстановки имеет вид L\to\cdot D, то из всех возможных представлений слова V' в виде RLS выбирается такое, при котором R — самое короткое, после чего работа алгорифма считается завершённой с результатом RDS. Если же эта формула подстановки имеет вид L\to D, то из всех возможных представлений слова 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 палочек: |||||.

Алфавит:

{ 0, 1, | }

Правила:

  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. |||||

  См. также

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

  Ссылки

  Примечания

   

dictionary.sensagent.com

Решение задачи с помощью нормальных алгоритмов Маркова

Расчетно-графическая работа №6

по дисциплине: «Теоретические основы информатики»

 

Тема: «Нормальные алгоритмы Маркова и машины Тьюринга»

 

Вариант №15

 

 

Выполнила: студентка 2 курса

направления «Педагогическое образование»

Скобликова Мария

 

Проверил: Колесников Александр Васильевич, профессор

 

 

Калиниград, 2014г

Содержание

 

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

1.1 Определение понятия «Нормальный алгоритм Маркова»…………………..3

1.2 Решение задачи с помощью нормальных алгоритмов Маркова………….3-5

Машина Тьюринга

2.1 Математическая модель машины Тьюринга…………………………..........6

2.2 Решение задачи с помощью машины Тьюринга…………………..……...6-9

3. Анализ результатов и выводы…………………………………….………….10

4. Список используемой литературы……………...............................................11

 

 

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

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

Понятие «нормальный алгоритм» было введено в 1947 г. Советским ученым А.А. Марковым в качестве одного из уточнений представления об алгоритме. Он предполагал, что нормальный алгоритм, являясь алгоритмом в некотором алфавите, порождает некоторый детерминированный процесс переработки только одного слова и только в одном алфавите.

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

Нормальный алгоритм Маркова – указание использовать упорядоченный список правил подстановки:

где αi и βi - слова в алфавите Vт.

Слово αi часто называют левой, а βi - правой частью правил.

 

Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:

 

 

 

 

В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» ( ). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой.

Записать алгоритм в виде НАМ – значит предъявить такой набор формул.

 

Решение задачи с помощью нормальных алгоритмов Маркова

Дано:

A={a,b,c}.

Условие:

Если в слове P не менее двух символов, то переставить два первых символа.

Решение:

1) Построение протокола

*ba .ab

*ab .ba

*ac .ca

*ca .ac

*bc .cb

*cb .bc

** .

*

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

** могут появиться в случае, если слово содержит одну букву, или же первые две буквы одинаковые.

2) Графическое представление алгоритма

 

3) Результаты отладки на эмуляторе

Пусть нам дано входное слова abc, тогда имеем:

 

 

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

Машина Тьюринга

studopedya.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 проводника.

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