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

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

1. Правила выполнения арифметических действий над числами.

2. Правило отыскания наибольшего общего делителя (алгоритм Евклида).

3. Правило извлечения квадратного корня.

4. Правило отыскания решений квадратного уравнения.

5. Правило отыскания производной многочлена n-ой степени.

6. Правило интегрирования рациональной функции.

В каждом из приведенных примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так, в задаче отыскания решения квадратного уравнения ах + bx + с =- 0 участвует три параметра а, b и с; меняя их, получаем различные задачи одного класса.

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

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

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

Отметим характерные черты понятия алгоритма.

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

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

3. Элементарность шагов алгоритма. Закон получе­ния последующей системы величин из предшествующей должен быть простым.

4. Массовость алгоритма. Начальная система величин может выбираться из некоторого потенциально бесконечного множества.

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

Алгоритмы, в которых основную роль играют математические действия, называются численными алгоритмами. От численных алгоритмов отделяют логические алгоритмы игр. В качестве примера, дающего логичес­кий алгоритм, рассмотрим следующую игру.

Имеется 15 предметов. В игре участвуют двое: начи­нающий и противник. Каждый игрок по очереди берет один, два или три предмета. Выигрывает тот, кто берет последний предмет. Какой стратегии в игре должен придерживаться начинающий, чтобы выиграть?

Выигрышная стратегия начинающего может быть описана в форме следующей таблицы:

Действительно, в итоге такой стратегии начинающий возьмет

3 + (4 - n) + (4 - m) + (4 - p) = 15 - (n + т + p) предметов, а противник возьмет n + m + p предметов, т.е. в сумме они возьмут 15 предметов, и последний предмет будет взят начинающим.

Слово «алгоритм» происходит от имени узбекско­го математика XIII века Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси. Оно претерпело эволю­цию: ал Хорезми - ал Горезми - алгоритм.