|
§ 1. Понятие алгоритма и его характерные черты
Слово алгоритм (лат. – algoritmi) произошло от арабского имени средне-азиатского ученого IX века аль-Хорезми (полное имя – Абу Абдалла Мухаммед бен Муса аль Хорезми аль Меджуси). Оно претерпело эволюцию: ал Хорезми – ал Горезми – алгоритм.
Понятие алгоритма принадлежит к числу основных понятий математики. Оно прошло большой путь развития. Еще в период зарождения математики в ней стали возникать различные вычислительные процессы чисто механического характера, с помощью которых искомые величины целого класса задач вычислялись последовательно из данных исходных величин по определенным правилам. Со временем такие процессы в математике получили название алгоритмов. Примерами алгоритмов являются:
Правила выполнения арифметических действий над числами.
Правило отыскания наибольшего общего делителя (алгоритм Евклида).
Правило извлечения квадратного корня.
Правило отыскания решений квадратного уравнения.
Правило отыскания производной многочлена n-ой степени.
6. Правило интегрирования рациональной функции.
В каждом из приведенных примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так, в задаче отыскания решения квадратного уравнения ах + bх + с = 0 участвует три параметра а, b и с; меняя их, получаем различные задачи одного класса.
В связи со сказанным можно дать следующее определение понятия алгоритма.
Алгоритмом называется конечный набор правил, позволяющих чисто механически решать любую конкретную задачу из некоторого класса однотипных задач.
Под алгоритмом интуитивно понимается некоторое формальное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату.
Возникает вопрос: так ли уж важно и необходимо иметь точное определение алгоритма, если и без него возможно составление и применение алгоритмов (причем даже без употребления самого термина)? Тем более что интуитивное понятие алгоритма хотя и не обладало строгостью, но было настолько ясным, что практически до ХХ в. не возникало ситуаций, когда математики разошлись бы в суждениях относительно того, является ли алгоритмом тот или иной конкретный процесс. Положение существенно изменилось в начале ХХ в., когда были сформулированы такие проблемы, алгоритмическое решение которых было не очевидным. Действительно, для доказательства существования алгоритма необходимо просто решить данную задачу, пользуясь набором известных приемов, или в их отсутствии предложить новые приемы. В таких ситуациях достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Гораздо сложнее доказать факт невозможности построения алгоритма решения некоторой задачи (или класса задач), без точного определения алгоритма эта проблема теряет смысл.
Другим основанием, потребовавшим построения точного определения алгоритма, явилась неопределенность понятия «элементарность шага» при выполнении алгоритмических действий. Пока математика изучала числовые объекты, действия с ними сводились к некоторой последовательности вычислительных операций, а элементарными считались арифметические операции, а также несколько логических, связанных с проверкой отношений между величинами, (равенство, неравенство, больше, меньше, и др.). Однако позднее математика перешла к исследованию свойств и действий со сложными объектами – векторами, матрицами, множествами, функциями – и понятие элементарности шага алгоритма перестало быть очевидным. Например, можно ли считать элементарным шагом взятие интеграла или транспонирование матрицы?
В тех ситуациях, когда задача допускает построение нескольких алгоритмов решения, с теоретической и практической точек зрения оказывается существенным вопрос их сопоставления и выбора наиболее эффективного, что также невозможно без строгого определения алгоритма. Таким образом, возникла необходимость в точном определении понятия «любой алгоритм», т.е. максимально общем определении, под которое подходили бы все мыслимые виды алгоритмов. В 20-е гг. ХХ в. построение определения алгоритма стало одной из центральных математических проблем. Определение это, с одной стороны, должно было соответствовать сущности интуитивного понятия алгоритма, а с другой стороны, быть формально строгим. Попытки формулировки такого понятия привели к появлению в 30-е гг. ХХ в. теории алгоритмов как самостоятельной науки, которая вместе с математической логикой изучает основные средства математики – методы доказательств, способы построения аксиоматических теорий, свойства математических процедур и пр. В 40-е – 50-е гг.началось бурное развитие вычислительной техники и наук, связанных с ее функционированием и использованием, и выяснилось, что в основе этих наук лежит теория алгоритмов, поскольку компьютер может реализовать только такие процедуры, которые представимы в виде алгоритмов. Любая программа есть не что иное, как запись алгоритма на языке, который может «понять» исполнитель – компьютер. Таким образом, уточнение понятия алгоритма с практической точки зрения является важной задачей.
В теории алгоритмов интуитивно-содержательное понятие алгоритма уточняется в строгих понятиях «рекурсивная функция», «машина Тьюринга», «нормальный алгоритм» и др.
Отметим характерные черты понятия алгоритма.
Do'stlaringiz bilan baham: |
