Открыть сервисСервис

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

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

Свойства алгоритмов

Классическое определение алгоритма выделяет несколько ключевых свойств, сформулированных в работах математиков XX века (в частности, Андрея Колмогорова и Андрея Маркова):

  • Дискретность — алгоритм состоит из отдельных шагов, каждый из которых выполняется последовательно.
  • Детерминированность — для каждого шага заранее известно, какое действие будет выполнено при заданном состоянии.
  • Массовость — алгоритм применим к целому классу задач, а не к единичному случаю.
  • Конечность — выполнение завершается за конечное число шагов.
  • Результативность — каждый алгоритм должен приводить к решению задачи.
  • Входные и выходные данные — алгоритм принимает исходные данные и выдаёт результат.

История

Понятие алгоритма имеет глубокие исторические корни. Ещё в Древней Греции Евклид в III веке до н. э. описал процедуру нахождения наибольшего общего делителя двух чисел — алгоритм Евклида, один из старейших известных алгоритмов, который до сих пор используется в криптографии. В IX веке аль-Хорезми систематизировал методы арифметических вычислений, а его имя стало нарицательным для обозначения вычислительных процедур.

В XVI–XVII веках алгоритмические идеи развивались в связи с созданием логарифмических таблиц и механических счётных устройств. В XIX веке Чарльз Бэббидж и Ада Лавлейс заложили основы программирования, рассматривая вычислительную машину как устройство, исполняющее заданную последовательность операций.

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

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

КлассификацияВиды
По способу представлениясловесные, блок-схемы, программы
По структурелинейные, ветвящиеся, циклические
По области примененияматематические, сортировки, поиска, графовые, численные
По вычислительной сложностис линейной, полиномиальной, экспоненциальной сложностью

Вычислительная сложность

Центральное понятие теории алгоритмов — сложность алгоритма, оцениваемая обычно в зависимости от размера входных данных. Используется нотация «большое О» (O-нотация), введённая Полем Бахманом и популяризированная Дональдом Кнутом. Например, алгоритм сортировки пузырьком имеет сложность O(n²), тогда как алгоритм быстрой сортировки в среднем — O(n log n). Понимание сложности позволяет выбирать наиболее эффективный алгоритм для конкретной задачи.

Примеры

К числу наиболее известных алгоритмов относятся:

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

Алгоритмы в России

В СССР теория алгоритмов активно развивалась в рамках московской математической школы. Андрей Марков-младший ввёл понятие нормальных алгоритмов — формальной модели алгоритма, эквивалентной по выразительной силе машине Тьюринга. Колмогоров и его ученики заложили основы алгоритмической теории информации. В 1960–1970-е годы в СССР были созданы первые отечественные языки программирования и вычислительные машины, реализующие алгоритмические идеи на практике.

Значение

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

Источники:

  • Кнут Д. «Основы программирования»
  • Колмогоров А. Н. «Три подхода к определению понятия «количества информации»»
  • Марков А. А. «Теория алгоритмов»
  • Кормен Т. и др. «Введение в алгоритмы»
  • Тьюринг А. «On Computable Numbers, with an Application to the Entscheidungsproblem» (1936)
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru