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



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




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

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

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

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

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

Машина Поста

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

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

Задачи


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


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

Со временем понятие алгоритма расширилось — сейчас мы говорим об алгоритмах для исполнителей, которые работают с текстами и другими объектами реального мира. Однако оказалось, что все эти объекты можно тем или иным способом закодировать в виде цепочек символов, так что любой алгоритм сводится к преобразованию одной символьной строки в другую. Таким способом можно представить и классические вычислительные алгоритмы — операции с цифрами. В алгоритме шахматной игры объекты — это фигуры на доске, но их расположение легко закодировать в символьной форме (вспомните запись шахматных партий).

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

Про любой алгоритм можно сказать следующее:

• алгоритм получает на вход дискретный объект (например, слово);
• алгоритм обрабатывает входной объект по шагам (дискретно), строя на каждом шаге промежуточные дискретные объекты; этот процесс может закончиться или не закончиться;
• если выполнение алгоритма заканчивается, его результат — это объект, построенный на последнем шаге;
• если выполнение алгоритма не заканчивается (алгоритм зацикливается) или заканчивается аварийно (например, в результате деления на 0), то результат его работы при данном входе не определён.

Любой алгоритм рассчитан на определённого исполнителя: он должен использовать только понятные этому исполнителю команды. Задание для исполнителя — это текст на специальном (формальном) языке, который обычно называют программой. Поэтому можно определить алгоритм как программу для некоторого исполнителя.

Напомним, что, с точки зрения теории алгоритмов, достаточно рассматривать только алгоритмы, работающие с цепочками символов, которые называют словами (рис. 5.1).

Рис. 5.1

Рис. 5.1

Каждый алгоритм задаёт (вычисляет) функцию, которая преобразует входное слово в результат (выходное слово). Такая функция может быть не определена для некоторых входных слов, если алгоритм зацикливается ИЛ И завершается аварийно.

Функция, заданная алгоритмом, может быть нигде не определена. Например, алгоритм

нц пока да

кц


зацикливается при любом входном слове.

Алгоритмы называются эквивалентными, если они задают одну и ту же функцию. То есть при любом входном слове оба алгоритма должны приводить к одному и тому же результату или зацикливаться (оба алгоритма не выдают никакого результата). Например, следующие алгоритмы для выбора минимального из значений переменных а и b эквивалентны:



Следующая страница Универсальные исполнители



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






Наверх