База рефератов

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

Рассмотрим подробнее ключевые слова в этой формулировке:

"точное предписание” означает, что предписание однозначно и одинаково понимается всеми исполнителями алгоритма и при одних и тех же исходных данных любой исполнитель всегда получает один и тот же результат;

“из заданного фиксированного множества” означает, что множество действий, используемых в предписании, оговорено заранее и не может меняться в ходе исполнения алгоритма.

“решения всех задач, заданного класса” означает, что это предписание предназначено для решения класса задач, а не одной отдельной задачи. Позднее мы подробнее рассмотрим смысл выражения “класс задач”.

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

Исходные данные: n, m - натуральные числа

Результат: НОД (n, m) - натуральное число d, такое, что

Алгоритм:

1. Положи a =n, b = m ; (следующий шаг)

2. Сравни a и b ; (следующий шаг)

3. Если a=b, то a - результат; (стоп)

 иначе; (следующий шаг)

4. Если a<b, то поменяй их местами; (следующий шаг)

5. Вычти b из a ; (следующий шаг)

6. Положи a = разность; (перейти к шагу 2)

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

Например:

Сравни a и b ;(следующий шаг)

Все исполнители должны “понимать”, что надо сравнить значения, представленные символами а и b, а не сами символы, и перейти к действию 3.

Положи a = разность; (перейти к шагу 2)

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

Последовательность действий, выполняемых исполнителем, образуют процесс. Назовем этот процесс вычислительным процессом. Например, для случая исходных данных  n=3, m=2 и алгоритма НОД этот процесс можно описать так:

Стоп

Нетрудно видеть разницу между алгоритмом и вычислительным процессом, им порождаемым. Так, например, действие, которое встречается в алгоритме один раз, может быть выполнено несколько раз, а следовательно встретиться неоднократно в описании вычислительного процесса. Примерами такого действия может быть действие 3, либо действие 5, либо 6. В нашем алгоритме, как правило, экземпляры одного и того же действия будут различаться данными (операндами), над которыми совершается это действие. Однако, эти данные могут быть представлены одними и теми же именами.

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

Алгоритм всегда определяет однозначно, какое действие должно быть выполнено следующим, равно как и то, какое действие должно быть выполнено первым. Очередное действие всегда определено однозначно. Именно этой цели служат слова “(cледующий шаг).” Они явно указывают какое действие должно быть выполнено следующим. В силу этого свойства алгоритма, которое называется детерминированность, вычислительный процесс всегда для заданных исходных данных определен однозначно. Таким образом, при одних и тех же исходных данных вычислительный процес будет одним и тем же.

Обычно по умолчанию предполагают “естественный” порядок выполнения действий в алгоритме. Это означает, что если нет явного изменения порядка выполнения действий, то они выполняются последовательно одно за другим, а выполнение алгоритма начинают с первого по порядку действия. Поэтому, в дальнейшем слова “(следующий шаг)” мы будем опускать.

Рассмотрим подробнее понятие действия. В нашем примере присутствуют как минимум два вида действий:

действия над данными (например, сравни, вычти, положи);

