Способ композиции нормальных алгоритмов будет суперпозицией если

Содержание

Нормальные алгоритмы Маркова.
Способ композиции нормальных алгоритмов будет суперпозицией если
Способы композиции нормальных алгоритмов:
Рекурсивные функции.

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

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

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

Рассмотрим слова M и N в некотором алфавите А

Если N является частью M, то говорят, что N входит в M.

Зададим в некотором алфавите конечную систему подстановок N – M, S – T, … где N,M,S,T,… — слова в этом алфавите.

Любую подстановку можно применить к некоторому слову K следующим образом:

Если в K имеется одно или несколько вхождений слова N, то любое из них может быть заменено слово M и наоборот.

Пример: A= N = ab M = bcb K = abcbcbab.

Заменить в слове K – N на M: bcbcbcbab или abcbcbbcb

К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д..

Совокупность всех слов в данном алфавите, вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок. Слова P1 и P2 в некотором ассоциативном исчислении называют смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки. Последовательность слов P1, P2,… M называется дедуктивной цепочкой, ведущей от слова P к слову M – дедуктивная цепочка.

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

Может быть рассмотрен специальный вид ассоциативного исчисления, в котором подстановки являются ориентированными. N -> M

Для каждого ассоциативного исчисления существуют задачи.

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

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

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

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

Такой набор предписаний вместе с алфавитом и набором подстановок B, определяют нормальный алгоритм.

Процесс останавливается только в двух случаях:

1) когда подходящая подстановка не найдена;

2) когда применена последняя подстановка из их набора.

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

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

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

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

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

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

Алгоритм называется нормализуемым, если можно построить эквивалентный ему нормальный алгоритм, и не нормализуемым в противном случае.

Принцип нормализации может быть высказан в видоизменённой форме:

Все алгоритмы нормализуемы.

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

Способы композиции нормальных алгоритмов:

1) Суперпозиция алгоритмов. При суперпозиции двух алгоритмов A и B выходное слово первого алгоритма рассматривается как входное слово второго алгоритма. Результат суперпозиции С может быть представлен в виде C(_P) = B(A(_P))

2) Объединение алгоритмов. Объединением алгоритмов A и B в одном и том же алфавите называется алгоритм C, преобразующий любое слово P, содержащееся в пересечении областей определения алгоритма A и B в записанные рядом слова A(_P) и B(_P)

3) Разветвление алгоритмов. Разветвление представляет собой композицию D трёх алгоритмов A,B и C, причём область определения алгоритма D является пересечением областей определения трёх алгоритмов A,B,C.

4) Итерация (повтор). Представляет собой такую композицию C двух алгоритмов A и B, что для любого входного слова P, соответствующего слова C(_P), получается в результате последовательного многократного применения алгоритма A до тех пор, пока не получится слово, образуемое алгоритмом B.

Источник

Способ композиции нормальных алгоритмов будет суперпозицией если

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

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

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

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

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

Например, в алфавите A = <а, b, с>имеются слова N = ab, М = bcb, K = abcbcbab . Заменив в слове K слово N на М , получим bcbcbcbab или abcbcbbcb , и, наоборот, заменив М на N , получим aabcbab или abcabab .

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

Слова P₁ и Р₂ в некотором ассоциативном исчислении называются смежными , если одно из них может быть преобразовано в другое однократным применением допустимой подстановки.Последовательность, слов P, P₁, . M называется дедуктивной цепочкой , ведущей от слова P к слову М , если каждое из двух рядом стоящих слов этой цепочки — смежное.

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

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

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

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

Введем понятие алгоритма на основе ассоциативного исчисления.

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

Система подстановок B :

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

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

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

Такой набор предписаний вместе с алфавитом A и набором подстановок B определяют нормальный алгоритм. Процесс останавливается только в двух случаях:

когда подходящая подстановка не найдена;
когда применена последняя подстановка из их набора.

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

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

Система подстановок B :

Слово P: 11+11+111 .

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

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

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

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

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

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

I. Суперпозиция алгоритмов . При суперпозиции двух алгоритмов слово первого алгоритма рассматривается как входное слово второго алгоритма B , результат суперпозиции C может быть представлен в виде C(p) и B(A(p)) .

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

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

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

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

Источник

Способы композиции нормальных алгоритмов:

Суперпозиция алгоритмов. При суперпозиции двух алгоритмов A и B выходное слово первого алгоритма рассматривается как входное слово второго алгоритма. Результат суперпозиции С может быть представлен в виде C(_P) = B(A(_P))

Объединение алгоритмов. Объединением алгоритмов A и B в одном и том же алфавите называется алгоритм C, преобразующий любое слово P, содержащееся в пересечении областей определения алгоритма A и B в записанные рядом слова A(_P) и B(_P)

Разветвление алгоритмов. Разветвление представляет собой композицию D трёх алгоритмов A,B и C, причём область определения алгоритма D является пересечением областей определения трёх алгоритмов A,B,C.

Итерация (повтор). Представляет собой такую композицию C двух алгоритмов A и B, что для любого входного слова P, соответствующего слова C(_P), получается в результате последовательного многократного применения алгоритма A до тех пор, пока не получится слово, образуемое алгоритмом B.

Рекурсивные функции.

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

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

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

Т.о. любой алгоритм можно свести к вычислению значений некоторой функции, при целочисленном значении аргумента.

Введём несколько понятий.

Пусть X и Y – два множества. Частичной функцией (или отображением из X в Y) будем называть пару , состоящее из подмножества D(f), содержащее D(f) € X.

Через n будем обозначать множество значений чисел (N) n .

Частичная функция f называется вычислимой, если можно указать такой алгоритм, который для входного набора XC(N) n даёт на выходе f(X), если X € D(f). И 0, если X не принадлежит D(f).

В этом отрезке неформальное понятие алгоритма оказывается связанным с понятием вычислимости функции.

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

Частная функция из (N) m полувычислима, если можно указать такой алгоритм, который для входного набора X(N) n лежит в области определения.

Очевидно, что вычислимые функции полувычислимы, а всюду определённые полувычилсимые функции вычислимы.

Частичная функция f называется ни вычислимой, ни полувычислимой. Фундаментальным открытием теории вычислимости является т.н. тезис Чёрча, который в слабейшей форме имеет следующий вид: можно явно указать:

семейство простейших полувычисимых функций;

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

Suc:N → N ( suc(x) = x+1 – определение следующего за x числа).

Определение размерности области определения функции

Pr n (x1…xn)=x2 – проекция области определения на одну из переменных.

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

Источник