довательность действий, которые нужно выполнить, чтобы из исходных данных по-
лучить результат. Однако такое определение алгоритма не является математически
строгим и, следовательно, не позволяет рассмотреть свойства алгоритмов как свой-
ства некоторых формальных объектов. Практическая реализация алгоритмов в виде
программы привела к необходимости сравнения качества алгоритмов. Стало важным
не просто показать разрешимость или неразрешимость какой-либо проблемы, но и
оценить возможности компьютера для практического решения поставленных задач.
Таким образом, необходимость рассмотрения математического определения алго-
ритма определяется несколькоми причинами.
Во–первых, только при наличии формального определения алгоритма можно
ставить задачу о разрешимости или неразрешимости каких–либо проблем. Если
мы хотим доказать, что та или иная функция не является эффективно вычислимой,
то мы прежде всего должны сформулировать точное математическое понятие эффек-
тивной вычислимости. Главным результатом теории алгоритмов, как будет показано
в дальнейшем, является доказательство существованиия некоторых неразрешимых
проблем.
Во–вторых, необходимо иметь математически точный инструмент для срав-
нения различных алгоритмов решения одних и тех же задач, а также для срав-
нения различных проблем по сложности алгоритмов их решения. Такое сравнение
невозможно без введения средств исследования алгоритмов как математических объ-
ектов и использования точного языка математики для их описания. Иначе говоря,
сами алгоритмы должны стать такими же предметами точного исследования, как те
объекты, для работы с которыми они предназначены.
Прежде, чем ввести математически строгое определение алгоритма, необходимо
рассмотреть свойства тех объектов, которые мы считаем алгоритмами. С точки зре-
ния современной практики алгоритм — это программа, а критерием алгоритмично-
сти процесса является возможность его запрограммировать. Именно благодаря этой
реальности алгоритма, а также потому, что подход программиста к математическим
методам всегда основан на возможности их практической реализации, можно выде-
лить следующие характерные свойства, которым удовлетворяет любой алгоритм.
1. "Конечность."
Любой алгоритм задается последовательностью инструкций конечных размеров.
Например, конечную длину имеет любая программа для ЭВМ, любой математиче-
ский алгоритм можно описать с помощью конечного числа русских слов.
2. "Детерминированность."
Алгоритм выполняется детерминированно, т.е. представляющая алгоритм после-
довательность действий на одних и тех же данных всегда выполняется одинаково.
Вычисления выполняются детерминированно без обращения к случайным устрой-
ствам (например, игральным костям ). Здесь следует отметить, что все программно
реализованные датчики случайных чисел генерируют на самом деле псевдослучай-
ную последовательность с достаточно большим периодом.
3. "Дискретность."
Отдельные инструкции алгоритма выполняются дискретно, т.е. последовательно
по отдельным шагам, без использования каких–либо аналоговых устройств непре-
рывного принципа действия или соответствующих непрерывных методов.
4. "Вычислимость" или "эффективная вычислимость."
Должен существовать вычислитель, способный выполнить указанные в алгорит-
ме инструкции. Здесь под вычислителем может пониматься любое существующее
или реализуемое устройство, способное понимать инструкции алгоритма. Частным
случаем такого устройства может являться компьютер или человек. Понятие "эф-
35