§1. Понятие алгоритма. Примеры. Способы задания. Общие свойства. Необходимость математического уточнения понятия алгоритма

1.1.Понятие алгоритма

Понятие алгоритма такое же древнее, как и сама математика. Хотя в современной науке это понятие вышло за рамки математики, до двадцатого столетия оно ассоциировалось с только математическими проблемами. Оно является фундаментальным понятием так же, как понятие «число» или «множество». Его можно пояснить лишь на конкретных примерах. Вместо слова «алгоритм» мы часто употребляем, такие синонимы как «метод», «способ», «правило». Например, метод Гаусса, правило сложения двух обыкновенных дробей, правило буравчика, правила дорожного движения и т.д.

На интуитивном уровне сущность алгоритма разные источники разъясняют примерно одинаково:

[8]. «Алгоритм – точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного и направленный на получение полностью определенного этим исходным данным результата… Вообще говоря, не предполагается, что результат будет обязательно получен: процесс применения алгоритма к конкретному исходному данному может оборваться безрезультатно или же продолжаться бесконечно».

[7]. «В математике принято понимать под «алгоритмом» точное предписание, определяющее вычислительный процесс, ведущих от варьируемых исходных данных к исходному результату.»

[10]. «Алгоритм – это детерминированная процедура, которую можно применить к любому элементу некоторого класса символических входов, которая для каждого такого входа дает, в конце концов, соответствующий символический выход».

[12]. «Алгоритм – точное предписание о выполнении в определенном порядке некоторой системы операций, позволяющее решать совокупность задач определенного класса».

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

Пример 1. Греческий астроном и географ из Александрии Эратосфен около 2000 лет назад предложил следующий метод отыскания простых чисел в натуральном ряду:

а) Обозревай натуральные числа в порядке возрастания, найди самое меньшее не вычеркнутое число, большее единицы. Пусть это p>1. Оно простое. Далее переходи к следующему указанию.

б) Вычеркивай все числа кратные p и переходи к выполнению указания а) начиная с числа p+1.

Несмотря на древность изобретения Эратосфена, современные электронно-вычислительные машины пользуются этим методом при пересчете простых чисел в заданном промежутке.

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

а) Обозревай заданные два числа a и b. Переходи к следующему указанию.

б) Сравни обозреваемые числа a=b, a<b, a>b. Переходи к следующему указанию.

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

г) Если a<b, то переставь их местами и переходи к следующему указанию.

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

Каковы бы ни были два числа a и b, за конечное число применений а) – д), всегда получим желаемый результат.

Пример 3. Арифметические действия сложения, вычитания, умножения и деления над числами в десятичном счислении.

Пример 4. Извлечение квадратного корня из положительного действительного числа, заданного в десятичном счислении.

Пример 5. Восьмого августа 1900 года в Париже на втором международном конгрессе математиков выдающийся немецкий математик Давид Гильберт выступил с часовым докладом под названием «математические проблемы», где сформулировал 23 проблемы, которые предопределили направление развития математики в XX столетии. Проблема под номером 10 касалась разрешимости алгебраических уравнений от любого числа переменных в целых числах: требуется выработать алгоритм, позволяющий для любого полинома с рациональными коэффициентами

выяснить, имеет ли он целочисленное решение <m₁,m₂,…,m_n> или нет.

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

Пример 6. Более частная проблема – задача отыскания целых корней алгебраических уравнений n-ой степени с одним неизвестным и с целыми коэффициентами.

P(x)= a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀=0 (1)

где a_n=1, решается просто. Для этого достаточно руководствоваться следующими указаниями:

а) Найти все делители свободного члена. Пусть это m₁,m₂,…,m_r и они расположены в порядке возрастания абсолютных величин. Переходи к следующему указанию.

б) Подставь каждый из делителей m_i (в порядке возрастания) в P(x) вместо x и вычисли его значение. Переходи к следующему указанию.

в) если хотя бы при одном 0< i  r P(m_i)=0, то m_i – целый корень P(x). В противном случае уравнение (1) целых корней не имеет.