Fallstudien relationaler Programmentwicklung am Beispiel ausgewählter Graphdurchlaufstrategien
Thorsten Hoffmann
ISBN 978-3-89722-967-9
150 Seiten, Erscheinungsjahr: 2002
Preis: 40.50 Eur
Stichworte/keywords: Informatik , Programmentwicklung , Verifikation , Relationenalgebra
Der enge Zusammenhang von Relationen und Graphen macht den
relationalen Kalkül in vielerlei Hinsicht für die Entwicklung
graphentheoretischer Algorithmen sehr interessant.
Einerseits künnen solche Algorithmen in Form von relationalen Programmen
sehr kurz und damit gut lesbar formuliert werden. Andererseits besteht
aufgrund des algebraischen Kalküls der Relationen die Müglichkeit, Aussagen
über Eigenschaften von Relationen sehr elegant nachzuweisen.
Im Zusammenspiel mit dem Hoare-Kalkül wird auf diese Weise ein
Rahmen bereitgestellt, der eine vollständig formale
Programmentwicklung bzw. -verifikation gestattet, ohne
zwischenzeitlich informelle oder anschauliche Argumentationen
einbringen zu müssen. Gleichzeitig wird durch dieses streng formale
Vorgehen die Wahrscheinlichkeit, fehlerhafte Beweisschritte zu
produzieren, auf ein Minimum gesenkt.
In der Arbeit werden drei bekannte Graphdurchlaufverfahren und
zahlreiche Anwendungen im relationalen Kontext vorgestellt und als
korrekt nachgewiesen. Die Präsentation des ersten Algorithmus, einem
iterativen relationalen Tiefensuche-Algorithmus, schließt eine
genaue Spezifikation des Tiefensuchwaldes ein. Dies stellt eine wesentliche
Erleichterung für die Korrektheitsbetrachtungen der Anwendungen
dar, da man nun mit der Spezifikation arbeiten kann
und somit umständliche Argumentationen über dynamische Ablaüfe
und die dabei herrschenden Beziehungen zwischen den beteiligten
Objekten entfallen. Anschließend wird ein relationaler
Breitensuche-Algorithmus entwickelt, der aus einem
Erreichbarkeits-Algorithmus durch geringfügige Modifikationen am
Programmcode hervorgeht. Der dritte Algorithmus beschäftigt sich mit
der Berechnung Hamiltonscher Kreise, wobei die Besonderheit darin
liegt, daß nicht jeder Graph einen solchen Kreis besitzt, was bei der
Programmentwicklung besonders zu berücksichtigen ist.
Eine Vielzahl von Anwendungen der vorgestellten Programme runden die
Arbeit ab.
zurück zum Katalog
Startseite
