Урок 11
Алгорифмы Маркова Советский математик Андрей Андреевич Марков, который в середине XX века изучал разрешимость некоторых задач алгебры, предложил новую модель вычислений, которую он назвал нормальными алгорифмами.
Нормальные алгорифмы Маркова (НАМ) — это строгая математическая форма записи алгоритмов обработки символьных строк, которую можно использовать для доказательства разрешимости или неразрешимости различных задач.
Марков предположил, что любой алгоритм можно записать как НАМ. В отличие от машин Тьюринга и Поста НАМ — это "чистый” алгоритм, который не связан ни с каким "аппаратным обеспечением” (лентой, кареткой и т.п.). НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задается алфавитом и системой подстановок. Заметьте, что в жизни мы нередко применяем такие замены. Например, при умножении в столбик мы не вычисляем каждый раз произведение 7 × 8, а просто помним, что оно равно 56. Пусть алфавит НАМ — это русские буквы, и задана система подстановок а → н ух → ло м → с
Применим эту систему подстановок к начальному слову "муха”. Подстановки нужно просматривать по порядку, начиная с первой. Первая подстановка означает "если в слове есть буквы а, заменить пер- вую букву а на букву н”. В слове муха есть буква "а”, поэтому заменяем ее на "н”. Получается "мухн”. Начинаем просмотр подстановок сначала. Букв "а” больше нет, поэтому переходим ко второй под- становке. Сочетание "ух” есть в слове "мухн”, поэтому вторая подстановка срабатывает, и мы заменяем "ух” на "ло”: получается "млон”. Теперь ни первая, ни вторая подстановки не применимы, а использование третьей дает в результате слово "слон”. Больше ни одну подстановку сделать нельзя, и НАМ заканчивает работу. Таким образом, приведенная система подстановок преобразует слово "муха” в слово "слон”. При поиске образца рабочая цепочка символов просматривается сначала. Если в строке словообразец встречается несколько раз, то за один шаг заменяется только первое из них. Так как на следующем шаге просмотр опять начинается с начала цепочки, после первой выполненной замены может "сработать” совсем другая подстановка. В записи подстановок слово-образец может быть пустым, в этом случае слово-замена приписывается в начало рабочей строки: → 0. Такая подстановка всегда должна быть последней в списке, иначе программа зациклится: в начало слова будут постоянно дописываться все новые и новые нули. Если после слова-замены стоит точка, после выполнения такой подстановки работа программы заканчивается. Например, если применить НАМ а → о. к слову "карова”, то в результате получим "корова”, потому что после первого же действия работа программы закончится, и последняя буква не будет заменена. Пример: Построим НАМ для следующей задачи: удалить из строки, состоящей из букв a и b, первый символ.
Например, строка abba должна быть преобразована в bba.
Казалось бы, здесь нужно использовать систему подстановок
a → . b → .
Однако такой НАМ будет неправильно работать для слов, начинающихся с буквы b, например, для слова bba, в котором будет удалена последняя буква, потому что первая подстановка выполнится раньше, чем вторая. Перестановка двух строк также не дает решения — теперь алгоритм неправильно работает для слов, начинающихся с буквы a. Чтобы решить эту задачу, в алфавит НАМ добавляют еще один специальный символ, например, символ "*”. Этим символом помечают начало слова, используя подстановку → * Полный алгоритм выглядит так: *a → . *b → . → * Как показано в теории алгоритмов, любой алгоритм для машин Тьюринга и Поста можно записать как НАМ, и наоборот. Поэтому все три рассмотренных подхода к строгому определению понятия "алгоритм” эквивалентны (равносильны).
Программное обеспечение:
Алгоритм Маркова программа (К.Поляков)
Вопросы:
1. Что такое нормальный алгорифм Маркова? 2. Зачем используют специальные символы в НАМ? 3. Что означает эквивалентность различных универсальных исполнителей? Задачи:
1. Что делают следующие НАМ, если применить их к символьной цепочке, состоящей из нулей и единиц: а) 0 → 00 1 → 11 б) *0 → 0* *1 → 1* * → =. → * в) *0 → 00* *1 → 11* * → . → * Как будет работать каждая из программ при различных начальных состояниях ленты? 2. Напишите НАМ, который "сортирует” цифры двоичного числа так, чтобы сначала стояли все нули, а потом — все единицы 3. Напишите НАМ, который умножает двоичное число на 2, добавляя 0 в конец записи числа
Дополнительный материал:
1. Майер Р.В. Алгоритмы Маркова (komp-model.narod.ru) Использованная литература: 1. К.Ю. Поляков, Е.А. Еремин "Элементы теории алгоритмов". Журнал "Информатика" №1, 2012 г. |