*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 6
Freitag, 22.09.2000, 15.00–15.20 Uhr, WIL C 129

Umkehrschemata für Evolutionen mit variablen Transformationskosten

Andrea Walther, TU Dresden, Institut für Wissenschaftliches Rechnen

Zur Berechnung von Adjungierten, für die Parameterschätzung, bei der interaktiven graphischen Bearbeitung von Gegenständen und ähnlichen Aufgaben kann die Umkehrung einer Programmauswertung notwendig werden. Der einfachste Ansatz ist dann die Erstellung einer vollständigen Mitschrift der ausgeführten Anweisungen. Anschließend wird die Mitschrift rückwärts ausgewertet. Diese Methode verursacht jedoch einen enormen Speicherplatzbedarf und kann deshalb häufig nicht sinnvoll angewendet werden. Als praktikable Alternative bietet sich die Verwendung von Checkpoints an. Hierbei erfolgt eine stückweise Mitschrift und Umkehr der Programmauswertung. Dafür werden bei der Vorwärtsrechnung einige Zwischenzustände als Checkpoints gespeichert. Zur Erstellung der stückweise Mitschrift startet dann die Vorwärtsrechnung von diesen gesetzten Checkpoints.

Betrachtet werden in diesem Vortrag Evolutionen, d.h. Programme, die als eine Folge von Transformationen auf einem Zustandsraum interpretierbar sind. Dabei kann die Zeit, die zur Berechnung des neuen Wertes im Zustandsraum benötigt wird, von Transformation zu Transformation variieren, d.h. die Transformationskosten sind variabel. Für diese Art von Evolutionen wird ein neuer Algorithmus zur Berechnung eines zeitoptimalen Umkehrschemas für eine gegebene Checkpointzahl vorgestellt. Dieses neue Verfahren verringert die kubischen Komplexität der Bestimmung mittels dynamischer Programmierung auf eine quadratische Komplexität bezüglich der Anzahl der Transformationen durch Ausnutzung einer Monotonieeigenschaft der Checkpoints.