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

Информация - Математика и статистика

Другие материалы по предмету Математика и статистика



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

В 1956 году отечественным математиком А.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднее было названо его именем.

В этом уточнении выделенные нами 7 параметров были определены следующим образом:

Совокупность исходных данных - слова в алфавите S;

Совокупность возможных результатов - слова в алфавите W;

Совокупность возможных промежуточных результатов - слова в алфавите

Р=SWV, где V - алфавит служебных вспомогательных символов.

Действия:

Действия имеют вид либо , либо , где , P*, где

P* - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово просматривается слева направо и ищется вхождение в него слова .

Определение.3.1. Слово называется вхождением в слово , если существуют такие слова и над тем же алфавитом, что и и , для которых верно: =.

Если вхождение в найдено, то слово заменяется на слово .

Все правила постановки упорядочиваются. Сначала ищется вхождение для первого правила подстановки. Если оно найдено, то происходит подстановка и преобразуемое слово опять просматривается слева направо в поисках вхождения. Если вхождение для первого правила не найдено, то ищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил начинается с первого, а слово просматривается сначала и слева направо.

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

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

Правило окончания - выполнение алгоритма заканчивается, если:

было применено правило подстановки вида ,

не применимо ни одно правило подстановки из схемы алгоритма.

7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.

Рассмотрим пример 1 из лекции 2:

построить алгоритм для вычисления

U(n)=n+1;

S={0,1,2,3,4,5,6,7,8,9}; S=W; V={*,+}.

Cхема этого НАМ показана на рисунке 3.1.

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

Увеличиваем на единицу, начиная с цифр младших разрядов.

Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове.

Рис.3.1. Схема НАМ для вычисления U1(n)=n+1

Нетрудно сообразить, что сложность этого алгоритма, выраженная в количестве выполненных правил подстановки, будет равна:

(k+1)+(l+1),

где k - количество цифр в n, l - количество 9, которые были увеличены на 1.

Но в любом случае сложность НАМ для U1(n) больше сложности Машины Тьюринга для этой же функции, которая равнялась k+1.

Обратите внимание, что у НАМ порядок следования правил подстановки в схеме алгоритма существенно влияет на результат, в то время как для МТ он не существеннен.

Построим НАМ для примера 2 из лекции 2:

построить алгоритм для вычисления

U2((n)1)=(n-1)1

Итак, S={|}; W=S; V=, т.е. пусто.

|

Cложность этого алгоритма равна 1, в то время как сложность алгоритма для Машины Тьюринга равнялась n.

Теперь построим НАМ для примера 3 из лекции 2:

построить алгоритм для вычисления

U3((n)1)=(n)10

S={|}; W={0,1,2,3,4,5,6,7,8,9}; V=

Схема этого алгоритма приведена на рисунке 3.2.

1|2

2|3

3|4

4|5

5|6

6|7

7|8

8|9

9||0

|010

0|1

|0|

Рис. 3.2. Схема НАМ для вычисления U3((n)1)=(n)10.

Сложность этого НАМ будет n+[log10n], что существенно меньше сложности для Машины Тьюринга, вычисляющей эту функцию, которая равнялась n2+[log10n(log10n+1)].

Реализацию функции U4 сравнения двух целых чисел оставляем читателю в качестве упражнения.

Замечание: исходное слово надо задать в форме *

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

Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий.

Построение алгоритмов из алгоритмов.

До сих пор, строя ту или иную МТ, или НАМ мы каждый раз все делали заново. Естественно задать вопрос, а нельзя ли при построении, например, новой МТ пользоваться уже построенной ранее МТ.

Например, МТ3 из примера 3

U3((n)1)=(n)10

по существу есть надлежащим образом объединенные МТ для U1(n)=n+1 и U2((n)1)=(n-1)1.

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

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

Определение.3.2. Будем говорить, что МТ1 можно эффективно построить из МТ2 и МТ3 если существует алгоритм, который позволяет, имея программу для МТ2 и МТ3, построить программу для МТ3.

Определение.3.3.Последовательной композицией МТ А и В называется такая МТ С, что

область применимости МТ А и С совпадают;

C()=B(A()).

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

Последовательную композицию МТА и МТВ будем обозначать АВ.

Теоре