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

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

¶Основные понятия

Алгоритм описывается на некотором формальном или естественном языке. Элементарные действия, допустимые в рамках алгоритма, называются базовыми операциями. Способы записи алгоритмов включают:

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

Алгоритм работает с данными, принимая их на входе и выдавая результат на выходе. Промежуточные величины хранятся в переменных. Управляющие конструкции — ветвление, цикл и последовательность — обеспечивают логику выполнения.

¶История

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

Классические индийские математики V—VII веков внесли значительный вклад: Ариабхата предложил алгоритм извлечения квадратного корня, Брахмагупта — правила вычисления с нулём. Аль-Хорезми в трактате «Об индийском счислении» (IX век) описал процедуру сложения и умножения многозначных чисел, а также метод решения линейных и квадратных уравнений.

В XVI—XVII веках алгоритмическое мышление развивали Франсуа Виет и Рене Декарт. В XIX веке Чарльз Бэббидж спроектировал аналитическую машину — механический компьютер, программируемый с помощью перфокарт, воплощавший идею универсального алгоритма.

¶Формализация

В XX веке были предложены математические модели вычислимости, определившие, что именно считается алгоритмом:

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

¶Классификация

Алгоритмы разделяют по нескольким признакам:

• По структуре: линейные (прямая последовательность), ветвящиеся (с условием), циклические (повторение шагов);
• По способу обработки данных: последовательные, параллельные, распределённые;
• По назначению: сортировки, поиска, сжатия данных, шифрования, машинного обучения;
• По детерминированности: детерминированные и вероятностные (с использованием случайных чисел).

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

Эффективность алгоритма оценивается через понятие сложности. Различают временную сложность (число операций в зависимости от размера входных данных) и пространственную (объём памяти). Сложность выражается в big O-нотации, например O(n), O(n log n), O(n²). Среди классов сложности выделяют P (решаемые за полиномиальное время), NP (решаемые за полиномиальное время при наличии сертификата решения) и NP-полные задачи. Отношение P = NP остаётся одной из главных открытых проблем математики.

¶Примеры классических алгоритмов

• Алгоритм Евклида — нахождение наибольшего общего делителя;
• Бинарный поиск — поиск элемента в отсортированном массиве за O(log n);
• Быстрая сортировка (Хоар, 1960) — сортировка массива в среднем за O(n log n);
• Алгоритм Дейкстры — поиск кратчайшего пути в графе с невесомыми рёбрами;
• RSA (Ривест, Шамир, Адлеман, 1977) — асимметричное шифрование;
• Обратное распространение ошибки — обучение нейронных сетей.

¶Применение

Алгоритмы лежат в основе информатики и применяются повсеместно: в операционных системах, поисковых системах, системах навигации, финансовых транзакциях, медицинской диагностике, прогнозировании погоды. В России разработка алгоритмов ведётся в ведущих вузах (МГУ, МФТИ, СПбГУ, ВШЭ) и технологических компаниях. Отдельное направление составляют криптографические алгоритмы, обеспечивающие безопасность данных, в том числе отечественные стандарты шифрования (ГОСТ Р 34.12-2015 «Кузнечик» и «Магистраль»).

¶Критика

Термин «алгоритм» в последние десятилетия широко используется в маркетинговых и публицистических контекстах для обозначения любых упорядоченных процедур, в том числе неформализованных. Специалисты отмечают размывание строгого значения термина за пределами математики и программирования.

¶Источники

• Кларк Д., Форд Д., Форсайт А. «Алгоритмы: построение и анализ»
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
• Новиков Л. «Алгоритмы: создание и анализ»
• Энциклопедия «Кругосвет» — статья «Алгоритмы»
• Википедия — статьи «Алгоритм», «Теория алгоритмов», «Вычислимость»