2. Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Приведенный в примере алгоритм подсчета гласных букв может быть понятен человеку, знающему русский язык. Чтобы этот алгоритм мог быть также выполнен человеком, не знающим русского языка, необходимо записать алгоритм на языке понятном исполнителю, и сообщить ему дополнительные сведения: перечислить явно гласные буквы русского алфавита.
Понятность алгоритма означает знание исполнителя о том, что надо делать для исполнения этого алгоритма.
Таким образом, при формулировке алгоритма необходимо учитывать возможности и особенности исполнителя, на которого рассчитан алгоритм.
3. Алгоритм представлен в виде конечной последовательности шагов. Говорят, что алгоритм имеет дискретную структуру. Следовательно, его исполнение расчленяется на выполнение отдельных его шагов, выполнение каждого очередного шага начинается после завершения предыдущего.
4. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут повторяться многократно. В рассмотренном выше примере многократно повторяются шаги с третьего по шестой. Однако выполнение алгоритма все же закончится за конечное число шагов, так как текст имеет конечную длину и в нем имеется символ @. При чтении этого символа будет выполнен седьмой шаг алгоритма, завершающий его выполнение.
В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Так, можно сформулировать процедуру вычисления числа Пи. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же ее искусственно прервать, например ввести условие завершения процесса вычислений вида: «Закончить вычисления после получения N десятичных знаков числа Пи», то получится алгоритм вычисления N десятичных знаков числа Пи. На этом принципе основано получение многих вычислительных алгоритмов: строится бесконечный, сходящийся к искомому решению процесс. Он обрывается на некотором шаге, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближения зависит от числа шагов.
5. Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен действовать строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие-нибудь действия, отличные от предписанных алгоритмом. Иными словами, алгоритм рассчитан на чисто механическое исполнение. Эта очень важная особенность означает, в частности, что если один и тот же алгоритм поручить для исполнения разным исполнителям, то они придут к одному и тому же результату, лишь бы эти исполнители понимали алгоритм. Именно определенность алгоритма дает возможность поручить его исполнение автомату, не обладающему «здравым смыслом».
B приведенном выше примере, действие перемещения указателя на следующий символ достаточно точно определено, если текст расположен на длинной узкой ленте и вытянут в одну строку (например, напечатан на узкой телетайпной ленте). Если же текст разбит на строки и страницы (т.е. имеет сложную структуру), то действие перемещения указателя на следующий символ уже не является столь очевидным. В этом случае необходимы указания, как поступать исполнителю, когда закончится очередная строка или очередная страница текста.
Таким образом, формулировка алгоритма должна быть так точна, чтобы полностью определять все действия исполнителя.
6. Каждый шаг алгоритма должен быть выполнен точно и за конечное время. В этом смысле говорят, что алгоритм должен бытьэффективным, т.е. действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Поэтому, например, указание вида: «Если любое целое число, большее 6, можно представить в виде суммы трех простых чисел, то счетчик увеличить на 1, иначе счетчик уменьшить на 1» – неэффективно, так как не известен способ доказательства истинности или ложности утверждения, содержащегося в нем. Следовательно, исполнитель не может выполнить этот шаг алгоритма, пока не найдет соответствующего доказательства.
Обычно отдельные указания исполнителю, содержащиеся в каждом шаге алгоритма, называют командами. Таким образом, эффективность алгоритма связана с возможностью выполнения каждой команды за конечное время. Исполнители отличаются друг от друга своими возможностями, т.е. репертуаром команд, которые они «понимают» и могут выполнять. Совокупность команд, которые могут быть выполнены конкретным исполнителем, называется системой команд исполнителя. Следовательно, алгоритм, рассчитанный на конкретного исполнителя, должен быть сформулирован так, чтобы содержать только те команды, которые входят в систему команд этого исполнителя.
Кроме того, эффективность означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время (обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее). Вот почему при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.
Приведенные выше комментарии поясняют интуитивное понятие алгоритма, но само это понятие не становиться от этого более четким и строгим. Тем не менее математики долгое время довольствовались этим понятием. Лишь с выявлением алгоритмически неразрешимых задач. т.е. задач, для решения которых невозможно построить алгоритм, появилось настоятельная потребность в построении формального определения алгоритма, соответствующего известному интуитивному понятию.
Интуитивное понятие алгоритма в силу своей расплывчатости не может быть объектом математического изучения, поэтому для доказательства существования или не существование алгоритма решения задачи было необходимо строгое формальное определение алгоритма.
Построение такого формального определение было начато с формализации объектов (операндов) алгоритма, так как в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания датчиков, фиксирующих параметры производственного процесса, шахматные фигуры и позиции и т.п. Однако, предполагая, что алгоритм имеет дело не с самими реальными объектами, а с их изображениями, можно считать, что операнды алгоритма есть слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритм связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена английским математиком А.Тьюрингом в 1936 году, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга) как исполнителя алгоритма и высказал тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга.
Мы будем придерживаться неформального определения алгоритма, формулируемого следующим образом:
Алгоритм - это упорядоченная последовательность указаний, выполнение которой приводит от исходных данных к требуемому результату.
Другими словами алгоритм это план решения задачи, записанный в виде последовательности указанийили групп указаний.
Приведем пример алгоритма Евклида, выполняя который определяется общий наибольший делитель двух положительных целых чисел a и b.
Пример 2. Алгоритм Евклида, нахождения наибольшего общего делителя двух положительных чисел.
1. Проверитьa>b. Если да, то перейти к указанию 2, иначе – к указанию 3.
2. Взять за новое значение a разностьa-b. Перейти к указанию 1.
3. Проверить b>a . Если да, то перейти к указанию 4, иначе - к указанию 5.
4. Взять за новое значение bразность b-a, перейти к указание 1.
5. За результат взять последнее значение a (b). Перейти к указанию 6.
6. Закончить процесс.
В приведенном выше алгоритме, предполагается, что его может выполнить любой человек или вычислительная машина, который умеет выполнять операции сравнения и вычитания двух чисел. Напомним, что в школе наибольший общий делитель определяется как произведение общих простых делителей чисел. В данном алгоритме о произведении и понятии делителя числа нет даже упоминания и, тем не менее, следуя ему, всегда определяется наибольший общий делитель двух целых положительных чисел. Это факт говорит о том, что получить результат можно разными способами с применением операций, которые, на первый взгляд, не имеют к решаемой проблеме никакого отношения, что позволяет среди всех возможных вариантов решения задачи, искать наиболее эффективный. В дальнейшем рассматриваются алгоритмы для вычислительных машин. Современные компьютеры с мощным программным обеспечением могут выполнять различные операции: от простых арифметических операций, производимых над двумя числами до решения сложных задач из многих сфер деятельности людей. Если на компьютере имеется программа, позволяющая решить требуемую задачу, то алгоритм решения такой задачи сводится к описанию процесса ввода исходных данных, обращения к требуемой программе и получения результатов в нужном виде. В тоже время для очень многих простых задач нет готовых программ их решения. По-видимому, нельзя на все случаи, да и нет такой необходимости, хранить в памяти необходимые программы. Но практически все программные системы, применяемые на компьютерах, имеют реализованные языки программирования, позволяющие с небольшими затратами составить самостоятельно программу решения довольно сложной задачи. Для реализации такой возможности надо уметь составлять алгоритмы и знать правила (синтаксис) записи указаний на алгоритмическом языке. В дальнейшем мы предполагаем, что «машина умеет» выполнять все арифметические операции, операции сравнения, логические операции, а также может вычислять практически все элементарные функции. Кроме этого она может ввести в память необходимые данные, а также напечатать или вывести на дисплей результаты.