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

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

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

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

a_i Þ b_i,

где a_i и b_i — слова в алфавите V_T.

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

Р_о ®P₁ ®P₂ ®... ®P_i®... ®Q.

Для организации последовательного использования правил вывода заключительного слова все они должны быть индексированы

i Î [1, 2, 3...].

Если Р_i - цепочка подслов (g₁ag₂) в алфавите V_т (g₁ и g₂ слова, возможно, пустые в алфавите V_T) и среди множества правил есть подмножество {aÞb_i}, то выбрать правило, имеющее наименьший номер и выполнить подстановку в слово (g₁ag₂) Þ (g₁b_i g₂).

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

. Среди множества правил подстановки есть простые правила, которые обозначают так: a₁ ® b₁ и заключительные: a_i ® · b _i .

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

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

Для того, чтобы построить модель нормального алгоритма, необходимо в соответствии с правилами подстановки найти множество распознавателей вхождения слов a_i в слово P_i и множество операторов подстановки слова b_i в слово P_{i+1 i}.

На граф-схеме алгоритма (см. рис.5.19) следует выделить два типа вершин:

• распознаватели вхождения - PB_i;

• операторы подстановки - ОП_i.

Распознаватели вхождения соединяются последовательно в соответствии с заданной нумерацией правил. Второй выход распознавателя вхождения при обнаружении a_i в слове Р_i передает информацию о слове P_i в оператор подстановки — ОП_i, где выполняется соответствующая замена слова a на слово b, т.е. g₁ a g₂ Þ g₁ b g₂ .

Выход оператора подстановки направляет преобразованное слово в начало алгоритма, если применена простая подстановка, и

в конец алгоритма, если применена заключительная подстановка.

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

М ₁:= базовая функция С_n(х)=0 в десятичной системе счисления.

Пусть х =’ # XXX... #.’ число в десятичной системе счисления, а X – цифра. Алфавит V_t содержит три символа v_t = {X, #, (},

Протокол.

1) # X ® (X;

2) (X ® 0 (;

3) (# ® ·#..

Пусть x = 289. Тогда #289# Þ#(289# Þ#0(89# Þ#00(9# Þ#000(# Þ#000·#.

На рис. 5.20 приведена блок-схема этого алгоритма.

М ₂:= базовая функции l(х) в десятичной системе счисления.

l(х)= # XXX... # =0.

Пусть х =’ # XXX... #.’ число в десятичной системе счисления, а X – цифра..

Алфавит содержит четыре символа V_t={X, #, (,)}.

Протокол.

1) #XÞ(X; 3) (#Þ)#; 5) X) Þ· (X+1);

2) (XÞX(; 4) 9) Þ)0; 6) #)Þ·1.

 

Пусть x=0.

Тогда #0# Þ#(0# Þ#0(# Þ #0)# Þ #·1#.

Пусть x=289.

Тогда #289# Þ#(289# Þ#2(89# Þ#28(9# Þ#289(# Þ#289)# Þ#28)0# Þ#2·90#.

Пусть x=999.

Тогда #999# Þ#(999# Þ#9(99# Þ#99(9# Þ#999(#Þ#999)# Þ#99)0# Þ#9)00# Þ#)000# Þ#·1000#. На рис. 5.21 приведена блок-схема этого алгоритма.

М ₃:= преобразование цифры в унарный код.

Если Р_о = # X₁Х₂Х₃ ...#, то Q = # |^x1#|^x2#|^x3#....

Алфавит V_t для преобразования цифры в код содержит символы V_Ò = {X, #, /, (}.

Протокол.

1) # X ®(X; 3) (0 ® #; 5) |X ®|(X;

