Понятие алгоритма принадлежит к числу
основных понятий математики. Оно прошло большой путь развития. Еще в период
зарождения математики в ней стали возникать различные вычислительные процессы
чисто механического характера, с помощью которых искомые величины целого класса
задач вычислялись последовательно из данных исходных величин по
определенным правилам. Со временем такие
процессы в математике получили название алгоритмов. Примерами алгоритмов
являются :
Правила выполнения арифметических действий над числами.
Правило отыскания наибольшего общего
делителя (алгоритм Евклида).
Правило извлечения квадратного корня.
Правило отыскания решений квадратного
уравнения .
В каждом
из приведенных примеров приходится иметь дело с классом однотипных
задач, или, как говорят с массовой проблемой. Задачи такого класса отличаются
друг от друга значениями входящих в них параметров. Так, в задаче отыскания
решения квадратного уравнения
участвует три параметра
; меняя их получаем различные задачи
одного класса.
В связи со сказанным можно дать следующее
определение понятия алгоритма.
Алгоритмом называется общий
единообразный, точно определенный способ решения любой задачи из данной массовой проблемы.
Такое определение нельзя считать строгим. Действительно, в нем встречаются
слова, точный смысл которых не установлен. В частности, это касается слова
«способ». В связи с этим это не строгое определение алгоритма называют
интуитивным.
Отметим основные
характерные черты понятия алгоритма.
1. Массовость – применимость алгоритма не к одной задаче, а к классу задач.
2. Дискретность – четкая разбивка на отдельные этапы (шаги).
3. Детерменированность – такая организация этапов выполнения,
при которой для перехода от одного этапа к другому не приходится прибегать к датчикам
случайных чисел, гаданию на кофейной гуще, подбрасыванию монеты и т.п.
4. Конечность – для получения результата при
применении алгоритма к решению конкретной задачи выполняется конечная
последовательность шагов алгоритма.
Вопросы «Что такое алгоритм?», «Что такое
алгоритмически разрешимые и неразрешимые проблемы?» стали особенно актуальными
в ХХ веке в связи с развитием ЭВМ и естественной потребностью в анализе их
возможностей. теория
алгоритмов была создана совместными (параллельными) усилиями, в основном
американских, английских и советских математиков. Осмысление понятия алгоритм
потребовало и пересмотра многих философских воззрений на мышление как
творческий процесс. Всегда ли, когда человек работает «головой», он думает?
Если часть «головной» работы переложена на машину, то следует ли считать, что
машина думает? Решение этих философских проблем принадлежит одному из
крупнейших математиков ХХ в., основоположнику кибернетики Н. Винеру,
американскому математику Э. Посту и английскому математику А. Тьюрингу.