Das Kontruktionsproblem

Abstract

Wir haben in dieser Arbeit das Konstruktionsproblem formuliert und eine nu- merische und eine symbolische LÄosung dieses Problems vorgestellt. Die nume- rische Lösung, die so genannte rückwirkende Dynamik, ermöglicht es, auf einer interaktiven Zeichenoberfläche alle Punkte - sowohl Ursprungspunkte der Kon- struktion als auch abhängige Punkte - frei zu bewegen und die resultierende Bewegung der übrigen Punkte zu beobachten. Cedric ist unseres Wissens das erste dynamische Geometriesystem, das eine solche rückwirkende Dynamik an- bietet. Für die exakte Lösung haben wir einen Algorithmus vorgestellt, der isolierte Nullstellen eines Gleichungssystems findet, die durch Quadratwurzeln ausdrückbar sind. Das Gleichungssystem kann dabei selbst Quadratwurzeln enthalten. Wir haben den Euklidischen Körper vorgestellt und einen Darstellungssatz formuliert, der uns eine minimale Repräsentation in der Anzahl verschiedener Wurzeln von Elementen des Euklidischen KÄorpers erlaubt. Wir haben für diese Darstellung ein Eindeutigkeitsresultat für die meisten der Elemente dieses Körpers gezeigt. Zur Lösung des Gleichungssystems haben wir drei klassische Methoden angepasst und eine weitere, neue Methode eingeführt, um das Gleichungssystem auf die Lösung eines univariaten Polynoms zurückzuführen. Für die Lösung des univariaten Problems haben wir einen Algorithmus vorgestellt, der über dem Grundkörper nur die Faktorisierung benötigt und dann alle durch Quadratwurzeln ausdrückbaren Nullstellen eines vorgegebenen Polynoms finden kann. Wir haben gezeigt, dass dieser Algorithmus bei polynomieller Faktorisierung für Polynome vom Grad d maximal O(dlog (d)) Schritte benötigt und im Regelfall - bei vollständigen Elementen - sogar nur d Faktorisierungen eines Polynoms vom Grad kleiner oder gleich d2 benötigt, also in polynomieller Zeit läuft. Bei exponentieller Faktorisierung ist die Laufzeit in jedem Fall durch diesen Anteil dominiert.

Liegt nicht vor.