Понятие алгоритма, относящиеся к фундаментальным концепциям информатики, возникло задолго до появления ЭВМ и стало одним из основных понятий математики.
Слово «алгоритм» произошло от имени среднеазиатского (узбекского) математика аль-Хорезми (IХ в.) и использовалось в математике для обозначения правил выполнения четырех арифметических действий: сложения, вычитания, умножения, деления. В настоящее время понятие алгоритма используется не только в математике. Его применяют во многих областях человеческой деятельности, например говорят об алгоритме управления производственным процессом, алгоритме игры в шахматы, алгоритме пользования бытовым прибором, алгоритме поиска пути в лабиринте, алгоритме управления полётом ракеты и т.п.
Для пояснения понятия «алгоритм» важное значение имеет определение понятия «исполнитель алгоритма». Алгоритм формулируется в расчете на конкретного исполнителя, например человека, специально дрессированное животное, особую машину - автомат и т.д. Алгоритм является руководством к действию для исполнителя, поэтому значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание». Можно сказать, что алгоритм - понятное и точное предписание (указание) исполнителю совершить определённую последовательность действий для достижения указанной цели или решения поставленной задачи. Сказанное не является определением в математическом смысле, а лишь отражает интуитивное понимание алгоритма, сложившееся за долгие годы.
Пример 1. Пусть имеется текст на русском языке, подготовленный специальным образом, который заканчивается специальным символом @, больше нигде в тексте не встречающемся. Необходимо подсчитать число гласных букв в данном тексте.
Для решения этой задачи можно предложить такой способ подсчета числа гласных букв: читать последовательно символ за символом и каждый раз, когда очередной символ есть гласная буква русского алфавита, прибавлять к счетчику единицу (предполагается, что исполнитель данного алгоритма умеет различать гласные и не гласные буквы). Счет начинать с нуля и продолжать до тех пор, пока не будет прочитан символ @, обозначающий конец текста. Приведенное выше описание дает лишь идею алгоритма, но, чтобы превратить его в понятное и точное предписание исполнителю, его необходимо уточнить.
Во-первых, объектами алгоритма являются символы текста и числа. Над символами текста производятся операции чтения, поиска следующего символа, сравнения символа с символом @ и сравнение символа с одной из гласных букв русского алфавита. Над числами производится операция прибавления единицы.
Во-вторых, символы текста читаются последовательно один за другим, начиная с первого символа до символа @ включительно. Чтобы не ошибиться при чтении, будем предполагать, что наш абстрактный исполнитель имеет в своем распоряжении указатель, который можно перемещать по тексту и который указывает на очередной читаемый символ. Поэтому поиск следующего символа сводится к перемещению указателя на следующий по порядку символ текста.
В-третьих, счет числа гласных букв начинается с нуля, поэтому до начала работы счетчик числа гласных должен содержать нуль.
Учитывая эти замечания, сформулируем алгоритм в виде такой последовательности действий:
1. Записать в счетчик 0.
2. Установить указатель на первый символ текста.
3. Если символ не есть @, то перейти к п.4, иначе перейти к пункту 7.
4. Если символ - гласная буква русского алфавита, то увеличить счетчик на единицу.
5. Перевести указатель на следующий символ текста.
6. Перейти к п.3.
7. Взять число, находящееся в счетчике, в качестве ответа. Стоп.
Обратим внимание на основные особенности (свойства) алгоритма.
1. Алгоритм имеет некоторое число входных величин - аргументов, задаваемых до начала работы (в приведенном выше примере входными данными являются символы текста и возможно набор гласных букв).
Цель выполнения алгоритма - получение результата (результатов), имеющего вполне определенное отношение к исходным данным.
В данном примере результат - число, обозначающее число гласных букв в исходном тексте.
Для алгоритма можно брать различные наборы входных данных, т.е. применять один и тот же алгоритм для решения целого класса однотипных задач, различающихся исходными данными. Это свойство алгоритма обычно называют массовостью. Рассмотренный в примере алгоритм применим к различным текстам на русском языке. Вместе с тем существуют и такие алгоритмы, которые применимы только к единственному набору исходных данных. Например, для алгоритма пользования автоматическим турникетом при входе в метро существует единственный вариант исходного данного - тридцати копеечный жетон. Поэтому понятие массовости требует уточнения. Можно считать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда свойство массовости означает применимость алгоритма ко всем объектам этого класса. А количество объектов класса (конечное или бесконечное) - свойство самого класса исходных данных.
2. Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Приведенный в примере алгоритм подсчета гласных букв может быть понятен человеку, знающему русский язык. Чтобы этот алгоритм мог быть также выполнен человеком, не знающим русского языка, необходимо записать алгоритм на языке понятном исполнителю, и сообщить ему дополнительные сведения: перечислить явно гласные буквы русского алфавита.
Понятность алгоритма означает знание исполнителя о том, что надо делать для исполнения этого алгоритма.
Таким образом, при формулировке алгоритма необходимо учитывать возможности и особенности исполнителя, на которого рассчитан алгоритм.
3. Алгоритм представлен в виде конечной последовательности шагов. Говорят, что алгоритм имеет дискретную структуру. Следовательно, его исполнение расчленяется на выполнение отдельных его шагов, выполнение каждого очередного шага начинается после завершения предыдущего.
4. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут повторяться многократно. В рассмотренном выше примере многократно повторяются шаги с третьего по шестой. Однако выполнение алгоритма все же закончится за конечное число шагов, так как текст имеет конечную длину и в нем имеется символ @. При чтении этого символа будет выполнен седьмой шаг алгоритма, завершающий его выполнение.
В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Так, можно сформулировать процедуру вычисления числа Пи. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же ее искусственно прервать, например ввести условие завершения процесса вычислений вида: «Закончить вычисления после получения N десятичных знаков числа Пи», то получится алгоритм вычисления N десятичных знаков числа Пи. На этом принципе основано получение многих вычислительных алгоритмов: строится бесконечный, сходящийся к искомому решению процесс. Он обрывается на некотором шаге, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближения зависит от числа шагов.
5. Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен действовать строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие-нибудь действия, отличные от предписанных алгоритмом. Иными словами, алгоритм рассчитан на чисто механическое исполнение. Эта очень важная особенность означает, в частности, что если один и тот же алгоритм поручить для исполнения разным исполнителям, то они придут к одному и тому же результату, лишь бы эти исполнители понимали алгоритм. Именно определенность алгоритма дает возможность поручить его исполнение автомату, не обладающему «здравым смыслом».
B приведенном выше примере, действие перемещения указателя на следующий символ достаточно точно определено, если текст расположен на длинной узкой ленте и вытянут в одну строку (например, напечатан на узкой телетайпной ленте). Если же текст разбит на строки и страницы (т.е. имеет сложную структуру), то действие перемещения указателя на следующий символ уже не является столь очевидным. В этом случае необходимы указания, как поступать исполнителю, когда закончится очередная строка или очередная страница текста.
Таким образом, формулировка алгоритма должна быть так точна, чтобы полностью определять все действия исполнителя.
6. Каждый шаг алгоритма должен быть выполнен точно и за конечное время. В этом смысле говорят, что алгоритм должен быть эффективным, т.е. действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Поэтому, например, указание вида: «Если любое целое число, большее 6, можно представить в виде суммы трех простых чисел, то счетчик увеличить на 1, иначе счетчик уменьшить на 1» - неэффективно, так как не известен способ доказательства истинности или ложности утверждения, содержащегося в нем. Следовательно, исполнитель не может выполнить этот шаг алгоритма, пока не найдет соответствующего доказательства.
Обычно отдельные указания исполнителю, содержащиеся в каждом шаге алгоритма, называют командами. Таким образом, эффективность алгоритма связана с возможностью выполнения каждой команды за конечное время. Исполнители отличаются друг от друга своими возможностями, т.е. репертуаром команд, которые они «понимают» и могут выполнять. Совокупность команд, которые могут быть выполнены конкретным исполнителем, называется системой команд исполнителя. Следовательно, алгоритм, рассчитанный на конкретного исполнителя, должен быть сформулирован так, чтобы содержать только те команды, которые входят в систему команд этого исполнителя.
Кроме того, эффективность означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время (обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее). Вот почему при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
