Детерминированность. Процесс применения правил к исходным данным (путь решения задачи) определен однозначно или по другому - каждый шаг однозначно определяется состоянием системы
Формальность
Понятность.
Результативность.
Дискретность.
Детерминированность.
Массовость
Конечный набор точных и понятных предписаний (правил, инструкций, команд), позволяющих механически решать конкретную задачу из определенного класса однотипных задач.
Вплоть до 30-х годов прошлого столетия понятие алгоритма носило сугубо интуитивный характер.
Под алгоритмом понимали:
Основными свойствами такого «интуитивного» понятия алгоритма являются:
Массовость. Означает, что алгоритм применим к целому классу задач, а при решении конкретной задачи из класса исходные данные могут меняться в определенных пределах или по другому алгоритм применим для разных наборов исходных.
Дискретность. Означает, что путь решения задачи определен в виде последовательности шагов – четко разделенных друг от друга предписаний. Только выполнив одно предписание, можно приступить к выполнению следующего.
Результативность. На каждом шаге процесса применения правил известно, что считать результатом этого процесса, а сам процесс должен закончиться за конечное число шагов.
Понятность. Означает, что алгоритм создается в расчете на определенного исполнителя, т.е. необходимо, чтобы он мог понять и выполнить каждый шаг предписания.
Формальность - инструкции алгоритма могут выполняться формально (бездумно)
Для задач, имеющих положительное решение, этого определения достаточно. Другое дело, когда задача или класс задач не имеют решения. В этом случае требуется строго формализованное понятие алгоритма, чтобы иметь возможность доказать его отсутствие. Определение такого понятия алгоритма стала одной из центральных математических проблем. Решение было получено в середине 30-х годов в работах известных математиков, в двух эквивалентных формулировках: на основе особого класса арифметических функций, называемых рекурсивными (Д. Гильберт, К. Гедель, А. Черч, С. Клини), и на основе абстрактных автоматов (Э. Пост и А. Тьюринг).
Рекурсия– процесс определения функции, при котором ее значение для произвольных значений аргументов выражается известным образом через значения функции для меньших значений аргументов.
Функция, для которой существует алгоритм оценки для любого аргумента в области определения функции, называется вычислимой.
Функция, для которой существует эффективная процедура ее вычисления на основе рекурсии, называется рекурсивной.
Класс рекурсивных функций тождественен с классом всюду определенных вычислимых функций – тезис Черча.
Функция, определенная не для всех значений аргументов, а только на некотором подмножестве, называется частичной функцией.
Все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными – тезис Клини.
Понятие частично рекурсивных функций используют для доказательства алгоритмической разрешимости или неразрешимости проблемы.
Определение алгоритма на основе абстрактных автоматов (машины Тьюринга)
Алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина».
Под «машиной» в данном случае подразумевается некоторый абстрактный, существующий лишь в воображении автомат.
В общем случае такая машина состоит из следующих частей:
- информационная лента, состоящая из ячеек, представляющая неограниченную память машины, так как лента неограниченна в обе стороны. В каждой ячейке можно хранить только один символ, в том числе и ноль;
- головка чтения/записи, вдоль которой может перемещаться лента (или которая может перемещаться относительно информационной ленты);
- устройство управления, которое в каждый рассматриваемый момент находится в некотором «состоянии». Устройство управления может находиться в некотором конечном числе состояний, если это состояние заключительное, машина заканчивает работу.
Такая машина может сдвигать ленту на одну ячейку влево или вправо, оставляя содержимое ячеек неизменным, или может изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной. Машина Тьюринга работает в произвольном конечном алфавите и выполняет некоторое конечное число приказов.
Машины Тьюринга представляют собой универсальных исполнителей, с использованием которых можно имитировать все алгоритмические процессы, описываемые математиками. Было доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций. Т.о. вопрос о существовании или не существовании алгоритма для задачи того или иного типа следует понимать как вопрос о существовании или не существовании машины Тьюринга, обладающей нужным свойством.
Интуитивное понимание машины Тьюринга: имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.
На базе теорий рекурсивных функций и абстрактных автоматов появилось целое математическое направление – теория алгоритмов, в которой в основу определения алгоритма было поставлено особое соответствие между словами в том или ином абстрактном алфавите (А. Марков, Л. Калужнин). Теория алгоритмов оказалась тесно связанной не только с теоретической математикой (математической логикой, алгеброй, геометрией, анализом), но и с рядом областей лингвистики, экономики, физиологии мозга, философии, естествознания. Примером задачи этой области может служить описание алгоритмов, реализуемых человеком в процессе умственной деятельности.
А.А. Марков –
Алгоритм– это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами: определенности, массовости и результативности
· определенность (общепонятность и точность, не оставляющая места для произвола),
· массовость (возможность применения ко всем процессам данного класса),
