Нормальные алгоритмы маркова кратко
Обновлено: 02.07.2024
Норма́льный алгори́тм Ма́ркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 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
Использование алгоритма Маркова для преобразований над строками:
- "А" → "апельсин"
- "кг" → "килограмм"
- "М" → "магазинчике"
- "Т" → "том"
- "магазинчике" → ·"ларьке" (заметьте, это заключительная формула!)
- "в том ларьке" → "на том рынке"
Исходная строка:
"Я купил кг Аов в Т М."
При выполнении алгоритма строка претерпевает следующие изменения:
- "Я купил кг апельсинов в Т М."
- "Я купил килограмм апельсинов в Т М."
- "Я купил килограмм апельсинов в Т магазинчике."
- "Я купил килограмм апельсинов в том магазинчике."
- "Я купил килограмм апельсинов в том ларьке."
На этом выполнение алгоритма завершится (так как будет достигнута формула №5, которую мы сделали заключительной).
Пример 2
Теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории) была разработана советским математиком А. А. Марковым (1903–1979) в конце 1940-х — начале 1950-х гг. XX в. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите.
Марковские подстановки
Алфавитом (как и прежде) называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Пустое слово будем обозначать , то алфавит (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе. Например, если . Слово является подсловом слова , а — подсловом и , причем в оно входит дважды. Особый интерес представляет первое вхождение.
Определение 34.1. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов , состоящая в следующем. В заданном слове (если таковое имеется) и, не изменяя остальных частей слова . Полученное слово называется результатом применения марковской подстановки к слову в слово в неприменима к слову
Пример 34.2. Примеры марковских подстановок рассмотрены в таблице, в каждой строке которой сначала дается преобразуемое слово, затем применяемая к нему марковская подстановка и, наконец, получающееся в результате словно:
Для обозначения марковской подстановки используется запись . Она называется формулой подстановки . Некоторые подстановки будем называть заключительными (смысл названия станет ясен чуть позже). Для обозначения таких подстановок будем использовать запись , называя ее формулой заключительной подстановки. Слово называется левой частью, а — правой частью в формуле подстановки.
Нормальные алгоритмы и их применение к словам
Упорядоченный конечный список формул подстановок
в алфавите Определение 34.3. Нормальным алгоритмом (Маркова) в алфавите слов в алфавите последовательности берется слово слово построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в , то полагают Равным , и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частями, входящими в , то в качестве берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово ; процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки) и продолжающимся — в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову будем записывать следующим образом:
Мы определили понятие нормального алгоритма в алфавите Пример 34.4. Пусть — алфавит. Рассмотрим следующую схему нормального алгоритма в
Нетрудно понять, как работает определяемый этой схемой нормальный алгоритм. Всякое слово , он перерабатывает в слово, получающееся из
Пример 34.5. Пусть — алфавит. Рассмотрим схему
Она определяет нормальный алгоритм, перерабатывающий всякое слово (в алфавите
Нормально вычислимые функции и принцип нормализации Маркова
Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам. В свою очередь, мы предписываем им такие правила, результаты применения которых мы можем интерпретировать как вычисления. Рассмотрим два примера.
Пример 34.6. В алфавите схема (все такие слова суть следующие: и т.д.) приписывает слева 1. Следовательно, алгоритм реализует (вычисляет) функцию .
Пример34.7. Дана функция где со следующей схемой:
Этот алгоритм работает по такому принципу: пока число букв 1 а слове не меньше 3, алгоритм последовательно стирает по три буквы. Если число букв меньше 3, но больше 0, то оставшиеся буквы 1 или 11 стираются заключительно; если слово пусто, оно заключительно переводится в слово 1. Например:
Таким образом, рассмотренный алгоритм реализует (или вычисляет) данную функцию.
Сформулируем теперь точное определение такой вычислимости функций.
Определение 34.8. Функция , заданная на некотором множестве слов алфавита и такой нормальный алгоритм в этот алгоритм перерабатывает в слово .
Таким образом, нормальные алгоритмы примеров 34.6 и 34.7 показывают, что функции и нормально вычислимы. Причем соответствующие нормальные алгоритмы удалось построить в том же самом алфавите . Следующий пример демонстрирует нормальный алгоритм в расширенном алфавите, вычисляющий данную функцию.
Пример 34.9. Построим нормальный алгоритм для вычисления Функции не в одноичной системе (как сделано в примере 34.6), а в десятичной. В качестве алфавита возьмем перечень арабских цифр , а нормальный алгоритм будем строить в его расширении . Вот схема этого нормального алгоритма (читается по столбцам):
Попытаемся применить алгоритм к пустому слову
Это означает, что к пустому слову данный алгоритм не применим.
Если применить теперь алгоритм к слову 499, получим следующую последовательность слов: (применена формула из середины первого столбца).
Таким образом, слово 499 перерабатывается данным нормальным алгоритмом в слово 500. Предлагается проверить, что .
В рассмотренном примере нормальный алгоритм построен в алфавите (т.е. и ), но данный алгоритм слова в алфавите перерабатывает снова в слова в алфавите "Принцип нормализации Маркова" . Согласно этому принципу, для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима.
Сформулированный принцип, как и тезисы Тьюринга и Чёрча, носит внематематический характер и не может быть строго доказан. Он выдвинут на основании математического и практического опыта.
Все, что в предыдущих параграфах было сказано о тезисах Тьюринга и Чёрча, можно с полным правом отнести к принципу нормализации Маркова. Косвенным подтверждением этого принципа служат теоремы следующего пункта, устанавливающие эквивалентность и этой теории алгоритмов теориям машин Тьюринга и рекурсивных функций.
Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу
Это совпадение будет означать, что понятие нормально вычислимой функции равносильно понятию функции, вычислимой по Тьюрингу, а вместе с ним и понятию частично рекурсивной функции.
Теорема 34.10. Всякая функция, вычислимая по Тьюрингу, будет также и нормально вычислимой.
Пусть машина Тьюринга с внешним алфавитом и алфавитом внутренних состояний вычисляет некоторую функцию , заданную и принимающую значения в множестве слов алфавита представить в виде совокупности марковских подстановок. Конфигурации, возникающие в машине Тьюринга в процессе ее работы, представляют собой слова в алфавите . Эти слова имеют вид: . Нам понадобится различать начало слова и его конец (или его левый и правый концы). Для этого к алфавиту добавим еще два символа (не входящие ни в ): . Эти символы будем ставить соответственно в начало и конец каждого машинного слова . Это означает, что машинное слово . Посмотрим, какой совокупностью марковских подстановок можно заменить данную команду в каждом из следующих трех случаев:
а) , т.е. команда имеет вид: . Ясно, что в этом случае следующее слово получается из слова , которую мы и будем считать соответствующей команде ;
б) . Нетрудно понять, что в этом случае для получения из слова
которая применима к слову — самая левая буква в слове . В этом случае аналогично, чтобы получить из слова
которая применима к слову входит в слово Теорема 34.11. Всякая нормально вычислимая функция вычислима по Тьюрингу.
Эквивалентность различных теорий алгоритмов
Итак, в двух последних параграфах мы познакомились с тремя теориями, каждая из которых уточняет понятие алгоритма, и доказали, что все эти теории равносильны между собой. Другими словами, они описывают один и тот же класс функций, т. е. справедлива следующая теорема.
Теорема 34.12. Следующие классы функций <заданных на натуральных числах и принимающих натуральные значения) совпадают:
а) класс всех функций, вычислимых по Тьюрингу;
б) класс всех частично рекурсивных функций;
в) класс всех нормально вычислимых функций.
Полезно уяснить смысл и значение этого важного результата. В разное время в разных странах ученые независимо друг от друга, изучая интуитивное понятие алгоритма и алгоритмической вычислимости, создали теории, описывающие данное понятие, которые оказались равносильными. Этот факт служит мощным косвенным подтверждением адекватности этих теорий опыту вычислений, справедливости каждого из тезисов Тьюринга, Чёрча и Маркова. В самом деле, ведь если бы один из этих классов оказался шире какого-либо другого класса, то соответствующий тезис Тьюринга, Чёрча или Маркова был бы опровергнут. Например, если бы класс нормально вычислимых функций оказался шире класса рекурсивных функций, то существовала бы нормально вычислимая, но не рекурсивная функция. В силу ее нормальной вычислимости она была бы алгоритмически вычислима в интуитивном понимании алгоритма, и предположение о ее нерекурсивности опровергало бы тезис Чёрча. Но классы Тьюринга, Чёрча и Маркова совпадают, и таких функций не существует. Это и служит еще одним косвенным подтверждением тезисов Тьюринга, Маркова и Чёрча.
Можно отметить, что существуют еще и другие теории алгоритмов, и для всех них также доказана их равносильность с рассмотренными теориями.
Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.
Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.
Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.
Зададим в некотором алфавите конечную систему подстановок N - М, S - Т. где N, М, S, Т. - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.
Например, в алфавите А = имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb.
Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.
Слова P1 и Р2 в некотором ассоциативном исчислении называются смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки.
Последовательность слов Р, P1, Р2, . М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное.
Слова Р и М называют эквивалентными, если существует цепочка от Р к М и обратно.
ad - da; eca - ae
bc - cb; eda - be
bd - db; edb - be
Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde - cadbe эквивалентны.
Может быть рассмотрен специальный вид ассоциативного исчисления, в котором подстановки являются ориентированными: N → М (стрелка означает, что подстановку разрешается производить лишь слева направо). Для каждого ассоциативного исчисления существует задача: для любых двух слов определить, являются ли они эквивалентными или нет.
Любой процесс вывода формул, математические выкладки и преобразования также являются дедуктивными цепочками в некотором ассоциативном исчислении. Построение ассоциативных исчислений является универсальным методом детерминированной переработки информации и позволяет формализовать понятие алгоритма.
Введем понятие алгоритма на основе ассоциативного исчисления: алгоритмом в алфавите А называется понятное точное предписание, определяющее процесс над словами из А и допускающее любое слово в качестве исходного. Алгоритм в алфавите А задается в виде системы допустимых подстановок, дополненной точным предписанием о том, в каком порядке нужно применять допустимые подстановки и когда наступает остановка.
Алфавит: Система подстановок В:
Предписание о применении подстановок: в произвольном слове Р надо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.
Так, применяя систему подстановок В из рассмотренного примера к словам babaac и bсaсаbс получаем:
babaac → bbcaaac → остановка
bcacabc → bcacbcac → bcacccac → bсасаbс → бесконечные процесс (остановки нет), так как мы получили исходное слово.
Предложенный А.А.Марковым способ уточнения понятия алгоритма основан на понятии нормального алгоритма, который определяется следующим образом. Пусть задан алфавит А и система подстановок В. Для произвольного слова Р подстановки из В подбираются в том же порядке, в каком они следуют в В. .Если подходящей подстановки нет, то процесс останавливается. В противном случае берется первая из подходящих подстановок и производится замена ее правой частью первого вхождения ее левой части в Р. Затем все действия повторяются для получившегося слова P1. Если применяется последняя подстановка из системы В, процесс останавливается.
Такой набор предписаний вместе с алфавитом А и набором подстановок В определяют нормальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда применена последняя подстановка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.
Приведем пример нормального алгоритма, описывающего сложение -натуральных чисел (представленных наборами единиц).
Алфавит: Система подстановок В:
Слово Р: 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. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.
Существует строгое доказательство того, что по возможностям преобразования нормальные алгоритмы Маркова эквивалентны машинам Тьюринга.
Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.
Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.
Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.
Зададим в некотором алфавите конечную систему подстановок N - М, S - Т. где N, М, S, Т. - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.
Например, в алфавите А = имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb.
Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.
Слова P1 и Р2 в некотором ассоциативном исчислении называются смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки.
Последовательность слов Р, P1, Р2, . М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное.
Слова Р и М называют эквивалентными, если существует цепочка от Р к М и обратно.
ad - da; eca - ae
bc - cb; eda - be
bd - db; edb - be
Слова abcde и acbde - смежные (подстановка bc - cb). Слова abcde - cadbe эквивалентны.
Может быть рассмотрен специальный вид ассоциативного исчисления, в котором подстановки являются ориентированными: N → М (стрелка означает, что подстановку разрешается производить лишь слева направо). Для каждого ассоциативного исчисления существует задача: для любых двух слов определить, являются ли они эквивалентными или нет.
Любой процесс вывода формул, математические выкладки и преобразования также являются дедуктивными цепочками в некотором ассоциативном исчислении. Построение ассоциативных исчислений является универсальным методом детерминированной переработки информации и позволяет формализовать понятие алгоритма.
Введем понятие алгоритма на основе ассоциативного исчисления: алгоритмом в алфавите А называется понятное точное предписание, определяющее процесс над словами из А и допускающее любое слово в качестве исходного. Алгоритм в алфавите А задается в виде системы допустимых подстановок, дополненной точным предписанием о том, в каком порядке нужно применять допустимые подстановки и когда наступает остановка.
Алфавит: Система подстановок В:
Предписание о применении подстановок: в произвольном слове Р надо сделать возможные подстановки, заменив левую часть подстановок на правую; повторить процесс с вновь полученным словом.
Так, применяя систему подстановок В из рассмотренного примера к словам babaac и bсaсаbс получаем:
babaac → bbcaaac → остановка
bcacabc → bcacbcac → bcacccac → bсасаbс → бесконечные процесс (остановки нет), так как мы получили исходное слово.
Предложенный А.А.Марковым способ уточнения понятия алгоритма основан на понятии нормального алгоритма, который определяется следующим образом. Пусть задан алфавит А и система подстановок В. Для произвольного слова Р подстановки из В подбираются в том же порядке, в каком они следуют в В. .Если подходящей подстановки нет, то процесс останавливается. В противном случае берется первая из подходящих подстановок и производится замена ее правой частью первого вхождения ее левой части в Р. Затем все действия повторяются для получившегося слова P1. Если применяется последняя подстановка из системы В, процесс останавливается.
Такой набор предписаний вместе с алфавитом А и набором подстановок В определяют нормальный алгоритм. Процесс останавливается только в двух случаях: 1) когда подходящая подстановка не найдена; 2) когда применена последняя подстановка из их набора. Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами подстановок.
Приведем пример нормального алгоритма, описывающего сложение -натуральных чисел (представленных наборами единиц).
Алфавит: Система подстановок В:
Слово Р: 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. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
Нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта. Это один из немногих языков, разработанных в России и получивших известность во всем мире.
Существует строгое доказательство того, что по возможностям преобразования нормальные алгоритмы Маркова эквивалентны машинам Тьюринга.
Нормальные алгоритмы Маркова — это стандартный метод формализованного определения понятия алгоритма.
Теоретические основы нормальных алгоритмов были сформулированы видным математиком Советского Союза А.А. Марковым в конце сороковых годов двадцатого века. Они явились некоторыми базовыми правилами по обработке словесных символов в каких-либо алфавитах, то есть начальными информационными данными и итоговыми результатами таких алгоритмов выступали буквы некоторого алфавита.
Подстановки Маркова
Под алфавитом понимается любые непустые множества. Компоненты алфавита именуются буквами, а все последовательные буквенные наборы считаются словами данного алфавита. При этом могут существовать и пустые слова, то есть не имеющие букв в своём составе. Пустые слова обозначаются символом Ʌ. Если A и B являются двумя алфавитами, и при этом алфавит A принадлежит алфавиту B, то алфавит B выступает как расширение алфавита A. Выполнять обозначение слов принято при помощи латинских букв: P, Q, R. Все слова могут являться составными частями других слов. В этом варианте первое слово считается подсловом второго слова или его вхождением. К примеру, если А является русскоязычным алфавитом, то рассмотрим следующие слова $P_1$= paragraph, $P_2$ = graf, $P_3$ = ra. Слово $P_2$ считается подсловом $P_1$, а $P_3$ это подслово $P_1$ и $P_2$, при этом в $P_1$ присутствует двойное вхождение.
Подстановкой Маркова является процедура над словами, которая выполняется при помощи двух упорядоченных слов (P, Q), и состоит в таких действиях. В выбранном слове R определяется первое вхождение слова P (при наличии такого) и, без коррекции других фрагментов слова R, подменяют в нём данное вхождение словом Q. Сформированное в итоге слово является результатом использования подстановки Маркова (P, Q) к слову R. В случае отсутствия первого вхождения P в слово R, то есть вхождения полностью отсутствуют, то это означает неприменимость подстановки Маркова (P, Q) к слову R.
Частным случаем подстановок Маркова считаются подстановки с использованием пустых слов:
Ниже в таблице приведены примеры подстановок Маркова, во всех строках которой вначале приведено слово, подлежащее преобразованию, далее применимая к этому слову подстановка Маркова и в конце сформированное в итоге слово:
Рисунок 1. Примеры подстановок Маркова. Автор24 — интернет-биржа студенческих работ
Готовые работы на аналогичную тему
Чтобы обозначить Марковскую подстановку (P, Q), применяется запись P → Q. Она носит название формулы подстановки (P, Q). Отдельные подстановки (P, Q) называются заключительными. Чтобы обозначить такие подстановки применяется запись P → Q, которая называется формулой заключительной подстановки. Слово P является левой частью, а слово Q считается правой частью в формуле подстановки.
Нормальные алгоритмы Маркова
Финальный перечень формул подстановок после упорядочения представлен ниже:
Данный упорядоченный конечный перечень формул подстановок в алфавите A именуется записью нормального алгоритма в A. Точка, взятая в скобки, показывает, что её в этом месте может и не быть. Приведённая схема даёт определение алгоритма преобразования слов, который называется нормальным алгоритмом Маркова. Сформулируем более точное понимание нормального алгоритма Маркова.
Нормальным алгоритмом Маркова в алфавите А является определённый закон формирования очерёдности слов Vi в алфавите A, на основании заданного слова V в выбранном алфавите. Начальным словом V0 очерёдности слов назначается слово V. Предположим, что некоторого значения i ≥ 0 слово Vi сформировано, и процедура реализации данной последовательности пока не завершена. В случае отсутствия в схеме нормального алгоритма формул, у которых левая часть вошла бы в Vi, то Vi+1 считается равным Vi, что даёт право считать процедуру формирования последовательности завершённой. Но когда в схеме присутствуют формулы, у которых левые части входят в Vi, то за значение Vi+1 принимается итог подстановки Маркова правой части начальной в этих формулах, замещая первое вхождение её левой части в слово. Процедура формирования последовательности может считаться завершённой, когда в текущем шаге использовалась формула финальной подстановки, в противном случае процесс продолжает выполняться. В случае обрыва процедуры формирования упомянутой последовательности, то считается, что текущий нормальный алгоритм можно применить к слову V. Оконечный элемент W последовательности является итогом использования нормального алгоритма к слову V. То есть, по сути, при помощи нормального алгоритма перерабатывается V в W.
Последовательность Vi записывается в таком порядке:
V0 ⇨ V1 ⇨ V2 ⇨ … ⇨ Vm-1 ⇨ Vm.
Здесь V0 = V, а Vm = W.
Это определение является понятием нормального алгоритма в алфавите A. В случае задания алгоритма в каком-либо алфавитном расширении A, то считается, что он является нормальным алгоритмом над A.
Приведём пример нормального алгоритма. Имеется алфавит A = . Будем рассматривать такую схему нормального алгоритма в A:
Задаваемый данной схемой алгоритм работает следующим образом. Любое слово V в алфавите A, которое содержит даже единственное вхождение буквы a, алгоритм переработает в слово, формирующееся из V путём вычёркивания в нём самого первого вхождения символа a. А если слово является пустым, то алгоритм выполняет его переработку также в пустое. Данный алгоритм не может быть использован со словами, содержащими лишь только букву b. К примеру:
aabab ⇨ abab, ab ⇨ b, aa ⇨ a, bbab ⇨ bbb, baba ⇨ bba.
Аналогично машине Тьюринга, нормальные алгоритмы, по сути, не выполняют отдельных вычислительных операций. Они только осуществляют операции по преобразованию слов, путём замены в них одних букв на другие согласно заложенным в алгоритмы правилам.
Читайте также: