Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)



Уроки 58 - 60
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма




Содержание урока

Зачем нужно определение алгоритма?

Что такое алгоритм?

Универсальные исполнители

Машина Тьюринга

Машина Поста

Нормальные алгорифмы Маркова

Вопросы и задания

Задачи


Нормальные алгорифмы Маркова


Советский математик А. А. Марков младший (сын Андрея Андреевича Маркова (2 (14) июня 1856, Рязань — 20 июля 1922, Петроград) — русского математика, академика, внёсшего большой вклад в теорию вероятностей, математический анализ и теорию чисел), который в середине XX века изучал разрешимость некоторых задач алгебры, предложил новую модель вычислений, которую он назвал нормальными алгорифмами.

Нормальные алгорифмы Маркова (НАМ) — это строгая математическая форма записи алгоритмов обработки символьных строк, которую можно использовать для доказательства разрешимости или неразрешимости различных задач. Марков предположил, что любой алгоритм можно записать как НАМ. В отличие от машин Тьюринга и Поста НАМ — это «чистый» алгоритм, который не связан ни с каким «аппаратным обеспечением» (лентой, кареткой и т. п.).

НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задаётся алфавитом и системой подстановок. Заметьте, что в жизни мы нередко применяем такие замены. Например, при умножении в столбик мы не вычисляем каждый раз произведение 7 • 8, а просто помним, что оно равно 56.

Пример 1. Пусть алфавит НАМ — это русские буквы и задана система подстановок:

а → н
ух → ло
м → с

Применим эту систему подстановок к начальному слову «муха». Подстановки нужно просматривать по порядку, начиная с первой. Первая подстановка означает: «если в слове есть буквы “а”, заменить первую букву “а” на букву “н”». В слове «муха» есть буква «а», поэтому заменяем её на «н». Получается «мухн».

Начинаем просмотр подстановок сначала. Букв «а» больше нет, поэтому переходим ко второй подстановке. Сочетание «ух» есть в слове «мухн», поэтому вторая подстановка срабатывает, и мы заменяем «ух» на «ло»: получается «млон».

Теперь ни первая, ни вторая подстановки не применимы, а использование третьей даёт в результате слово «слон». Больше ни одну подстановку сделать нельзя, и НАМ заканчивает работу. Таким образом, приведённая система подстановок преобразует слово «муха» в слово «слон».

При поиске образца рабочая цепочка символов просматривается с начала. Если в строке слово-образец встречается несколько раз, то за один шаг заменяется только первое из них. Так как на следующем шаге просмотр опять начинается с начала цепочки, после первой выполненной замены может «сработать» совсем другая подстановка.

В записи подстановок слово-образец может быть пустым, в этом случае слово-замена приписывается в начало рабочей строки:

→ О

Такая подстановка всегда должна быть последней в списке, иначе программа зациклится: в начало слова будут постоянно дописываться всё новые и новые нули.

Если после слова-замены стоит точка, после выполнения такой подстановки работа программы заканчивается. Например, если применить НАМ
а→о.

к слову «карова», то в результате получим «корова», потому что после первого же действия работа программы закончится, и последняя буква не будет заменена.

Пример 2. Построим НАМ для следующей задачи: удалить из строки, состоящей из букв «а» и «b», первый символ. Например, строка «abba» должна быть преобразована в «bbа». Казалось бы, здесь нужно использовать систему подстановок: а → . b → .

Однако такой НАМ будет неправильно работать для слов, начинающихся с буквы «b», например для слова «bbа», в котором будет удалена последняя буква, потому что первая подстановка выполнится раньше, чем вторая. Перестановка двух строк также не даёт решения — теперь алгоритм неправильно работает для слов, начинающихся с буквы «а». Чтобы решить эту задачу, в алфавит НАМ добавляют еще один специальный символ, например символ «*». Этим символом помечают начало слова, используя подстановку.

→ *

Полный алгоритм выглядит так:

*а → .
*b → .
→ *

Сначала срабатывает третья подстановка (ставим «*» в начало строки), затем, в зависимости от первой буквы исходного слова, работает первая или вторая подстановка, и алгоритм заканчивает работу. Дополнительный символ похож на маркер в текстовом редакторе — он отмечает место в тексте, с которым потом будут выполняться какие-то действия.

Как показано в теории алгоритмов, любой алгоритм для машин Тьюринга и Поста можно записать как НАМ и наоборот.

Поэтому все три рассмотренных подхода к строгому определению понятия «алгоритм» эквивалентны (равносильны).

Следующая страница Вопросы и задания



Cкачать материалы урока




Наверх