Colloquy Cycle on Tuesday, November 19, 1996 - 15:45

Bei der Implementierung von (semi-)numerischen Algorithmen hat man zu beachten, dass durch die endliche Rechengenauigkeit beliebig falsche Resultate entstehen koennen, selbst wenn die Input-Daten im verwendeten Maschinenzahlen-Raster exakt darstellbar sind. Auch das Erkennen und korrekte Behandeln von Sonderfaellen (degenerate input data), in letzter Zeit gerade fuer geometrsiche Algorithmen im Mittelpunkt des Interesses, gestalten sich schwierig.

Um korrekte Aussagen bzw. Werte zu erhalten, koennen verschiedene Methoden Anwendung finden: Verwendung einer exakten Integer-Arithmetik, symbolisches Rechnen, die von Edelsbrunner/Muecke vorgeschlagene Technik "Simulation of Simplicity" oder Rechnen mit Einschliessungsmengen. Diese oder andere Verfahren, die auch hybrid eingesetzt werden, arbeiten selbst nur unter gewissen Voraussetzungen teilweise oder durchgaengig erfolgreich, was ihre Bedeutung jedoch nicht schmaelert.

Im Vortrag wird eine weitere Methode vorgeschlagen, die an das Rechnen mit Einschliessungsmengen anschliesst, um Algorithmen, die unter Verwendug einer exakten Zahlendarstellung, Arithmetik und Auswertung von Standardfunktionen korrekte Resultate liefern wuerden, durch Transformationen zu implementieren. Die Transformationen haben als Grundbausteine Regeln zu Umwandlung von Ergibtanweisungen, Sequenzen, if-then-else-Anweisungen und while-Schleifen und setzen sich induktiv aus diesen zusammen. Wenn der transformierte Algorithmus Werte liefert, so sind dies garantierte Einschliessungen der gesuchten exakten. Bricht er waehrend seiner Laufzeit unterwegs ab, so kann er mitteilen, warum dies so ist. An Beispielen wird die Praktikabilitaet demonstriert.