Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
2. Сравнения двух действительных чисел (<с, =, ф, >,»¦
3. Косвенная адресация памяти (допустимы только целочисленные адреса).
Дополнительные операции (только для тех приложений, где это необходимо):
4. Корни k-ft степени, тригонометрические функции, ЕХР, LOG (вообще аналитические выражения).
Эту модель будем называть вещественнозначной РАМ. Она хорошо отражает тот тип программ, которые обычно пишутся на алгоритмических языках высокого уровня, таких как Фортран и Алгол, в которых принято считать, что переменные типа REAL имеют неограниченную точность. На этом уровне абстракции можно игнорировать вопросы типа: «Как ввести или вывести действительное число за конечное время?»
') См. [Гэри, Джонсон (1982), с. 27].—Прим. перев. 2) В русском переводе этой книги аббревиатура РАМ расшифровывается как «равнодоступная адресная машина». — Прим. ред.
Гл. 1. Введение
Установление нижних оценок для характеристик работы алгоритмов решения определенной задачи — одна из главных целей анализа алгоритмов, поскольку они дают меру для оценки эффективности конкретных алгоритмов. Но это, вообще говоря, очень трудная проблема. Иногда удается установить трудоемкость одной задачи по известной трудоемкости другой задачи, используя метод преобразования задач1). В частности, предположим, что у нас есть две задачи, si- и которые связаны так, что задачу s4- можно решить следующим образом:
1. Исходные данные к задаче яФ преобразуются в соответствующие исходные данные для задачи 9$.
2. Решается задача j?.
3. Результат решения задачи Я преобразуется в правильное решение задачи бФ.
В этом случае мы говорим, что задача зФ преобразуема в задачу 3S2). Если шаги 1 и 3 вышеприведенного преобразования можно выполнить за время 0(т(Л/)), где, как обычно, N — «размер» задачи ?Ф, то скажем, что s4< x(N)-преобразуема в 3$, и запишем это кратко так: бФссЛ{М)$. Вообще говоря, преобразуе-мость не симметричное отношение; в частном случае, когда М- i\ М взаимно преобразуемы, мы назовем их эквивалентными.
Следующие два самоочевидных утверждения характеризуют мощь метода преобразования в предположении, что это преобразование сохраняет порядок размера задачи.
Предложение 1 (Нижние оценки методом преобразования). Если известно, что задача М- требует Т(\г) времени и М- х(М)-преобразуема в 03 (т. е. осг(Л/)-^), то задача $ требует не менее T(N) — 0(x(N)) времени.
Предложение 2 (Верхние оценки методом преобразования). Если задачу $ моокно решить за время T(N) и задача s? r(N)-преобразуема в Я (т. е. зФосх то лФ можно решить за
время, не превышающее T(N) + 0(т(Лг)).
Эту ситуацию графически иллюстрирует рис. 1.7, на котором показано, как нижняя и верхняя оценки переносятся от одной задачи к другой. Этот перенос справедлив, когда t(N) = = 0(T(N)), т. е. когда время преобразования не превосходит времени вычисления.
') Этот метод очень часто именуют сведением. Поскольку «сведение» предполагает преобразование к более простой задаче (а в данном случае это не так), то мы постараемся обойтись без этого понятия.
2) Преобразуемость (или сводимость) обычно определяется по отношению к языкам. В этом случае преобразование результатов не требуется, поскольку в качестве результата распознаватель цепочки выдает нуль или единицу. Для геометрических задач необходима большая гибкость, подкрепленная более общим определением.
45
Возвращаясь к нашей прежней классификации задач, возьмем некую задачу s& (задачу вычисления или поиска подмножества) и связанную с ней задачу распознавания D(?&). Легко видеть, что D{s4) ос0{N)<s&, поскольку:
1. Если зФ— задача вычисления, то никакого преобразования исходных данных не требуется (т. е. шаг 1 процедуры пре-
дадача А
Верхняя оценка
Рис. 1.7. Перенос верхней и нижней оценок между преобразуемыми задачами.
образования не нужен), а решение бФ надо просто сравнить за постоянное время 0(1) с фиксированной величиной, даваемой D(st).
2. Если же s& — задача поиска подмножества, то опять входная информация 5' для D(s4-) подается на вход зФ (т. е. шаг 1 не нужен), а решение зФ проверяется за время 0(N), чтобы убедиться в том, что его мощность совпадает с мощностью 5'.
Это очень важное рассуждение, поскольку оно показывает, что, когда мы ищем нижние оценки, можно сосредоточить свое внимание на задачах распознавания.
Когда вещественнозначная РАМ исполняет алгоритм для задачи распознавания, ее поведение описывается последовательностью операций двух типов: арифметических и сравнения. В этой последовательности главную роль играют сравнения, поскольку в зависимости от результата каждого сравнения алгоритм выбирает ту или иную ветвь выполнения. Эта ситуация графически показана на рис. 1.8; там каждый кружок представляет собой арифметическую операцию, а каждый треугольник — сравнение. Другими словами, процесс вычислений, исполняемый на РАМ, можно рассматривать как путь на дереве с корнем.
40
Гл. 1. Введение
Это корневое дерево заключает в себе описание чрезвычайно важной вычислительной модели, называемой «алгебраическим деревом решений», которую мы сейчас формализуем.