действия, изменяющие “естественный” порядок вычислений (например, если - то - иначе; перейди к шагу #).

Если присмотреться внимательней, то мы увидим, что действия вида “сравни”, “вычти” и действия вида “положи ” - это разные действия. Разница между ними в том, что действия первого вида указывают что делать с его операндами, но не указывают где “сохранить” полученный результат. Действия второго вида, наоборот “умалчивают” каким образом получено значение, которое надо “сохранить” в качестве нового значения переменной.

Теперь пристальнее рассмотрим правило окончания алгоритма и выбора результата. В алгоритме могут быть использованы десятки переменных, но результат будет храниться лишь в нескольких. Эти “результирующие” переменные должны быть явно указаны в алгоритме, т.к. в противном случае нет никакой возможности их выявить. Момент, когда в этих переменных сформированы нужные значения, определяет правило окончания алгоритма. Правило окончания всегда формулируется как некоторое условие на множестве текущих значений переменных. Достижение этого условия и означает, что в определенных переменных получен результат. В нашем примере таким условием является равенство текущего значения переменной а текущему значению переменной b.

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

Данные в алгоритме могут быть представлены переменными (в нашем примере именуемые a и b), либо явно, в виде постоянной величины - константы  (в нашем примере n и m), которая не меняет своего значения в конце выполнения алгоритма.

Переменная - это имя, с которым связано конкрентное множество значений. В каждый конкретный момент времени исполнения алгоритма каждая переменная принимает одно конкретное значение, из связанного с ней множества.

Определение 1.1

Типом переменной называется множество возможных ее значений.

Пусть у нас есть множество переменных {vi|i=1,k}.   (Примеры!)

Определение 1.2

Состоянием на множестве переменных {vi|i=1,k} называется набор значений этих переменных.

Пусть А - алгоритм, {vi|i=1,k} - набор всех переменных, используемых в этом алгоритме. Добавим к этому набору еще одну переменную p, тип которой есть множество индексов действий в алгоритме. Каждый шаг исполнения алгоритма можно однозначно охарактеризовать сосотоянием на множестве переменных ({vi|i=1,k},p).

Определение 1.3

Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого алгоритма.

Определение 1.4

Состоянием вычислительного процесса, порожденного алгоритмом А, называется состояние на множестве переменных ({vi|i=1,k},p), где{vi|i=1,k} - набор всех переменных, используемых в алгоритме А.

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

Определение 1.5

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

Определение 1.6

Результат - это определенная совокупность значений из терминального состояния вычислительного процесса алгоритма.

Определение 1.7

Действие - переход из одного состояния в другое.

Действительно, если действие связано с преобразованием каких-либо данных, то правильность этого утверждения очевидна. Если же действие связано с изменением “естественного” порядка выполнения действий в алгоритме, то состояние вычислительного процесса меняется все равно, т.к. изменяется значение специальной переменной  p -  индекс действия.

Рассмотрим еще один пример. Пусть нам надо построить алгоритм для решения следующего класса задач:

вычислить значение выражения    ,  в точке x=b, где

aiÎR, bÎR, где R - множество вещественных чисел.

Множество исходных данных: , где aiÎR, bÎR.

  вектор из n+1 вещественных числа;

b - вещественное число.

Результат b  r:  , где

Переменные: i - типа целый; х, r - типа вещественный.

Константы:{ai|i=1, n+1}, п.

Нетрудно видеть, что мы имеем дело с классом задач. Ниже приведен алгоритм для этого класса задач.

Алгоритм:

Положи i равным п,  x равным b;

Положи r равным ;

Умножь r на x;

Положи r равным произведению;

Положи i равным i -1;

Положи r равным r+ ;

Если i = 0,  то  r - результат

иначе перейди к шагу 3;

Организацию вычислений по  этому алгоритму можно пояснить вот таким выражением:

Этот метод вычисления значения полинома в точке называется схемой Горнера. Однако, есть и другой алгоритм для решения этих задач, который мы назовем прямым.

Исходные данные: те же, что и в предыдущем примере.

Результат: тот же.

Переменные: r, s, x - типа вещественный, i - типа целый.

Константы: , п.

Алгоритм:

Положи i равным п,  s равным 0,  х равным b;

Возведи х в степень i

Умножь  на степень;

Положи s равной сумме s и произведения.

Если i = 0, то s - результат (стоп)

иначе положи i=i -1, перейди к шагу 2.

Организацию вычислений по  этому алгоритму описывает выражение

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

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

Определение 1.8

Сложностью алгоритма называется количество действий в вычислительном процессе этого алгоритма.

Обратите внимание, именно в вычислительном процессе, а не в самом алгоритме.

Для того, чтобы сравнивать сложность разных алгоритмов, надо чтобы она подсчитывалась для них в терминах одинаковых действий. Например, умножь, сложи, положи. Выразим сложность действия возведения в степень  i  как (i - 1) операций умножения. Тогда, сложность первого алгоритма (по схеме Горнера) в виде числа операций сложения и умножения будет равна 2п.  Для прямого алгоритма она будет равна:

Таким образом, первый алгоритм эффек