Лекция: Понятие алгоритма

Единого точного определения термина «Алгоритм» не существует. Разные источники дают его по-разному. Самое простое определение:

Алгоритм — это описание последовательности действий, приводящих к требуемому результату.

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

Алгоритм — это формализованное описание конечной последовательности дискретных, однозначно определенных действий, приводящих к требуемому результату.

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

Подавляющее большинство алгоритмов, особенно научно-технических, оперируют с данными. Данные — это информация, представленная в форме, пригодной для алгоритмической обработки. Входные данные поставляются в алгоритм извне и обрабатываются им, превращаясь в выходные данные – результат работы алгоритма. В интерактивных алгоритмах входные данные вводятся неоднократно, часто в зависимости от промежуточных результатов. Все игровые программы основаны на интерактивных алгоритмах. В не интерактивных (линейных, алгоритмах типа «вход-выход») входные данные вводятся однократно и автоматически преобразуются в выходные, образуя в процессе преобразования промежуточные или внутренние данные. Понятие данных позволяет увидеть разницу между алгоритмом и компьютерной программой (которая записывается на «алгоритмическом» языке). По определению Н.Вирта [1], программа = алгоритм + структуры данных. Иными словами,

компьютерная программа – это описание структур данных и алгоритма их обработки, выполненное на формализованном языке, допускающем автоматическое преобразование в язык машинных команд.

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