Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
17
формации, которые в совокупности с алгоритмами приводят к эффективному и элегантному решению вычислительных задач.
1.2.1. Алгоритмы: их запись и оценка эффективности
Алгоритмы формулируют по отношению к конкретной модели вычислений; как мы увидим в разд. 1.4, эта модель представляет собой удобную абстракцию реальной машины, используемой для исполнения программ. Однако, как было подчеркнуто в работе [Aho, Hopcroft, Ullman (1974)],нет ни нужды, ни желания записывать алгоритмы машинным кодом. Напротив, в интересах ясности, изобразительной эффективности и краткости мы будем, как правило1), использовать язык высокого уровня, ставший стандартным в литературе на данную тему — псевдоалгол. Псевдоалгол — это неформализованная и гибкая версия языка Алгол; он достаточно строг в своих управляющих структурах, но весьма волен в формате других своих операторов, где употребление общепринятых математических обозначений свободно чередуется с использованием выражений естественного языка. Разумеется, программа на псевдоалголе может быть рутинно превращена в строгую программу на языке уровня.
Следуя за работой Ахо, Хопкрофта, Ульмана, мы кратко проиллюстрируем конструкции псевдоалгола. Формальные определения типов данных опущены, а тип любой переменной обычно становится ясным из контекста. Кроме того, не выбирается специальный формат для выражений и условий.
Любая программа, обычно называемая процедурой, имеет следующий формат:
procedure имя (параметры) оператор.
Оператор можно заменить (согласно терминологии порождающих грамматик) цепочкой из двух или более операторов, заключая ее в этом случае в «операторные скобки» «begin ... end»:
begin оператор;
оператор
end.
В свою очередь смысл любого оператора можно раскрыть или предложением на естественном языке, или одним из нижеследующих особых более формальных способов.
А ') Иногда алгоритмы могут быть представлены в сугубо описательной яорме.
18
Гл. 1. Введение
1. Присваивание:
переменная := источник
Термин «источник» определяет вычисление, порождающее значение заданной переменной; вычисление это, вообще говоря, некоторое выражение над множеством переменных. (Некоторые из этих переменных могут в свою очередь выражаться через «функции»; функция — это особая форма программы, как показано ниже.) 2. Условие:
if условие then оператор (else оператор)
где составляющая else необязательна.
3. Цикл. Он представим в одном из трех форматов:
За. for переменная := значение until значение do оператор 36. while условие do оператор Зв. repeat оператор until условие
Конструкции while и repeat различаются, поскольку в цикле типа «while» условие проверяется перед выполнением оператора, в то время как в цикле типа «repeat» имеет место обратное. 4. Возврат:
return выражение
Оператор этого вида должен появиться в программе функционального типа, которая имеет формат
function имя (параметры) оператор.
Выражение, стоящее аргументом в операторе return, становится источником в операторе присваивания, как указано в п. 1.
Часто алгоритмы на псевдоалголе содержат комментарии, предназначенные для пояснения происходящего. В данной книге типовой формат комментария будет следующим: («предложение на естественном языке*).
Время, затраченное на вычисление при выполнении алгоритма, представляет собой сумму времен отдельных исполненных операторов (см. также разд. 1.4). Как упоминалось выше, программу, написанную на псевдоалголе, можно превратить прямым (хотя и утомительным) путем в программу на машин-
1.2. Алгоритмические основы
ном коде заданной ЭВМ. Это в принципе дает метод оценки времени выполнения указанной программы. Однако такой подход не только скучен, но также и мало вразумителен, ибо он ориентирован на конкретную ЭВМ, тогда как нас, по сути, интересует более общая функциональная зависимость времени счета от размеров задачи (т. е. то, как быстро время счета растет с ростом размеров задачи). В области анализа и построения алгоритмов принято выражать время выполнения, так же как и любую другую меру эффективности, с точностью до мультипликативной константы. Это обычно делается путем подсчета лишь определенных «ключевых операций», выполняемых алгоритмом (что легко осуществить, анализируя версию этого алгоритма, записанную на языке высокого уровня). Такой подход абсолютно правомерен при определении нижних оценок времени выполнения, поскольку любые неучтенные операции могут лишь увеличить их; однако при работе с верхними оценками мы обязаны убедиться в том, что вклад выбранных ключевых операций в сумме отличается не более чем в константу раз от вклада всех операций, выполненных алгоритмом. Кнут популяризовал аппарат обозначений, прекрасно отличающих верхние оценки от нижних, который мы и заимствуем [Knuth (1976)]:
0(f(N)) служит для обозначения множества всех функций g{N) таких, что существуют положительные константы С и N0, для которых \g(N) | ^ Cf (N) при всех N ^ N0.
Q{f(N)) служит для обозначения множества всех функций g{N) таких, что существуют положительные константы С и N0, для которых g(N)^ Cf{N) при всех N ^ N0.
