Информатика -продвинутый курс



         

НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА - часть 4


= + 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. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В

выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В. Результат суперпозиции С может быть представлен в виде С(р) = В(А(р)),




Содержание  Назад  Вперед