Please use this identifier to cite or link to this item:
doi:10.22028/D291-25786
Title: | Das Kontruktionsproblem |
Author(s): | Oertzen, Timo von |
Language: | German |
Year of Publication: | 2003 |
SWD key words: | Konstruieren |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-2424 hdl:20.500.11880/25842 http://dx.doi.org/10.22028/D291-25786 |
Advisor: | Günter Hotz |
Date of oral examination: | 2-Sep-2003 |
Date of registration: | 15-Jul-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
TimovonOertzen_ProfDrGuenterHotz.pdf | 1,09 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.