Алгоритм в информатике¶
Алгоритм — конечная последовательность точно определённых инструкций, выполняемых для решения определённой задачи или достижения заданной цели. Термин происходит от латинизированного написания имени персидского математика аль-Хорезми (Мухаммад ибн Муса аль-Хорезми, IX век), чьи труды по счислению были переведены на латынь в Средние века. В информатике алгоритм является фундаментальной абстракцией: программа представляет собой реализацию алгоритма на конкретном языке программирования, а сам алгоритм существует независимо от языка и аппаратуры.
¶Основные свойства
Классическое определение алгоритма включает пять ключевых свойств, сформулированных в трудах по теории вычислений:
- Дискретность — алгоритм состоит из конечного числа отдельных шагов (действий), каждый из которых выполняется за конечное время.
- Детерминированность — каждый шаг однозначно определяет следующий; для одного и того же набора исходных данных алгоритм выполняется одинаково.
- Полнота — исходные данные и все действия описаны достаточно полно, чтобы результат был получен без обращения к внешним инструкциям.
- Конечность — алгоритм завершается за конечное число шагов для любых допустимых входных данных.
- Результативность — каждый шаг алгоритма применим к допустимым данным и приводит к поставленной цели.
Дополнительно к алгоритму предъявляется требование массовости: он должен решать не одну конкретную задачу, а класс задач, отличающихся только значениями исходных данных.
¶Способы описания
Алгоритм может быть описан несколькими способами, различающимися по степени формализации:
| Способ описания | Характеристика |
|---|---|
| Естественный язык | Неспециализированный текст, допускающий неоднозначность |
| Псевдокод | Обобщённая запись, близкая к программе, но не привязанная к языку |
| Блок-схема | Графическое представление с использованием геометрических фигур |
| Формальная запись | Математическая нотация (лямбда-исчисление, машина Тьюринга) |
| Программа | Реализация на конкретном языке программирования |
Псевдокод и блок-схемы широко используются в обучении и при проектировании, поскольку позволяют отделить логику алгоритма от синтаксиса конкретного языка.
¶Классификация
По структуре алгоритмы делятся на линейные (последовательное выполнение шагов), ветвящиеся (содержат условные переходы) и циклические (включают повторяющиеся фрагменты). По способу получения результата выделяют алгоритмы с прямым ходом (таблицы, формулы), последовательного перебора, деления пополам, динамического программирования, ветвей и границ, «жадные» алгоритмы и алгоритмы с сужением области перебора.
По назначению различают алгоритмы сортировки (пузырьковая сортировка, быстрая сортировка, сортировка слиянием), поиска (линейный поиск, бинарный поиск), математические (нахождение НОД, возведение в степень), строковые, графовые (обход графа в ширину и в глубину, поиск кратчайшего пути) и многие другие.
¶Оценка эффективности
Качество алгоритма оценивается по времени выполнения и объёму используемой памяти. Для этого применяется асимптотическая нотация Большого O, введённая немецким математиком Паулем Бахманом в 1894 году и популяризированная Эдмундом Ландо. Нотация описывает, как растёт время выполнения или потребление памяти при увеличении объёма входных данных.
Типичные оценки сложности:
- O(1) — конечное время, не зависящее от объёма данных (доступ по индексу в массиве).
- O(log n) — логарифмическая сложность (бинарный поиск).
- O(n) — линейная сложность (линейный поиск).
- O(n log n) — линейно-логарифмическая (быстрая сортировка в среднем случае).
- O(n²) — квадратичная (пузырьковая сортировка).
- O(2ⁿ) — экспоненциальная (перебор всех подмножеств).
¶История
Понятие алгоритма как формальной процедуры существовало задолго до появления компьютеров. Египетские и вавилонские математики описывали вычислительные процедуры ещё в III тысячелетии до н. э. Труды аль-Хорезми «Об индийском счислении» и «Книга о восстановлении и противопоставлении» заложили основу алгебры как дисциплины.
В XIX веке немецкий математик и философ Готлоб Фреге ввёл понятие формального языка, а Дэвид Гильберт в 1900 году поставил проблему разрешимости — вопрос о существовании алгоритма, решающего любую поставленную задачу. В 1930-х годах Алан Тьюринг и Алонзо Черч независимо друг от друга дали строгое определение алгоритма: Тьюринг предложил абстрактную вычислительную машину (машина Тьюринга), а Черч — лямбда-исчисление. Тезис Черча — Тьюринга утверждает, что любая эффективно вычислимая функция может быть вычислена алгоритмом на машине Тьюринга.
В 1936 году Курт Гёдель, Алан Тьюринг и другие доказали неразрешимость проблемы остановки: не существует универсального алгоритма, определяющего, завершится ли произвольная программа за конечное время. Это открытие ограничило область применимости алгоритмов и заложило основы теории сложности вычислений.
¶Значение
Алгоритмы лежат в основе всей программной инженерии, информатики и цифровых технологий. Системы поиска в интернете, рекомендательные системы, шифрование данных, маршрутизация сетей, распознавание изображений и языковые модели — всё это реализации конкретных алгоритмов. Понимание алгоритмов и методов оценки их эффективности является базовым навыком программиста и компьютерного учёного.
История: Д. Кнут, «Искусство программирования»; Т. Кормен и др., «Алгоритмы: построение и анализ»; Г. С. Туманов, «Алгоритмы и их реализация»; В. А. Бурков, «Основы математической теории систем».