Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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

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

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

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

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

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

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

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

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

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

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


Поделиться:



Популярное:

  1. I. Понятие и система криминалистического исследования оружия, взрывных устройств, взрывчатых веществ и следов их применения.
  2. I. Понятие криминалистической тактики.
  3. II. Прокомментируйте параллельные переводы и объясните необходимость использования приема конкретизации.
  4. II. Прокомментируйте параллельные переводы и объясните необходимость использования приема опущения.
  5. II. Прокомментируйте параллельные переводы и объясните необходимость использования приема примечаний.
  6. III Необходимость принятия христианства
  7. IV. Понятие о частях речи (ЧР)
  8. V1: Понятие, объект, предмет и система криминологии
  9. Административная юрисдикция. Понятие и основные черты.
  10. Административно-процессуальные нормы: понятие и виды
  11. Административно-юрисдикционный процесс: понятие, признаки, принципы. Административно-юрисдикционные производства.
  12. Административное задержание: понятие, сроки


Последнее изменение этой страницы: 2016-04-10; Просмотров: 2321; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.011 с.)
Главная | Случайная страница | Обратная связь