Шаг 2.
Основные понятия теории алгоритмов.
Основные свойства алгоритма

    На этом шаге мы рассмотрим основные свойства алгоритма.

    Приведем перечень наиболее важных свойств алгоритма.

    Дадим краткую характеристику каждого свойства.

    Дискретность означает, что алгоритм состоит из конечного числа описаний шагов и эти шаги выполняются в дискретном времени, т. е. любые два последовательных шага разделены при исполнении конечным, ненулевым отрезком времени. Можно считать, что шаги выполняются мгновенно в моменты времени t0, t1, t2, ... -, а между этими моментами ничего не происходит.

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

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

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

    Массовость означает, что входные данные для алгоритма могут выбираться из некоторого множества значений. Если же входные данные уникальны, то алгоритм в силу свойства определенности (детерминированности) будет давать всегда один и тот же результат и само построение алгоритма теряет смысл.

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

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

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

    Замечание об определенности и конечности: иногда считают, что алгоритм может заканчиваться без получения результата (безрезультатная остановка) или даже не заканчиваться вовсе при некоторых исходных данных (неприменимость к этим исходным данным). Взгляд на это с точки зрения теории - машины Тьюринга - обсудим позже. С практической точки зрения такая ситуация тоже требует внимания: операционная система (ОС) вычислительной машины, являясь совокупностью алгоритмов, при нормальной работе не предполагает остановки и выдачи каких-либо результатов; она лишь добросовестно получает периодически входные данные-задания и запускает их; задания-алгоритмы сами получают результаты. Таким образом, ОС не выдает продукции, если не считать протокола ее работы. Другие диалоговые программные системы также требуют для своего описания более широкой интерпретации понятия алгоритма: они не получают входные данные сразу и не всегда можно говорить об априорной ограниченности объема данных некоторой константой. Однако все сказанное не умаляет важности приведенного понятия алгоритма, а говорит лишь о богатстве проблематики компьютерных наук.

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

    Если есть текст некоторого предписания, то нужно убедиться в том, что это предписание является алгоритмом. Для этого необходимо проверить, выполняются ли перечисленные выше свойства.

    Рассмотрим такую проверку на примере следующего текста (отыскание максимального и минимального элементов массива):

    «Исходные данные - положительное число N, определяющее количество элементов массива A, и целочисленные элементы A[1], A[2], ..., A[N] массива A. Значения всех чисел находятся в пределах непосредственно представимых в вычислительной машине. Кроме исходных данных вводятся целочисленные переменные Max, Min, i. Первые две по окончании работы алгоритма определяют его результаты, третья является вспомогательной. Действия алгоритма состоят в выполнении следующих шагов:

  1. Установить значения Мах = A[1], Min = A[1], i = 2.
  2. Пока i <= N повторять шаги с 3 по 5.
  3. Если Мах < A[i], то положить Мах = A[i].
  4. Если Мin > A[i], то положить Мin = A[i].
  5. Увеличить i на 1.
  6. Вывести результаты Мах и Min.
  7. Остановиться».

    Проверим выполнение основных свойств.

    Дискретность очевидна.

    Элементарность шагов. Шаг 1 содержит три присваивания значений; шаг 2 содержит одно сравнение чисел; шаги 3-5 содержат два сравнения чисел, два присваивания значений (выполняется каждый раз только одно из них), одно увеличение значения на единицу; шаг 6 - вывод на экран или на печать данных ограниченного объема.

    Определенность. Каждый шаг и алгоритм в целом заканчивается определенным результатом; строго определена последовательность шагов.

    Конечность. Шаги 1 и 6 выполняются по одному разу. Количество выполнений шагов 2-5 зависит от значений переменной i и уровня N. Поскольку i монотонно возрастает, то ее значение достигнет уровня N через конечное число шагов. Если начальное значение переменной i больше уровня N, то шаг 2 выполняется один раз, а шаги 3-5 не выполняется ни разу. Таким образом, в любом случае выполнение алгоритма завершится через конечное число шагов.

    Массовость. Алгоритм может воспринимать в качестве исходных данных различные массивы разной длины.

    Однако не всегда так легко доказать выполнимость основных свойств алгоритма. Особенно это касается свойства конечности. Рассмотрим, например, алгоритм с одним входным аргументом - натуральным числом k.

  1. Если k = 1, то остановиться.
  2. Если k четное, то положить k = k/2; если k нечетное, то положить k = 3k+1.
  3. Повторить, используя новое значение 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).

    На следующем шаге мы рассмотрим понятие исполнителя алгоритма.




Предыдущий шаг Содержание Следующий шаг