8_Теория алгоритмов. (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004)

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

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

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

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

Каждый встречается с алгоритмами со школьной скамьи. Правила, по которым выполняются арифметические действия с многоразрядными числами являются простейшими примерами алгоритмов. Сам термин "алгоритм" происходит от имени средневекового узбекского математика Мухаммеда бен Муса аль Хорезми, который еще в 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.

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

Общие свойства алгоритмов.

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

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

2. Массовость алгоритма: алгоритм служит для решения не какой-то одной задачи, а целого класса однотипных задач. В этом аспекте таблица умножения не является алгоритмом, а умножение столбиком многозначных чисел – алгоритм. Например, в алгоритме Евклида числа a и b выбираются из бесконечного (счетного) множества целых чисел.

3. Детерменированность алгоритма: после выполнения очередного этапа однозначно определено, что делать на следующем этапе.

4. Элементарность шагов алгоритма: решение задачи разбивается на этапы, каждый из которых должен быть простым и локальным. Это означает, что соответствующая операция должна быть элементарной для исполнителя алгоритма (человека или машины). Например, встречающиеся в алгоритме Евклида операции сравнения, вычитания и перестановки чисел достаточно стандартны и привычны. В то же время сам алгоритм Евклида может фигурировать в качестве элементарной операции более сложного алгоритма.

5. Результативность алгоритма: алгоритм через конечное число шагов должен привести к остановке, которая свидетельствует о достижении требуемого результата. Так при поиске пути в лабиринте остановка наступает либо на достижимой площадке, либо при возвращении на исходную площадку, если указанная цель не достижима. В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, обязан показать, что алгоритм останавливается после конечного числа шагов (как говорят, сходится) для любого x из области задания f. Однако проверить результативность (сходимость алгоритма) гораздо труднее, чем другие его свойства.

Способы задания алгоритмов

Алгоритм может быть задан в следующем виде:

1. в вербальной (словесной) форме;

2. в виде ЛГСА (логически графическая схема алгоритма) – в графической форме в виде блок-схемы;

3. в виде структурограммы Насси-Шнейдермана;

4. в виде программы для ЭВМ.

Блок-схема это графическое изображение алгоритма. При её построении содержимое каждого шага алгоритма записывается в произвольной форме внутри блока, представленного геометрической фигурой. Порядок выполнения шагов указывается с помощью стрелок, соединяющих блоки. Использование различных геометрических фигур отражает различный характер выполняемых действий. Размеры фигур и их вид регламентированы ГОСТ 19.003-80 или ISO 1028-73.

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

В ромб (блок сравнения) записывают условия подлежащие проверке с целью выбора варианта продолжения вычисления.

Параллелограмм (блок ввода-вывода) содержит информацию о входных и выходных данных.

Овал означает начало или окончание вычислительного процесса.

Наиболее часто употребляемые символы ЛГСА

В блок-схеме алгоритма вершинам соответствуют шаги алгоритма, а ребрам – переходы между шагами. Вершины в блок-схеме может быть двух видов: вершины, из которых выходит одно ребро, (их называют операторами) и вершины, из которых выходит два ребра, (их называют логическими условиями и предикатами). Кроме того, имеется единственный оператор конца, из которого не выходит ни одного ребра и единственный оператор начала.

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

На блок-схеме хорошо видна разница между описанием алгоритма и процессом его реализации. Описание – это граф, процесс реализации – это путь в графе. Различные пути в одном и том же графе возникают при различных данных, которые создают разные логические условия в точках принятия решения (в точках ветвления). Отсутствие сходимости означает, что в процессе вычисления не появляется условий ведущих к концу алгоритма и процесс зацикливается.

При всей наглядности языка блок-схем следует учитывать, что она отражает связи между отдельными блоками по управлению, а не по информации. Блок-схема лишь указывает, что делать в следующий момент, какому блоку передается управление. Блок-схемы не содержат сведений ни о данных, ни о памяти, ни об используемых наборах элементарных шагов. По существу блок-схемы это не язык, а средство для описания детерминизма алгоритма. Как и все графические модели, это достаточно удобное и наглядное средство. Необходимо помнить, что точки ветвления могут быть не только двоичными (выбор из двух возможных вариантов в зависимости от истинности или ложности логического условия), но и многозначными (выбор одного ветвления из нескольких возможных). Важным является возможность выбора единственного пути при наличии нескольких возможных.

8.2 Формализация понятия алгоритма. Универсальные модели алгоритмов.

Интуитивное понятие алгоритма обладает целым рядом недостатков. Очевидно, что такие понятия, использованные при описании общих свойств алгоритмов, как элементарность шагов, сами нуждаются в уточнении. Очевидно, что их словесные определения будут содержать новые понятия, которые снова потребуют уточнения и т.д. Начиная с 30-х годов, было предложено несколько уточнений понятия алгоритма. Считается, что все они достаточно полно отражают основные черты интуитивного понятия алгоритма. Действительно, все формальные определения алгоритма в некотором смысле эквивалентны друг другу. Поэтому в теории алгоритмов применяется другой подход: выбирается конечный набор исходных объектов, которые объявляются элементарными и конечный набор способов построения их них новых объектов. Этот метод был уже использован в теории множеств и получил название конструктивного подхода.

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

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

Второй тип модели связан с развитием вычислительной техники и основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный дискретный момент времени весьма примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эвристика этой модели близка к ЭВМ и, следовательно, к инженерной интуиции. Основной теоретической моделью этого типа является созданная в 30-х годах концепция машины Тьюринга. Именно машина Тьюринга явилась моделью современной ЭВМ и способствовала развитию современной вычислительной техники.

Наконец, третий тип алгоритмических моделей – это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части слова (подслова) другим словом. Преимущества этого типа моделей заключаются в максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной, не обязательно числовой природы. Примерами моделей этого типа являются канонические системы Поста и нормальные алгоритмы Маркова. При этом общность формализации в конкретной модели не теряется и доказывается сводимость одних моделей к другим, т.е. показывается, что всякий алгоритм, описанный средствами одной модели, может быть описан средствами другой.