Programmentwicklung Und Verifikation (Springers Angewandte Informatik,)

Die entscheidenden Argumente fr die Korrektheit eines Programms knnen am einfachsten schon bei seiner Entwicklung festgehalten werden. Die Methoden, mit denen man den Korrektheitsbeweis Hand in Hand mit der Programmentwicklung fhrt, werden in diesem Buch beschrieben. Die Programme und die Informationen fr die Verifikation werden mit eigens zu diesem Zweck erweiterten Struktogrammen dargestellt. Die Methoden und die zahlreichen Beispiele sind unabhngig von einer bestimmten Programmiersprache. Das Buch wendet sich nicht nur an die an Programmverifikation interessierten Leser, sondern an alle, die ein tieferes Verstndnis von Programmen erreichen wollen. Der Leser soll die vorgestellten Methoden und Denkweisen bei der Entwicklung seiner eigenen Programme anwenden lernen, um so effizientere und sicherere Software zu erzeugen. 1. Warum Verifizieren von Programmen?.- 1.1 Korrektheit von Programmen.- 1.2 Verifizieren versus Testen von Programmen.- 1.3 Programme gleichzeitig entwickeln und verifizieren.- 1.4 Fr und wider Verifizieren.- 2. Einfhrende Beispiele.- 2.1 Mischen zweier sortierter Karteikartenstapel.- 2.2 Diskussion der Art der Prsentation des Verfahrens.- 2.3 Sortieren durch Mischen.- 2.4 Invarianten als Lsung von Rtselaufgaben.- 2.4.1 Weinpantschen.- 2.4.2 Hofstadters MU-Rtsel.- 3. Zusicherungen (Assertions).- 3.1 Zusicherungen als Dokumentation von Programmen.- 3.2 Die Sprache der Zusicherungen.- 3.2.1 Zusicherungen als Boolesche Ausdrcke.- 3.2.2 Die Zusicherungen true und false.- 3.2.3 Zusicherungen mit Quantoren.- 3.2.4 Selbstdefinierte Prdikate.- 3.2.5 Selbstdefinierte arithmetische Funktionen.- 4. Programmzustnde und Zustandsraum.- 4.1 Der Zusammenhang zwischen Zustnden und Zusicherungen.- 4.2 Programme als Abbildungen im Zustandsraum.- 5. Spezifizieren von Programmen.- 5.1 Spezifizieren mit Pre- und Postcondition.- 5.2 Beispiele fr Spezifikationen.- 6. Verifikationsregeln (Verification rules).- 6.1 Konsequenz-Regeln.- 6.2 Die Zuweisung.- 6.2.1 Die Zuweisung an eine einfache Variable.- 6.2.2 Die Mehrfachzuweisung.- 6.3 Die Sequenz.- 6.4 Die Alternative (if-Anweisung).- 6.5 Die Iteration (Schleife).- 6.5.1 Die while-Schleife.- 6.5.2 Die repeat-Schleife.- 6.6 Termination von Schleifen.- 6.7 Verifikation der while-Schleife.- 7. Entwickeln von Schleifen.- 7.1 Entwickeln einer Schleife aus einer gegebenen Invariante und Terminationsfunktion.- 7.2 Entwickeln von Invarianten aus gegebenen Spezifikationen.- 7.2.1 Die Invariante als Verallgemeinerung der Postcondition.- 7.2.2 Weglassen einer Bedingung.- 7.2.3 Konstante durch Variable ersetzen und Bereich der Variablen angeben.- 7.2.4 Kombinieren von Pre- und Postcondition.- 8. Die schwchste Precondition (weakest precondition).- 8.1 Verifikation mit wp.- 8.2 Die wp der einzelnen Anweisungen.- 8.2.1 wp der Leeranweisung.- 8.2.2 wp der Zuweisung.- 8.2.3 wp der Mehrfachzuweisung.- 8.2.4 wp der Sequenz.- 8.2.5 wp der Alternative.- 8.2.6 wp der Iteration.- 8.3 Die wp als Prdikatentransformation.- 8.4 Definition der Semantik mit Hilfe der schwchsten Precondition.- 8.5 Eigenschaften der wp.- 8.6 Die schwchste Precondition fr die Termination.- 9. Beispiele fr Programmentwicklungen.- 9.1 Sortieren von Feldern.- 9.1.1 Sortieren durch direktes Einfgen.- 9.1.2 Sortieren durch Minimumsuche.- 9.2 Binre Suche in einem Feld.- 9.3 Die Datenstruktur Heap (Halde).- 9.4 Heapsort.- 9.5 Die M kleinsten Elemente von N Elementen.- 9.6 Maximaler Kursgewinn bei Wertpapieren.- 10. Unterprogramme (Prozeduren).- 10.1 Die Prozedurdeklaration.- 10.2 Der Prozeduraufruf.- 10.3 Die schwchste Precondition des Prozeduraufrufs.- 10.4 Verifikation des Prozeduraufrufs.- 10.5 Spezifikation des Prozedurrumpfes mit externen Variablen.- 10.6 Verwendung von Variablen-Parametern.- 10.7 Eine verallgemeinerte Konsequenz-Regel.- 11. Invertieren von Programmen.- 11.1 Beispiele fr inverse Anweisungen.- 11.2 Invertieren der zusammengesetzten Anweisung.- 11.3 Invertieren der alternativen Anweisung.- 11.4 Invertieren von Schleifen.- 11.5 Eine Analogie zum tglichen Leben.- 12. Parallele Programme.- 12.1 Zusammensetzen von parallelen Programmen.- 12.2 Beispiele fr parallele Programme.- 12.2.1 Summe der Elemente eines Feldes.- 12.2.2 Skalarprodukt zweier Vektoren.- 12.2.3 Matrixmultiplikation.- A. Lsungen der Aufgaben.- B. Syntax der Zusicherungen.- C. Verifikationsregeln und wp.- D. Aufwand von Verfahren.