Понятие алгоритмической системы

Теория алгоритмов.

С давних времен в математике сложилось интуитивное представление об алгоритме как формальном предписании, которое определяет совокупность операций и порядок их выполнения для решения всех задач какого-либо типа.

Для решения ряда однотипных задач иногда целесообразно использовать чисто механические вычислительные процессы. С их помощью искомые величины вычисляются последовательно из данных величин по определенным правилам. Описание таких процессов принято называть алгоритмами. Вообще говоря, под алгоритмом интуитивно понимается некоторое формальное предписание, действуя согласно которому можно получить решение задачи.

Каждый встречается с алгоритмами со школьной скамьи. Правила, по которым выполняются арифметические действия с многоразрядными числами являются простейшими примерами алгоритмов. Сам термин "алгоритм" происходит от имени средневекового узбекского математика Мухаммеда бен Муса аль Хорезми, который еще в IX веке сформулировал такие правила. В своем развитии математика накопила огромное количество различных алгоритмов. Получая соответствующую интерпретацию в конкретных приложениях, они составляют значительную и наиболее существенную часть математического аппарата, используемого в технике.

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

Например великую теорему ферма спустя почти 400 лет доказал великий американский ученый Эндрю Уайлс, американский профессор английского происхождения, о чем он доложил в сенсационном докладе на Международном конгрессе математиков в Цюрихе в 1994 году. Но золотую медаль Филдса за это выдающееся достижение он не смог получить из-за того, что золотые медали Филдса вручаются математикам строго до 40 лет. Как известно, в 1936 году был учрежден аналог Нобелевской премии по математике – золотая медаль Филдса. Ее присуждают раз в четыре года за выдающиеся достижения в математике молодым ученым до 40 лет, пока не пройдет пик творческой активности. Для Эндрю Уайлса решили учредить серебряный знак Филдсовского комитета, который был вручен гениальному ученому на следующем конгрессе математиков в 1998 году в Берлине. Интересно, что за выдающиеся достижения в топологии на следующем конгрессе математиков в Пекине в 2002 году золотая медаль Филдса была вручена американскому профессору русского происхождения Владимиру Воеводскому, 36 лет. Он окончил МГУ, затем аспирантуру Гарвардского университета.

Алгоритмы могут быть численными и логическими. Алгоритмы, которые сводят решение поставленной задачи к арифметическим действиям над числами, называются численными алгоритмами. Типичными примерами численных алгоритмов служат решения следующих задач:

1) Нахождение наибольшего общего делителя двух положительных натуральных чисел (алгоритм Евклида);

2) Извлечение квадратного корня из рационального числа с заданной степенью точности;

3) Вычисление ранга целочисленной матрицы.

Традиционным историческим примером численного алгоритма является алгоритм Евклида для нахождения наибольшего общего делителя двух заданных положительных целых чисел a и b. Алгоритм Евклида состоит из следующей системы последовательных указаний:

1. Обозревай a и b и переходи к следующему;
2. Сравни обозреваемые числа ( a=b, a<b или a>b ), переходи к следующему;
3. Если обозреваемые числа равны, то каждое из них дает искомый результат, если нет – переходи к следующему;
4. Если первое обозреваемое число меньше второго, переставь их местами и переходи к следующему;
5. Вычитай второе число из первого и обозревай два числа – вычитаемое и остаток; переходи к указанию 2.

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