MENÜ MENÜ  

cover

Fallstudien relationaler Programmentwicklung am Beispiel ausgewählter Graphdurchlaufstrategien

Thorsten Hoffmann

ISBN 978-3-89722-967-9
150 Seiten, Erscheinungsjahr: 2002
Preis: 40.50 €
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.

Keywords:
  • Informatik
  • Programmentwicklung
  • Verifikation
  • Relationenalgebra

KAUFOPTIONEN

40.50 €
auf Lager
Versandkostenfrei innerhalb Deutschlands


Wollen auch Sie Ihre Dissertation veröffentlichen?