Уроки 58 - 60
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Зачем нужно определение алгоритма?
Нормальные алгорифмы Маркова
Нормальные алгорифмы Маркова
Советский математик А. А. Марков младший (сын Андрея Андреевича Маркова (2 (14) июня 1856, Рязань — 20 июля 1922, Петроград) — русского математика, академика, внёсшего большой вклад в теорию вероятностей, математический анализ и теорию чисел), который в середине XX века изучал разрешимость некоторых задач алгебры, предложил новую модель вычислений, которую он назвал нормальными алгорифмами.
Нормальные алгорифмы Маркова (НАМ) — это строгая математическая форма записи алгоритмов обработки символьных строк, которую можно использовать для доказательства разрешимости или неразрешимости различных задач. Марков предположил, что любой алгоритм можно записать как НАМ. В отличие от машин Тьюринга и Поста НАМ — это «чистый» алгоритм, который не связан ни с каким «аппаратным обеспечением» (лентой, кареткой и т. п.).
НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задаётся алфавитом и системой подстановок. Заметьте, что в жизни мы нередко применяем такие замены. Например, при умножении в столбик мы не вычисляем каждый раз произведение 7 • 8, а просто помним, что оно равно 56.
Пример 1. Пусть алфавит НАМ — это русские буквы и задана система подстановок:
а → н
ух → ло
м → с
Применим эту систему подстановок к начальному слову «муха». Подстановки нужно просматривать по порядку, начиная с первой. Первая подстановка означает: «если в слове есть буквы “а”, заменить первую букву “а” на букву “н”». В слове «муха» есть буква «а», поэтому заменяем её на «н». Получается «мухн».
Начинаем просмотр подстановок сначала. Букв «а» больше нет, поэтому переходим ко второй подстановке. Сочетание «ух» есть в слове «мухн», поэтому вторая подстановка срабатывает, и мы заменяем «ух» на «ло»: получается «млон».
Теперь ни первая, ни вторая подстановки не применимы, а использование третьей даёт в результате слово «слон». Больше ни одну подстановку сделать нельзя, и НАМ заканчивает работу. Таким образом, приведённая система подстановок преобразует слово «муха» в слово «слон».
При поиске образца рабочая цепочка символов просматривается с начала. Если в строке слово-образец встречается несколько раз, то за один шаг заменяется только первое из них. Так как на следующем шаге просмотр опять начинается с начала цепочки, после первой выполненной замены может «сработать» совсем другая подстановка.
В записи подстановок слово-образец может быть пустым, в этом случае слово-замена приписывается в начало рабочей строки:
→ О
Такая подстановка всегда должна быть последней в списке, иначе программа зациклится: в начало слова будут постоянно дописываться всё новые и новые нули.
Если после слова-замены стоит точка, после выполнения такой подстановки работа программы заканчивается. Например, если применить НАМ
а→о.
к слову «карова», то в результате получим «корова», потому что после первого же действия работа программы закончится, и последняя буква не будет заменена.
Пример 2. Построим НАМ для следующей задачи: удалить из строки, состоящей из букв «а» и «b», первый символ. Например, строка «abba» должна быть преобразована в «bbа». Казалось бы, здесь нужно использовать систему подстановок:
а → . b → .
Однако такой НАМ будет неправильно работать для слов, начинающихся с буквы «b», например для слова «bbа», в котором будет удалена последняя буква, потому что первая подстановка выполнится раньше, чем вторая. Перестановка двух строк также не даёт решения — теперь алгоритм неправильно работает для слов, начинающихся с буквы «а». Чтобы решить эту задачу, в алфавит НАМ добавляют еще один специальный символ, например символ «*». Этим символом помечают начало слова, используя подстановку.
→ *
Полный алгоритм выглядит так:
*а → .
*b → .
→ *
Сначала срабатывает третья подстановка (ставим «*» в начало строки), затем, в зависимости от первой буквы исходного слова, работает первая или вторая подстановка, и алгоритм заканчивает работу. Дополнительный символ похож на маркер в текстовом редакторе — он отмечает место в тексте, с которым потом будут выполняться какие-то действия.
Как показано в теории алгоритмов, любой алгоритм для машин Тьюринга и Поста можно записать как НАМ и наоборот.
Поэтому все три рассмотренных подхода к строгому определению понятия «алгоритм» эквивалентны (равносильны).
Следующая страница 
Вопросы и задания
Cкачать материалы урока
