Алгоритм — понятие, свойства, история¶
Алгоритм — конечная последовательность точно определённых инструкций, выполняемых для решения определённой задачи или достижения заданной цели. Термин происходит от имени персидского математика IX века Мухаммада ибн Мусы аль-Хорезми (латинизированное Algoritmi), чьи труды по вычислениям были основой европейской математической традиции. В современном понимании алгоритм — центральное понятие математической логики, теории вычислений и информатики.
¶Свойства алгоритмов
Классическое определение алгоритма, сформулированное в работах Андрея Андреевича Маркова-старшего и Андрея Николаевича Колмогорова, выделяет следующие свойства:
- Дискретность — алгоритм состоит из отдельных дискретных шагов (действий).
- Детерминированность — каждый шаг определён однозначно; результат не зависит от внешних условий.
- Конечность — выполнение завершается за конечное число шагов.
- Массовость — применим к классу задач, а не к единичной.
- Результативность — применение алгоритма к допустимым данным приводит к получению результата.
- Понятность — исполнителю ясно, как выполнить каждый шаг.
¶История
Понятие алгоритма предшествует самому термину. Египетские папирусы III тысячелетия до н. э. содержат описания процедур вычисления площадей и объёмов. Вавилонские таблички II тысячелетия до н. э. содержат пошаговые процедуры решения квадратных уравнений.
Термин «алгоритм» закрепился в европейской науке после перевода трактата «Об индийском счислении» («De numero indorum»), приписываемого аль-Хорезми. В XIII веке алгоритмами называли любые точные вычислительные процедуры, в частности таблицы арифметических действий.
В XIX веке математики начали формализацию понятия. Готлоб Фреге, Джузеппе Пеано, Дэвид Гильберт и другие разрабатывали аксиоматические основания математики. В 1928 году Гильберт и Вильгельм Акерманн поставили проблему разрешимости: существует ли общий алгоритм, определяющий, является ли формальное высказывание истинным.
В 1936 году Алан Тьюринг ввёл абстрактную модель вычислительной машины (машина Тьюринга), а Алонзо Чёрч — лямбда-исчисление. Обе модели формализовали понятие алгоритмически вычислимой функции и доказали неразрешимость проблемы разрешимости. Понятие «алгоритм» получило строгое определение через эти модели.
В СССР в 1930-е годы Вячеслав Сергеевич Стечкин и Андрей Марков сформулировали аксиоматическое определение алгоритма. Понятие «число Маркова» связано с одним из фундаментальных результатов теории алгоритмов.
¶Классификация
Алгоритмы классифицируют по нескольким основаниям:
| Основание | Виды |
|---|---|
| По способу представления | Лексические, графовые, деревья, формулы |
| По структуре | Линейные, ветвящиеся, циклические, рекурсивные |
| По типу исполнителя | Детерминированные, недетерминированные, вероятностные |
| По цели | Поисковые, сортировки, вычислительные, оптимизации |
¶Сложность
Оценка эффективности алгоритма производится через понятие алгоритмической сложности. Наиболее распространена оценка в нотации Большого О (Big O), характеризующая рост времени выполнения или объёма памяти в зависимости от размера входных данных.
Примеры сложности:
- O(1) — константная (доступ к элементу массива по индексу).
- O(log n) — логарифмическая (бинарный поиск).
- O(n) — линейная (линейный поиск).
- O(n log n) — линейно-логарифмическая (быстрая сортировка в среднем случае).
- O(n²) — квадратичная (пузырьковая сортировка).
¶Основные классы алгоритмов
¶Сортировка
Сортировка — упорядочивание элементов последовательности. Известны сотни алгоритмов сортировки: пузырьковая, вставками, выбором, быстрая (Хоара), слиянием (Джон фон Нейман), поразрядная (Лео Бэчер), пирамидальная (Джон Уильямс), интросортив.
¶Поиск
Линейный поиск последовательно проверяет элементы. Бинарный поиск требует упорядоченной последовательности и делит область поиска пополам на каждом шаге, обеспечивая сложность O(log n).
¶Графовые алгоритмы
Обход графа в ширину и глубину, алгоритм Дейкстры (кратчайший путь), алгоритм Крускала и Прима (минимальное остовное дерево), алгоритм Флойда — Уоршелла (все пары кратчайших путей), топологическая сортировка.
¶Численные алгоритмы
Метод Ньютона нахождения корней, метод Гаусса решения систем линейных уравнений, метод Эйлера и метод Рунге — Кутты решения дифференциальных уравнений, алгоритм Евклида (наибольший общий делитель).
¶Применение
Алгоритмы лежат в основе программного обеспечения, операционных систем, баз данных, сетевых протоколов, компиляторов. Вне информатики алгоритмические идеи применяются в генетике (выравнивание последовательностей), лингвистике, криптографии, экономике (теория игр), робототехнике и искусственном интеллекте.
¶Интересные факты
- В 1936 году Тьюринг доказал, что не существует универсального алгоритма, определяющего, завершится ли выполнение произвольной программы (проблема остановки).
- В 1971 году Стивен Кук сформулировал проблему P = NP — одну из семи задач тысячелетия Института Клэя, оставшуюся нерешённой.
- В 2006 году российский математик Григорий Перельман отказался от премии за решение гипотезы Пуанкаре, доказательство которой опирается на геометрические алгоритмы.
Источники:
- Кнут Д. «Основы программирования» (The Art of Computer Programming).
- Колмогоров А. Н. «О понятии алгоритма» (Успехи математических наук, 1953).
- Марков А. А. «Теория алгоритмов» (Труды МИАН, 1951).
- Тьюринг А. «On Computable Numbers» (1936).
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ».