В этом разделе будет уточнено понятие алгоритма. Кроме того, будут даны строгие математические понятия, которые формализуют представление о том, что некоторые функции поддаются вычислению с помощью алгоритма, скажем на компьютере, как только для этого будет составлена надлежащая программа, тогда как другие функции, заданные неэффективным определением, могут требовать творческого подхода для вычисления своих значений.
Под алгоритмом понимается способ преобразования представления информации. Слово algorithm - произошло от имени аль-Хорезми - автора известного арабского учебника по математике (от его имени произошли также слова "алгебра" и "логарифм").
Интуитивно говоря, алгоритм - некоторое формальное предписание, действуя согласно которому можно получить решение задачи.
Алгоритмы типичным образом решают не только частные задачи, но и классы задач. Подлежащие решению частные задачи, выделяемые по мере надобности из рассматриваемого класса, определяются с помощью параметров. Параметры играют роль исходных данных для алгоритма.
Основные особенности алгоритма
Определенность.Алгоритм разбивается на отдельные шаги (этапы), каждый из которых должен быть простым и локальным.
Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных данных, т. е. величин, заданных ему до начала работы.
Вывод. Алгоритм имеет одну или несколько выходных величин, т. е. величин, имеющих вполне определенное отношение к входным данным.
Детерминированность. После выполнение очередного шага алгоритма однозначно определено, что делать на следующем шаге.
Полезные алгоритмы должны быть практичными и хорошими с эстетической точки зрения.
Примеры алгоритмов широко известны: изучаемые в школе правила сложения и умножения десятичных чисел или, скажем, алгоритмы сортировки массивов. Для алгоритмически разрешимой постановки задачи всегда имеется много различных способов ее решения, т. е. различных алгоритмов.
Примеры "почти" алгоритмов: медицинский и кулинарный рецепты. Кстати, почему такие рецепты во многих случаях нельзя рассматривать как алгоритмы?
Данное здесь определение алгоритма не является, конечно, строгим, но оно интуитивно кажется вполне определенным. К сожалению, для решения некоторых задач не существует алгоритма. Установление таких фактов требует введение строгого понятия алгоритма.
Мы будем рассматривать алгоритмы, имеющие дело только с натуральными числами. Можно доказать, что это не является потерей общности, так как объекты другой природы можно закодировать натуральными числами. Для пользователей компьютеров такое утверждение должно быть очевидным.
Пусть Í обозначает множество натуральных чисел {0,1,2,...}. Объекты, которые мы будем рассматривать будут функциями с областью определения DfÍ Ík (k - целое положительное число) и с областью значений Rf Í Í. Такие функции будем называть k-местными частичными. Слово "частичная" должно напомнить о том, что функция определена на подмножестве Ík (конечно, в частном случае может быть Df = Ík, тогда функция называется всюду определенной).
Назовем k-местную частичную функцию f: Ík à Í эффективно вычислимой (или просто вычислимой), если существует алгоритм, который вычисляет f. Этот алгоритм должен удовлетворять следующим критериям:
1. Если на вход алгоритма поступил вектор x = <x1, x2, ..., xk> из Df, то вычисление должно закончиться после конечного числа шагов и выдать f(x).
2. Если на вход алгоритма поступил вектор x, не принадлежащий области определения Df, то алгоритм никогда не заканчивается.
Множество эффективно вычисляемых функций мы не отождествляем с множеством "практически вычисляемых" функций, так как не накладываем на первое множество никаких ограничений, связанных с современными вычислительными машинами.
Хотя каждое входное натуральное число, должно быть конечным, тем не менее не предполагается верхняя граница размера этого числа, так, например, количество цифр числа может быть больше числа электронов во Вселенной. Точно также, нет никакой верхней границы на число шагов, которые может сделать алгоритм для конкретных x из области определения.
Должно быть совершенно ясным, что предыдущее определение вычислимой функции не является формальным, поэтому мы собираемся дать строгое определение нового множества функций, которое в некотором смысле будет совпадать с множеством вычислимых функций. Мы дадим три различные формализации понятия алгоритма.
Все должно быть изложено так просто, как только возможно, но не проще.
Альберт Эйнштейн