В середине прошлого века выдающийся русский математик А.А. Марков ввел понятие нормального алгоритма (алгоритма) с целью уточнения понятия "алгоритм", что позволяет решать задачи по определению алгоритмически неразрешимых проблем. Позже это понятие получило название нормального алгоритма Маркова (НАМ).
   Язык НАМ, с одной стороны, намеренно беден, что необходимо для цели введения понятия "алгоритм". Однако, с другой стороны, идеи НАМ положены в основу большой группы языков программирования, получивших название языки логического программирования, которые являются темой данного пособия.  Для определения НАМ вводится произвольный алфавит - конечное непустое множество символов, при помощи которых описывается алгоритм и данные. В алфавит также включается пустой символ, который мы будем обозначать греческой буквой .
   Под словом понимается любая последовательность непустых символов алфавита либо пустой символ, который обозначает пустое слово. Всякий НАМ определяется конечным упорядоченным множеством пар слов алфавита, называемых подстановками. В паре слов подстановки левое (первое) слово непустое, а правое (второе) слово может быть пустым символом. Для наглядности левое и правое слово разделяются стрелкой. Например, в качестве данных алгоритма берется любая непустая строка символов. Работа НАМ состоит из последовательности совершенно однотипных шагов. Шаг работы алгоритма может быть описан следующим образом: В упорядоченной последовательности подстановок ищем самую первую подстановку, левое слово которой входит в строку данных. В строке данных ищем самое первое (левое) вхождение левого слова найденной подстановки. Это вхождение в строке данных заменяем на правое слово найденной подстановки (преобразование данных). Шаг работы алгоритма повторяется до тех пор, пока:
 - либо не возникнет ситуация, когда шаг не сможет быть выполнен из-за того, что ни одна подстановка не подходит ( левое слово любой подстановки уже не входит в строку данных ) - правило остановки ;
 - либо не будет установлено, что процесс подстановок не может остановиться.
   В первом случае строка данных, получившаяся при остановке алгоритма, является выходной (результатом) и алгоритм применим к входным данным, а во втором случае алгоритм не применим к входным данным. Так, определенный выше в примере нормальный алгоритм Маркова преобразует слово в слово следующим образом (над стрелкой преобразования мы пишем номер применяемой подстановки, а в преобразуемой строке подчеркиваем левое слово применяемой подстановки ): а при преобразовании слова abbc этот же алгоритм будет неограниченно работать, так как имеет место цикличное повторение данных: Таким образом, всякий нормальный алгоритм Маркова определяет функцию, которую мы назовем нормальной (или вычислимой по Маркову), которая может быть частичной и которая в области определения входному слову ставит в соответствие выходное слово.
   Все правила постановки упорядочиваются. Сначала ищется вхождение для первого правила подстановки. Если оно найдено, то происходит подстановка и преобразуемое слово опять просматривается слева направо в поисках вхождения. Если вхождение для первого правила не найдено, то ищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил начинается с первого, а слово просматривается сначала и слева направо.

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

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

Пример№1
Итак, - пустая буква
1) Например, мы хотим решить: f(x)=5-3
  1#1#                        
  #1#1                         
   #                              
Решение:                             
11111#111
1111#11
111#1
11#
  11
Ответ: 2

 Пример№2
2)  Вычислить f(x)=x/2
#111#                     
#1#1                       
#                          
#                           
Решение:                                 
Проверим на примере 4/2, итак: 
1111
#1111
1#11
11#
11
Ответ: 2

 Пример№3
3) А если мы проверим на примере 5/2? Итак:
#111#                     
#1#1                       
#                          
#                           
Решение:  
11111
#11111
1#111
11#1
11#1
11#1
.......
Таким образом у нас получилось зацикливание.

Оценка - 1.0 (13)
2012-12-10 • Просмотров [ 6479 ]