Самостоятельная работа по векторам. Нам, также марковский алгоритм
![]()
|
Норма́льный алгори́тм (алгори́фм) Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ. Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ — полный по Тьюрингу язык, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал. Описание Нормальные алгоритмы вербальны, то есть предназначены для применения к словам в различных алфавитах. Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам, из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида {\displaystyle L\to D} ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Примером схемы нормального алгоритма в пятибуквенном алфавите {\displaystyle |*abc} ![]() {\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.} ![]() Процесс применения нормального алгоритма к произвольному слову {\displaystyle V} ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Например, в ходе процесса применения алгорифма с указанной выше схемой к слову {\displaystyle |*||} ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации». Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал. Использование алгоритма Маркова для преобразований над строками. Алфавит: { а…я, А…Я, «пробел», «точка» } Правила: А → апельсин кг → килограмм М → магазинчике Т → том магазинчике →. ларьке (заключительная формула) в том ларьке → на том рынке Исходная строка: Я купил кг Аов в Т М. При выполнении алгоритма строка претерпевает следующие изменения: Я купил кг апельсинов в Т М. Я купил килограмм апельсинов в Т М. Я купил килограмм апельсинов в Т магазинчике. Я купил килограмм апельсинов в том магазинчике. Я купил килограмм апельсинов в том ларьке. На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной). |