Интуитивное понятие алгоритма

Вопрос 1.

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

Многие годы понятие «алгоритм» использовалось математиками для описания правил решения математических задач. Например, существуют алгоритм вычисления квадратного корня положительного числа, алгоритм нахождения наибольшего общего делителя двух целых чисел.

Однако не следует считать алгоритм чисто математическим понятием. Каждый из нас с раннего детства, даже не замечая этого, ежедневно решает задачи, для описания которых используется тот или иной алгоритм, сформулированный в виде конечной последовательности однозначных предписаний. Например, чтобы приготовить вкусное блюдо, вы раскрываете поваренную книгу, отыскиваете рецепт (иными словами, алгоритм приготовления) и, следуя его конкретным указаниям (на два стакана муки – 250 г масла, 1 яйцо,…, тесто разрезать на полоски …, в духовке 20—25 минут…), за конечное число шагов решаете поставленную перед собой задачу.

Носителями алгоритмов являются рецептурные справочники, инструкции по использованию бытовой и технической аппаратуры, медицинские рекомендации, кулинарные книги и многое другое.

В белорусско-русском терминологическом словаре «Информатика» (авторы Быкодоров Ю.А., Кузнецов А.Т., Павловский А.И., Пономаренко В.К., Морозов А.А.) понятие алгоритма трактуется так: «алгоритм – это конечная последовательность точно сформулированных правил, формальное исполнение которых позволяет за конечное время получить искомый результат, основываясь на варьируемых исходных данных».

Отметим, что все эти фразы не являются определением алгоритма в математическом смысле, а лишь отражают интуитивное понятие алгоритма, сложившееся за долгие годы. Из этого определения вытекают все свойства алгоритмов.

Точное определение понятия алгоритма было разработано в математической логике в 30-40-е годы ХХ века. Примерами могут служить: машина Тьюринга, нормальный алгоритм Маркова, рекурсивные функции и другие. На языке каждой из этих математических теорий можно дать математическое определение алгоритма. Более того, последующая математическая практика показала, что эти определения в некотором смысле эквивалентны.