На этом шаге мы рассмотрим основные свойства алгоритма.
Приведем перечень наиболее важных свойств алгоритма.
Дадим краткую характеристику каждого свойства.
Дискретность означает, что алгоритм состоит из конечного числа описаний шагов и эти шаги выполняются в дискретном времени, т. е. любые два последовательных шага разделены при исполнении конечным, ненулевым отрезком времени. Можно считать, что шаги выполняются мгновенно в моменты времени t0, t1, t2, ... -, а между этими моментами ничего не происходит.
Элементарность шагов означает, что объем работы, выполняемой на любом шаге, мажорируется некоторой константой, зависящей от характеристик исполнителя алгоритмов, но не зависящей от входных данных и промежуточных значений, получаемых алгоритмом. Для численных алгоритмов такими элементарными шагами могут быть, например, сложение, вычитание, умножение, деление, сравнение двух 32-разрядных чисел, пересылка одного числа из некоторого места памяти в другое. К элементарным шагам не относится сравнение двух файлов, так как время сравнения зависит от длины файлов, а длина потенциально неограниченна.
Определенность (детерминированность) алгоритма означает, что для каждого шага могут быть по набору исходных для этого шага данных однозначно вычислены результаты выполнения шага, и эти результаты не зависят ни от каких случайных факторов. Соответственно этому и алгоритм в целом по окончании работы исполнителя выдает вполне определенный результат.
Конечность (финитность) алгоритма означает, что для получения результата нужно выполнить конечное число шагов, т. е. исполнитель в некоторый момент времени останавливается. Требуемое число шагов зависит от входных данных алгоритма и не мажорируется константой.
Массовость означает, что входные данные для алгоритма могут выбираться из некоторого множества значений. Если же входные данные уникальны, то алгоритм в силу свойства определенности (детерминированности) будет давать всегда один и тот же результат и само построение алгоритма теряет смысл.
Понятие данных (значений) - исходных, промежуточных и результата также требует некоторого ограничительного толкования. Наиболее общее интуитивное понимание состоит в том, что данными в алгоритме могут служить самые разнообразные конструктивные объекты.
Конструктивный объект - это строгое математическое понятие. Можно пока считать, что конструктивный объект - это элемент какого-либо конечного множества (например, один из дней недели), либо объект, вычисленный каким-либо алгоритмом. Конструктивными объектами являются символы, логические значения, целые и вещественные числа, представимые в машине, массивы конструктивных объектов. Алгоритм (его текст) также является конструктивным объектом и, значит, может рассматриваться как данные для другого алгоритма: текст программы (алгоритма) является входными данными для программы-транслятора.
Таким образом, понятия алгоритма и данных двойственны, их определения рекурсивны: в формулировке понятия алгоритма использовались понятия данных, а они, в свою очередь, определяются с использованием понятия алгоритма, и т. д. Это определяет равную важность двух понятий в компьютерных науках, что отражается и в современных языках программирования.
Замечание об определенности и конечности: иногда считают, что алгоритм может заканчиваться без получения результата (безрезультатная остановка) или даже не заканчиваться вовсе при некоторых исходных данных (неприменимость к этим исходным данным). Взгляд на это с точки зрения теории - машины Тьюринга - обсудим позже. С практической точки зрения такая ситуация тоже требует внимания: операционная система (ОС) вычислительной машины, являясь совокупностью алгоритмов, при нормальной работе не предполагает остановки и выдачи каких-либо результатов; она лишь добросовестно получает периодически входные данные-задания и запускает их; задания-алгоритмы сами получают результаты. Таким образом, ОС не выдает продукции, если не считать протокола ее работы. Другие диалоговые программные системы также требуют для своего описания более широкой интерпретации понятия алгоритма: они не получают входные данные сразу и не всегда можно говорить об априорной ограниченности объема данных некоторой константой. Однако все сказанное не умаляет важности приведенного понятия алгоритма, а говорит лишь о богатстве проблематики компьютерных наук.
Алгоритм является предписанием, а наличие предписания предполагает, что результат будет получен неким исполнителем, действующим по этому предписанию. Исполнитель (компьютер или программист, вручную отлаживающий свою программу) получает предписание и исходные данные. После этого он начинает действовать как автомат, т.е. выполнять в реальном времени описанные в алгоритме шаги. В результате выполнения каждого шага могут образовываться промежуточные результаты, которые исполнитель должен где-то фиксировать так, чтобы они могли быть использованы в качестве исходных данных для следующего шага. Исполнитель совершит конечное число шагов (даже если отдельные описания шагов использовались неоднократно) и после этого остановится, зафиксировав окончательный результат подобно промежуточным результатам.
Если есть текст некоторого предписания, то нужно убедиться в том, что это предписание является алгоритмом. Для этого необходимо проверить, выполняются ли перечисленные выше свойства.
Рассмотрим такую проверку на примере следующего текста (отыскание максимального и минимального элементов массива):
«Исходные данные - положительное число N, определяющее количество элементов массива A, и целочисленные элементы A[1], A[2], ..., A[N] массива A. Значения всех чисел находятся в пределах непосредственно представимых в вычислительной машине. Кроме исходных данных вводятся целочисленные переменные Max, Min, i. Первые две по окончании работы алгоритма определяют его результаты, третья является вспомогательной. Действия алгоритма состоят в выполнении следующих шагов:
Проверим выполнение основных свойств.
Дискретность очевидна.
Элементарность шагов. Шаг 1 содержит три присваивания значений; шаг 2 содержит одно сравнение чисел; шаги 3-5 содержат два сравнения чисел, два присваивания значений (выполняется каждый раз только одно из них), одно увеличение значения на единицу; шаг 6 - вывод на экран или на печать данных ограниченного объема.
Определенность. Каждый шаг и алгоритм в целом заканчивается определенным результатом; строго определена последовательность шагов.
Конечность. Шаги 1 и 6 выполняются по одному разу. Количество выполнений шагов 2-5 зависит от значений переменной i и уровня N. Поскольку i монотонно возрастает, то ее значение достигнет уровня N через конечное число шагов. Если начальное значение переменной i больше уровня N, то шаг 2 выполняется один раз, а шаги 3-5 не выполняется ни разу. Таким образом, в любом случае выполнение алгоритма завершится через конечное число шагов.
Массовость. Алгоритм может воспринимать в качестве исходных данных различные массивы разной длины.
Однако не всегда так легко доказать выполнимость основных свойств алгоритма. Особенно это касается свойства конечности. Рассмотрим, например, алгоритм с одним входным аргументом - натуральным числом k.
Как следует из текста алгоритма, имеется некоторый процесс изменения значения k, начинающийся с определенного начального значения, затем на каждом шаге k либо увеличивается, либо уменьшается и, наконец, возможно, приходит к значению 1, на котором и останавливается. В общем случае процесс немонотонный. Например, для k = 40:
k = 40, 20, 10, 5, 16, 8, 4, 2, 1 (8 шагов).
Решить вопрос о конечности данного алгоритма - это значит доказать одно из двух утверждений:
Если k равно степени двойки (2, 4, 8, 16, 32, ...), то процесс будет монотонно убывающим и завершится за число шагов, равное этой степени. В противном случае на некотором промежуточном шаге значение k станет нечетным, но не равным единице, и на следующем шаге значение k увеличится. Оба варианта (алгоритм заканчивается, алгоритм не заканчивается) не кажутся очевидными. С одной стороны, увеличение k происходит в три раза, а уменьшение только в два раза и, если шаги увеличения и уменьшения строго чередуются, то для такого процесса имеется общая тенденция к возрастанию. С другой стороны, за шагом увеличения обязательно следует шаг уменьшения, но обратное неверно, т. е. шагов уменьшения может быть и больше, чем шагов увеличения. Потенциально возможно также зацикливание процесса, когда на очередном шаге получается уже встречавшееся ранее значение. Вот типичный пример с чередованием шагов:
k = 127, 382, 191, 574, 287, 862, 431, 1294, 647, 1942, 971, 2914, 1457, 4372, 2186, 1093, 3280, 1640, 820, 410, 205, 616, 308, 154, 77, 232, 116, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
До значения k = 4372 шаги строго чередуются, затем начинается отрезок нерегулярного изменения, на котором имеется 20 четных и 8 нечетных чисел, и заканчивается процесс «хвостом» из степеней двойки.
Можно показать, что для всех нечетных k = 2j - 1 или даже для k = n2j - 1, где n - нечетное натуральное число, начальный участок последовательности является строго чередующимся до достижения величины 2(n3j - 1); причем длина участка строгого чередования шагов пропорциональна величине j. Это плохая тенденция, поскольку k удаляется от 1. С другой стороны, для многих сочетаний n и j величина n3j - 1 = m2p - пропорциональна степени двойки. В этом случае вслед за возрастанием k идет группа операций деления на 2, «сбрасывающая» значение k до величины m.
В целом вопрос о конечности этого алгоритма должен решаться методами теории чисел. Несмотря на ряд усилий, предпринимавшихся математиками, решение пока не найдено. Более подробный анализ задачи можно найти в книге Ю. Нивергельт, Дж. Фаррар, Э. Рейнгольд «Машинный подход к решению математических задач» (М.: Мир, 1977. С. 298).
На следующем шаге мы рассмотрим понятие исполнителя алгоритма.