Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Евклидово построение замечательно по разным причинам; например, оно определяет набор допустимых инструментов (линейка и циркуль) и множество допустимых операций (примитивов), которые можно выполнить с их помощью. Древних чрезвычайно интересовала полнота системы евклидовых примитивов при условии конечности числа операций. В частности,
/./. Исторический обзор
11
их интересовало, допускает ли такая система все мыслимые геометрические построения (например, трисекцию угла). В современной формулировке тот же вопрос ставит информатика: достаточно ли евклидовых примитивов для реализации всех геометрических «вычислений»? При попытке ответить на этот вопрос рассматривались многие альтернативные модели вычислений, получаемые путем изменения как набора примитивов, так и самих инструментов. Архимед предложил (корректную) конструкцию для трисекции угла в 60 градусов со следующим добавлением к множеству примитивов: даны два круга А и В и точка Р; мы можем выбрать отрезок MN прямой и разместить его так, чтобы прямая прошла через Р, причем точка М оказалась бы на границе А, а N — на границе В. В ряде случаев изучался ограниченный набор инструментов, например только циркуль. Такие идеи выглядят почти предвосхищением методов теории автоматов, которая проверяет мощность вычислительных моделей при разных ограничениях. Увы, доказательство неполноты евклидовых средств должно было дожидаться развития алгебры.
Влияние «Начал» Евклида было столь фундаментальным, что никаких других формулировок геометрии не было предложено вплоть до Декарта. Введение последним координат позволило выразить геометрические задачи алгебраически, вымостив путь к изучению высших плоских кривых и ньютоновскому анализу. Координаты позволили резко повысить вычислительные возможности, соединив две великие области математики и дав начало возрождению конструктивистского мышления. Теперь появилась возможность получать новые геометрические объекты, решая связанные с ними алгебраические уравнения. И вскоре снова возникли вопросы вычислимости. Так, Гаусс, уже вооруженный алгебраическими средствами, вновь вернулся к задаче о том, какие из правильных многоугольников с простым числом сторон можно построить, используя евклидовы инструменты, и полностью решил ее. При этом стала ясной близкая связь между построениями с помощью циркуля и линейки, расширениями поля1) и алгебраическими уравнениями. В своей докторской диссертации Гаусс показал, что у любого алгебраического уравнения существует по крайней мере один корень (основная теорема алгебры). Абель в 1828 г. занялся решением той же задачи на ограниченной модели вычислений. Он задался вопросом, можно ли найти корень любого алгебраического уравнения, воспользовавшись только арифметическими операциями и извлечением корней n-й степени, и доказал, что этого сделать нельзя. Хотя было известно, что все рациональные числа действительны, по-
') Имеется в виду поле действительных чисел. — Прим. перев.
t л. 1 Введение
следний ответ показал, что не все действительные числа рациональны. Вскоре после этого Абель описал те алгебраические уравнения, которые могут быть решены в радикалах, и это дало ему возможность обсуждать осуществимость специфически геометрических задач, таких как трисекция угла.
1.1.1. Представление о сложности в классической геометрии
Евклидовы построения для любых задач, кроме самых тривиальных, весьма сложны, ибо в них допустимы только рудиментарные примитивы. Весьма частым развлечением геометров после Евклида было улучшение его построений так, чтобы они могли выполняться за меньшее число «операций». Однако задача определения количественной меры сложности построения не была сформулирована вплоть до двадцатого столетия. В 1902 г. Эмиль Лемуан ввел науку геометрографию, систематизировав евклидовы примитивы следующим образом [Lemoin (1902)]:
1. Поставить одну ножку циркуля в данную точку.
2. Поставить одну ножку циркуля на данную прямую.
3. Провести окружность.
4. Совместить ребро линейки с данной точкой.
5. Провести линию.
Общее число таких операций, выполняемых в процессе построения, называется его простотой, хотя Лемуан полагал, что, возможно, более уместен термин «мера сложности». Это определение близко связано с нашей современной идеей временной сложности алгоритма, хотя в работе Лемуана нет функциональной связи между размером исходной информации (числом заданных точек и линий) для геометрического построения и его простотой. Безусловно, интерес Лемуана был направлен на улучшение исходных евклидовых построений, а не на развитие теории сложности вычислений. И в первом он добился замечательного успеха — евклидово решение задачи о кругах Аполлония требовало 508 шагов, в то время как Лемуан сократил его менее чем до двухсот [Coolidge (1916)]. К сожалению, Лемуан не почувствовал важности доказательства, а возможно, просто не смог доказать, что определенное число операций было необходимо для данного построения, и, таким образом, идея о нижней оценке алгоритма ускользнула от него.
