 Online Bewegungsplanung (2V+1Ü) (A,C) [A1]
Mo 15:00-16:30, HS 1 (Dr. Elmar Langetepe)
Übungen: Di 16-18, SR N 1001 (Dr. Elmar Langetepe, Thomas Kamphans)
 Model Checking (4V+2Ü) (A,C) [A2]
Mi, Fr 9-11, HS 1 (Prof. Dr. Christel Baier)
Übungen: n.Vereinb. (Prof. Dr. Christel Baier)
|
Vorlesung (Hauptstudium)
Reale und robuste Implementierung geometrischer Algorithmen
Dr. Elmar Langetepe
Geometrische Algorithmen werden normalerweise dadurch beschrieben, dass eine "Allgemeine Lage" der Objekte angenommen und die real random access machine ("real RAM") als Berechnungsmodell zugrunde gelegt wird.
Das "real RAM"-Modell erlaubt die exakte Repräsentation reeller Zahlen und berechnet für die Durchführung der Operationen +,*,: oder auch sqrt, log oder sin, cos nur konstante Zeit. Die "Allgemeine Lage"-Annahme ist von Fall zu Fall verschieden, z.B. sollen keine drei Punkte auf einer Geraden oder keine vier Punkte auf einem Kreis liegen. Die "real RAM"-Annahme wird häufig gemacht, weil exakte Ergebnisse für arithmetische Berechnungen gebraucht werden. Durch die "Allgemeine Lage"-Annahme soll die Behandlung degenerierter Fälle vermieden werden.
Beide Grundannahmen vereinfachen die Beschreibung und Analyse geometrischer Algorithmen erheblich. Leider ist die "real RAM" nicht implementierbar und die betrachteten Objekte könnten sehr wohl außerhalb "Allgemeiner Lage" sein. Deshalb kann man nicht davon ausgehen, dass die praktische Implementierung eines geometrischen Algorithmus tatsächlich die theoretisch bewiesene Korrektheit und Laufzeit erfüllt. So kann z.B. die reelle Arithmetik nicht einfach durch Floating Point-Berechnungen approximiert werden. Auch ist durch Floating Point-Berechnungen nicht mehr eindeutig festzustellen, ob drei Punkte auf einer Geraden liegen.
Es werden in der Vorlesung verschiedene Ansätze vorgestellt, wie man den obigen zwei Problemen und ihrer Kombination begegnen kann, um robuste Implementierungen klassischer Algorithmen zu erhalten.
|
Übersicht: alle Semester