imported>MBH: отмена правки 145587927 участника 188.65.247.234 (обс.)

2026-01-23T10:14:04Z

отмена правки 145587927 участника 188.65.247.234 (обс.)

Новая страница

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

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

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

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

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

<math>\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.</math>

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

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

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

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

== Примеры ==

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

'''Алфавит:'''
: { а…я, А…Я, «пробел», «точка» }

'''Правила:'''
# А → апельсин
# кг → килограмм
# М → магазинчике
# Т → том
# магазинчике →. ларьке ''(заключительная формула)''
# в том ларьке → на том рынке

'''Исходная строка:'''
: Я купил кг Аов в Т М.

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

# Я купил кг апельсинов в Т М.
# Я купил килограмм апельсинов в Т М.
# Я купил килограмм апельсинов в Т магазинчике.
# Я купил килограмм апельсинов в том магазинчике.
# Я купил килограмм апельсинов в том ларьке.

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

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

'''Алфавит:'''
: { 0, 1, | }

'''Правила:'''
# 1 → 0|
# |0 → 0||
# 0 → "" (пустая строка)

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

'''Выполнение:'''
# 0|01
# 0|00|
# 00||0|
# 00|0|||
# 000|||||
# 00|||||
# 0|||||
# |||||

== Ссылки ==
* [https://yad-studio.github.io/ Yad Studio — IDE и интерпретатор для Нормальных Алгоритмов Маркова (Open Source)]
* [http://matinf.vsgao.com/simulator/na.html Javascript-эмулятор нормальных алгорифмов Маркова (работает on-line)]
{{вс}}

{{плохое оформление|дата=2021-06-29}}
{{переработать|дата=2011-08-05}}

[[Категория:Алгоритмы]]
[[Категория:Модели вычислений]]

Нормальный алгоритм - История изменений

imported>MBH: отмена правки 145587927 участника 188.65.247.234 (обс.)