Понятие алгоритма. Необходимость уточнения понятия алгоритма. Алгоритмическая машина Поста.

⇐ ПредыдущаяСтр 11 из 45Следующая ⇒

Исторически термин «алгоритм» произошел от фамилии узбекского математика IX века Мухаммада ибн Муса ал-Хорезми, который впервые сформулировал правила 4х основных арифметических действий. Поначалу именно эти правила назывались алгоритмами, затем этот термин получил дальнейшее развитие в первую очередь в математике – алгоритмом стал называться любой способ вычислений, единый для некоторого класса исходных данных. Можно сказать, что алгоритм – это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса.

Однако данное утверждение нельзя принять в качестве строгого определения алгоритма, поскольку в нем использованы другие неопределяемые понятия – однозначность, элементарность и др. Понятие можно уточнить, указав перечень общих свойств, которые характерны для алгоритмов. К ним относятся: Дискретность алгоритма, Детерминированность алгоритма, Элементарность шагов, Направленность алгоритма, Массовость алгоритма.

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

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

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

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

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

Подходы к формализации алгоритма.

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

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

Головку обозначают знаком «Ñ » над обозреваемой секцией, а метку - знаком «М» внутри секции. Пустая секция никакого знака не содержит. За один такт (его называют шагом) головка может сдвинуться на одну секцию вправо или влево и поставить или удалить метку. Работа машины Поста заключается в переходе от одного состояния машины к другому в соответствии с заданной программой, которая строится из отдельных команд. Каждая команда имеет следующую структуру: хКу, где x - номер исполняемой команды; К - указание о выполняемом действии; у - номер следующей команды (наследника). Система команд машины включающая шесть действий, представлена в таблице.

⇐ Предыдущая 6 7 8 9 101112 13 14 15 Следующая ⇒