не является необходимым, так как оно выполняется алгоритмом неявно.
Рекурсивный алгоритм Евклида (GCD – Great Common Divider) для нахождения наибольшего общего делителя пары натуральных чисел (т, п).
GCD(m, n)
ЕСЛИ n = 0, ТО вернуть результат m,
ИНАЧЕ вернуть GCD(n, m mod n)
Как правило, для алгоритма можно выделить семь характеризующих его независимых параметров (пример дан для алгоритма Евклида):
· совокупность возможных исходных данных: I = {(m, n) | m ³ n};
· совокупность возможных промежуточных результатов: P = {(m, n) | m ³ n};
· совокупность результатов: R = {m | m > 0};
· правило начала: ввод пары чисел (m, n), m ³ n;
· правило обработки: (m, n) ® (n, m mod n);
· правило окончания: n = 0;
· правило извлечения результата: первое число пары (m, 0).
Смена конструктивных объектов (пар чисел) в алгоритме Евклида (для пары т = 10, п = 4): (10, 4) ® (4, 2) ® (2, 0).
Алгоритм называется частичным, если результат получается только для некоторых i Î I, и полным, если результат получается для всех i Î I.
К алгоритмам предъявляются следующие требования.
1. Алгоритм должен предназначаться для работы с данными, которые могут быть входными, промежуточными или выходными, которые должны принадлежать некоторому заранее определенному множеству объектов. Число входных данных может быть нулевым. Число выходных данных должно быть отлично от нуля.
Для представления данных определяется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов.
Типичным используемым средством является индуктивное построение. Например, определение идентификатора – это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах – наиболее обычный тип алгоритмических данных, а число символов в слове – естественная мера объема данных. Другой случай алгоритмических объектов – формулы. Примером могут служить формулы алгебры предикатов и алгебры высказываний. В этом случае не каждое слово в алфавите будет формулой.
2. Алгоритм должен размещать данные в памяти. Память обычно считается однородной и дискретной, т. е. она состоит из одинаковых ячеек, причем каждая ячейка может содержать один символ данных, что позволяет согласовать единицы измерения объема данных и памяти.
3. Алгоритм должен быть дискретным – состоящим из отдельных элементарных предписаний (шагов), множество которых должно быть конечным. Все предписания алгоритма должны иметь однозначную трактовку и быть понятны исполнителю, т. е. тому, кто будет выполнять алгоритм (должны быть включены в его систему команд).
Свойства исполнителя решающим образом влияют на алгоритм. Предписания, понятные одному исполнителю, могут оказаться непонятными для другого. Так, алгоритм Евклида предназначен для исполнителя, умеющего сравнивать и вычитать натуральные числа.
4. Алгоритм должен быть детерминированным. Последовательность его шагов должна быть определена для любого возможного случая, т. е. после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной. Значения на последующих шагах должны получаться по особым правилам из значений, имеющихся на предыдущих шагах.
5. Алгоритм должен быть конечным (финитным). Его работа алгоритма должна заканчиваться за конечное число шагов, которое может быть сколь угодно большим. Для решения практических задач это число должно быть предельно конечным, т. е. разумным.
Алгоритм Евклида обладает этим свойством, поскольку максимумы из m и n образуют убывающую последовательность натуральных чисел, а такая последовательность не может быть бесконечной.
6. Алгоритм должен быть результативным. При выполнении над исходными данными определенной последовательности действий алгоритм должен приводить к решению поставленной задачи за конечное число шагов.
Данное свойство иногда называют сходимостью алгоритма.
7. Алгоритм должен быть эффективным. Все его шаги должны быть достаточно простыми, чтобы исполнитель мог выполнить их за конечное время. Общее время работы алгоритма должно не просто быть конечным, но и разумным.
Методом полного перебора вариантов можно выяснить, чем кончится шахматная партия, однако время работы этого метода делает его практически бес полезным.
8. Алгоритм должен быть реализуемым. Предполагается наличие механизма, который по описанию алгоритма порождает процесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.
9. Алгоритм должен быть массовым. Он должен давать решение группы задач, отличающихся исходными данными, при всех допустимых значениях этих данных.
Алгоритм Евклида позволяет найти наибольший общий делитель любой пары натуральных чисел, являющихся исходными данными.
Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе вычислительного устройства, требование 2 – его памяти, требование 3 – программе работы, требования 4 и 6 – ее логической природе, требования 5, 7, 8 –возможностям вычислительного устройства.
Имеются также некоторые черты неформального понятия алгоритма, относительно которых не достигнуто окончательного соглашения. Эти черты сформулируем в виде вопросов и ответов.
· Следует ли фиксировать конечную границу для размера входных данных?
· Следует ли фиксировать конечную границу для числа элементарных шагов?
· Следует ли фиксировать конечную границу для размера памяти?
· Следует ли ограничить число шагов вычисления?
На все эти вопросы далее принимается ответ «НЕТ», хотя возможны и другие варианты, поскольку у физически существующих ЭВМ соответствующие размеры ограничены. Однако теория, изучающая алгоритмические вычисления, осуществимые в принципе, не должна считаться с такого рода ограничениями, поскольку они преодолимы, по крайней мере, в принципе (например, в общем случае, любой фиксированный размер памяти всегда можно увеличить на одну ячейку).
Дата добавления: 2015-04-11; просмотров: 92 | Поможем написать вашу работу | Нарушение авторских прав |