2) (X ®(X-1 |; 4) #|®|#; 6) |# ®·|.

Пусть x=234.

Тогда # 234# Þ(234# Þ(1 | 34# Þ(0 || 34# Þ # || 34# Þ#|| (34# Þ# || (2 | 4# Þ# || (1 || 4# Þ# || (0

THORN;# ||#

THORN;# || #

THORN;# ||#

THORN;# || #

(1

THORN;# || #

(0

THORN;|| #

#

THORN; || #

# |#

THORN; || #

THORN;|| #

#

THORN;|| #

На рис. 5.22 приведена блок-схема этого алгоритма. М4:= вычисление суммы двух чисел в унарном коде, т.е. f (х; у) = | x + y. Если Ро =#|x+|y#, то Q =# |x + y#. Алфавит для М3 есть Vt = { |, +, #, (}. Протокол. 1) #| ® (|; 2) (| ® |(; 3) (+ ® |(; 3) |(# ®•#. Пусть х=2, у=3. Тогда Ро =.# ||+ # Þ #(||+# Þ# |(|+# Þ# ||(+

THORN;#

(

THORN;#

THORN;#

THORN;#

THORN;#||·# =Q. На рис. 5.23 приведена блок-схема этого алгоритма.       М5:= вычисление произведения двух чисел в унарном коде. f(х; у)=|x* y. . Если Ро= #|x*|y #, то Q = #|x× y #. Алфавит содержит символы Vт ={|; *, #, (,)}. Протокол. 1) ×| | ®(×|; 4))(®(); 7) () ®); 2) ×|# ®(#; 5))| ®|); 8)) ®|; 3) |(®(|); 6) (| ®(; 9) |# ® •|#. Вычисление произведения двух чисел х = 3 и у = 2 имеет вид: #

THORN; #

THORN; #||(|)*|# Þ #|(|)|)*|# Þ #(|)|)|)*|# Þ #()|)|)*|# Þ #)|)|)*|# Þ #|))|)*|# Þ #|)|))*|# Þ #||)))*|# Þ #||)))(# Þ#||))()# Þ #||)())# Þ #||()))# Þ#|(|))))# Þ #(|)|))))# Þ #()|))))# Þ#)|))))# Þ #|)))))# Þ #||))))# Þ #

THORN; #

THORN; #

THORN; #

Nbsp; Анализ трех типов моделей показал, что основные свойства дискретности, детерминизма, массовости и результативности остаются неизменными для различных способов описания. Различия наблюдаются лишь в использовании алгоритмических объектов. Если для рекурсивных функций объектами являются числовые функции, а процесс вычисления задан операторами суперпозиции, рекурсии и минимизации, то для машин Тьюринга такими объектами являются символы алфавитов внешней и внутренней памяти, а процесс вычисления задан функциями выхода, перехода и перемещения. Для нормального алгоритма Маркова алгоритмическими объектами являются слова, а процесс вычисления задан правилами подстановки, изменяющими состав и структуру исходного слова до искомого результата. Функция называется вычислимой, если существует вычисляющий ее алгоритм.Различие между вычислительной функцией ивычислительным алгоритмом – это различие между описанием функции и способом получения ее значения для заданных значений независимых переменных аргумента. Все модели обеспечивают способ получения ее значений. Но процесс вычисления может быть определен для для всего множества значений независимых переменных аргумента. Особо при использовании оператора минимизации. Функции, значения которых определены не для всех значений независимых переменных аргумента, называют частичными. Следовательно, вычислительные функции, для которых ограничена область определения, называют частично вычислимыми функциями. Если частично вычислимая функция определена на множестве целых положительных чисел и принимает значение на том же множестве, то ее называют частично рекурсивной функцией. Функцию, определенную на всем множестве целых положительных чисел и принимающую значение на том же множестве, называют общерекурсивной функцией. Анализ моделей показывает, что на каждом шаге вычисления формируется частично рекурсивная функция и каждая функция этой последовательности является либо базовой, либо частично рекурсивной с использованием результатов предшествующего шага. Распространена гипотеза, известная под названием тезиса Черча, о том, что всякая функция, вычислимая некоторым алгоритмом, есть частично рекурсивная функция; и наоборот, всякая частично рекурсивная функция вычислима некоторым алгоритмом.

Сложность вычислений

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

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

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

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

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

 

 

Вопросы и задачи

5.1. Доказать, что следующие функции есть примитивно рекурсивные:

a) f(х)= х+n;

б) f(x)= n;

в) f(x)= x!

5.2. Какие функции могут быть получены по схеме примитивной рекурсии:

а) g(х)= J_1,1; h(х, у, f(х, у))= f₊(J_3,1, J_3,3);

б) g(х)= J_1,1; h(х, у, f(х, у))= f₊(J_3,1, J_3,2);

в) g(х)= J_1,1; h(х, у, f(х, у))= f₊(J_3,2, J_3,3);

5.3. Применить оператор минимизации к функции f по переменной у. Найти области определения и значения функции j.

a) f(a, y) = [y/2];

б) f(x, y) = (x - 2y);

в) f(x, y) = (x² - 2y).

5.4. Построить машину Тьюринга для вычисления функций:

a) f(x)= x/2;

б) f(x)= Sg x;

в) f(x)= [x/2].

5.5. Какую функцию вычисляет машина Тьюринга со следующей программой команд:

Т: q_о # ® q₁ # П;

q_о| ® q₁ # П;

q₁ # ® q₂ # с;

q₁ | ® q₁ | П.

5.6. Построить машины Тьюринга, выполняющие служебные функции:

a) T₁: #|^{x - 1}q_o|# ® q_k|^x#;

б) T₂: #|^{x - 1}q_o|# ® |^x# q_k |^x#;

в) T₃: q_o|^x# ®q_k|^x/2 #.

5.7. Написать протокол, таблицу и построить граф для машины Тьюринга:

T: #|^x # |^{y - 1}q_o|# ®#|^x#|^y#|^{(x + y) - 1}q_k|#.

5.8. Какие слова могут быть получены при использовании в нормальном алгоритма Маркова правил подстановки: 1) ав®ва; 2) ас ® са из слов: а) Р_о = ававав; б) Р_о = авсавс; в) Р_о = васвас.

 

 

⇐ Предыдущая22232425262728293031Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: