Свойства алгоритма и их классификация

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

Дискретность

Дискретность (от лат. discretus — разделённый, прерывистый) означает, что алгоритм представляется не как непрерывный процесс, а как последовательность отдельных, строго завершённых шагов (команд, операций). Каждое действие должно быть выполнено полностью прежде, чем начнётся следующее. Алгоритм разбивается на конечное множество элементарных предписаний, каждое из которых выполняется за один такт. Это свойство является фундаментальным, поскольку позволяет формализовать процесс вычисления и поручить его исполнение автоматическому устройству, которое физически не способно выполнять действия «параллельно» в рамках одного шага без специального описания.

Детерминированность (определённость)

Детерминированность подразумевает, что алгоритм не содержит случайных или неоднозначных предписаний. Для одного и того же набора исходных данных алгоритм всегда выдаёт один и тот же результат и проходит через одну и ту же последовательность шагов. Это свойство обеспечивается точностью формулировок: каждая команда должна быть однозначно понятна исполнителю, исключая возможность произвольного выбора. В более строгой трактовке различают понятия «определённость» (отсутствие разночтений в командах) и «детерминированность» (отсутствие случайностей). На практике эти термины часто употребляются как синонимы, хотя в теории вычислимости детерминированные алгоритмы противопоставляются вероятностным и недетерминированным (например, в машинах Тьюринга с недетерминированным выбором перехода).

Результативность (конечность)

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

Массовость

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

Понятность (формальность)

Понятность (или формальность) требует, чтобы алгоритм был записан в терминах команд, входящих в систему команд исполнителя. Исполнитель (человек, автомат, компьютер) должен быть способен выполнить каждую команду строго механически, не внося в неё собственных интерпретаций. Это свойство обеспечивает возможность автоматизации: алгоритм не должен опираться на интуицию, контекст или «здравый смысл» исполнителя. В информатике формальность достигается использованием формальных языков программирования, в которых синтаксис и семантика каждой конструкции строго определены. Отсутствие формальности превращает алгоритм в эвристику или неформальное описание процесса.

Дополнительные свойства

Помимо пяти классических свойств, в современной литературе часто рассматриваются дополнительные характеристики, которые не являются обязательными, но важны для практического применения:

• Корректность — способность алгоритма давать правильный результат для всех допустимых входных данных. Корректность доказывается математически, обычно методом индукции.
• Сложность — оценка требуемых ресурсов (времени и памяти) в зависимости от объёма входных данных. Различают временную и пространственную сложность, выражаемую в нотации «О-большое».
• Устойчивость (робастность) — способность алгоритма корректно обрабатывать некорректные или краевые входные данные (например, пустые массивы, отрицательные значения).
• Адаптивность — способность алгоритма изменять своё поведение в зависимости от свойств входных данных (например, алгоритм быстрой сортировки, переключающийся на сортировку вставками для малых массивов).

Значение свойств алгоритма

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

Нарушение любого из обязательных свойств приводит к тому, что последовательность действий не может считаться алгоритмом. Например, инструкция «налейте немного молока» не является алгоритмом из-за отсутствия детерминированности (понятие «немного» субъективно). Инструкция «переливайте воду из стакана в стакан, пока не надоест» нарушает свойство результативности, так как не определено условие завершения.

Критика и развитие понятия

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

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
• Ахо А., Хопкрофт Дж., Ульман Дж. «Структуры данных и алгоритмы»
• Марков А. А., Нагорный Н. М. «Теория алгорифмов»
• Успенский В. А., Семёнов А. Л. «Теория алгоритмов: основные открытия и приложения»
• Кнут Д. «Искусство программирования»