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

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

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

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

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

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

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

Исходные данные: 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 и алгоритма НОД этот процесс можно описать так: