Алгоритм — понятие и классификация¶

Алгоритм — это конечная последовательность точно определённых инструкций, предназначенная для решения определённой задачи или класса задач. Термин происходит от имени персидского математика IX века аль-Хорезми (Мухаммад ибн Муса аль-Хорезми), латинизированная форма его имени (Algoritmi) закрепилась в европейской науке. Ключевые свойства алгоритма: дискретность (пошаговое выполнение), детерминированность (однозначность действий на каждом шаге), конечность (завершение за конечное число операций), массовость (применимость к классу задач) и результативность (наличие выхода).

¶История понятия

Понятие алгоритма формировалось на протяжении тысячелетий. Древнеегипетские математики ещё в папирусе Ахмеса (около 1650 года до н. э.) описывали процедуры вычислений. Персидский учёный аль-Хорезми в IX веке разработал систематические методы решения линейных и квадратных уравнений, а его труд «Об исчислении индийцев» познакомил арабский мир с позиционной десятичной системой счисления.

В XIII веке итальянский математик Фибоначчи в «Книге об абаке» описал алгоритм евклидовой арифметики и позиционной записи чисел. В XIX веке немецкий математик Карл Фридрих Гаусс дал строгие алгоритмические описания ряда процедур в теории чисел.

Понятийный аппарат современной теории алгоритмов был создан в 1930-е годы. Алан Тьюринг сформулировал концепцию абстрактной вычислительной машины (машина Тьюринга, 1936), Алонзо Черч ввёл лямбда-исчисление, а Стивен Клейн и Андрей Марков разработали собственные формальные модели. Эти работы заложили основы теории вычислимости.

¶Формальные модели

Для строгого описания алгоритмов используются формальные вычислительные модели:

• Машина Тьюринга — абстрактное устройство, состоящее из бесконечной ленты, головки чтения/записи и конечного набора состояний. Считается универсальной моделью вычислений.
• Лямбда-исчисление — формальная система, основанная на понятих абстрактной функции и её применения, разработанная Алонзо Черчем в 1930-е годы.
• Модель Маркова — нормальная алгоритмическая система, предложенная Андреем Марковым в 1951 году, оперирующая подстановками символов в строки.
• Регистровая машина — абстрактная модель с набором регистров и примитивных операций над ними.

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

¶Классификация алгоритмов

Алгоритмы можно классифицировать по нескольким признакам.

По способу представления:

• словесный — описание на естественном языке;
• блочный — графическое представление в виде блок-схемы;
• программный — запись на языке программирования.

По характеру управления:

• линейные — последовательное выполнение команд без ветвлений;
• разветвляющиеся — с условными переходами;
• циклические — с повторением блоков команд;
• рекурсивные — вызывающие сами себя.

По типу данных:

• числовые — оперируют числами;
• символьные — работают со строками и структурами данных;
• графовые — основаны на операциях с графами.

По области применения:

• поисковые — нахождение элемента в массиве или графе;
• сортировочные — упорядочивание данных;
• математические — вычисления (умножение, нахождение НОД, возведение в степень);
• криптографические — шифрование и проверка подписей.

¶Сложность алгоритмов

Эффективность алгоритма оценивают с помощью понятия алгоритмической сложности. Различают временную сложность (число операций в зависимости от размера входных данных) и пространственную (объём дополнительной памяти).

Сложность выражают в виде функции от размера входа n и записывают в нотации Большого О (Big O). Наиболее распространённые классы:

Задачи, для которых не существует алгоритма полиномиальной сложности, составляют класс NP-полных задач. Наиболее известный открытый вопрос теории вычислимости — проблема P против NP.

¶Невычислимые задачи

Не все задачи допускают алгоритмическое решение. Алан Тьюринг в 1936 году доказал неразрешимость проблемы остановки: не существует универсального алгоритма, который по описанию программы и её входных данных определял бы, завершится ли выполнение за конечное время. К невычислимым также относятся проблема равенства двух лямбда-выражений, проблема непротиворечивости формальных теорий (теорема Гёделя о неполноте) и ряд задач комбинаторики.

¶Применение

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

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

¶Источники

• Клод К. «Введение в теорию алгоритмов и автоматов»
• Кнут Д. «Основы программирования»
• Марков А. А. «Теория алгоритмов»
• Тьюринг А. «On computable numbers» (1936)
• Корнеев Г. А. «Алгоритмы и структуры данных»