28.11.18 · Stefan Schirra (Universität Magdeburg) · Much Ado about Zero

SchirraMuch Ado about Zero

Vergleichsweise wenige der vielen effizienten, in der Algorithmischen Geometrie entwickelten Verfahren haben letztendlich den Weg in die Praxis gefunden. Ein Grund dafür ist sicherlich auch, dass der Entwicklung solcher Algorithmen in der Regel ein Berechnungsmodell zugrunde liegt, welches äußerst unrealistisch ist, die so gannte Real RAM, die exakte Arithmetik mit beliebigen reellen Zahlen erlaubt. In der Praxis wird hingegen meist einfach Gleitkommarithmetik benutzt. Kleine Rundungsfehler können jedoch inkonsistente Entscheidungen verursachen, mit, wie wir im Vortrag sehen werden, manchmal fatalen Folgen. Es klafft hier eine große Lücke zwischen Theorie und Praxis. Wir werden uns anschauen, wie man die Real RAM ein Stück weit in der Praxis umsetzen und so die Korrektheit der auf Basis der Real RAM entwickelten effizienten Algorithmen erhalten kann. Abschließend werden wir uns einer geometrischen Aufgabenstellung zuwenden, welche in der Praxis problemlos effizient gelöst werden kann, in der Theorie aber zu einem seit vielen Jahren offenen Problem wird, wenn als Berechnungsmodell nicht die Real RAM, sondern die Turingmaschine zugrunde gelegt wird.