Automatische Komplexitätsanalyse Funktionaler Programme

ISBN-13: 9783540534303 / Angielski / Mikrofilm / 1990 / 196 str.

Wolf Zimmermann

Opis

Es gibt im Bereich der Softwaretechnik viele Werkzeuge, die den Programmentwicklungsprozess unterstutzen. Sie stellen die Korrektheit der Implementierung sicher, nicht aber ihre Effizienz. Die vorliegende Arbeit fuhrt daher eine Methode ein, die es erlaubt, die Zeitkomplexitat funktionaler Programme automatisch zu ermitteln. Die Grundidee dieser Methode besteht darin, ein funktionales Programm in ein System von Rekurrenzgleichungen zu ubersetzen, dessen Losung das Zeitverhalten des Programms angibt. Durch Einfuhrung von bedingten Rekurrenzen und Rekurrenzfamilien ist es moglich, obere und untere Schranken fur die Zeitkomplexitat zu finden. Um die mittlere Zeitkomplexitat zu bestimmen, mussen Wahrscheinlichkeiten dafur berechnet werden, dass im Programm vorkommende Bedingungen wahr bzw. falsch werden. Diese Wahrscheinlichkeiten werden anhand einer probabilistischen Semantik des Programms berechnet. Um moglichst genaue Schranken fur die Zeitkomplexitat zu erhalten, muss eine Abhangigkeitsanalyse durchgefuhrt werden. Dies ermoglicht eine genaue Analyse von Divide-and-Conquer-Programmen."

Spis treści

1 Einleitung.- 2 Ansätze zur automatischen Komplexitätsanalyse.- 3 Das Maschinenmodell.- 4 Das Abbilden auf Rekurrenzen.- 5 Das Lösen von Rekurrenzen.- 6 Probabilistische Semantik.- 7 Zusammenfassung und Ausblick.- A Das Lösen von Rekurrenzen und Rekurrenzsystemen.- A.1 Lineare Rekurrenzen 1-ter Ordnung.- A.3 Rekurrenzsysteme.- A.4 Die Methode der erzeugenden Funktionen.- B Die Korrektheit der Übersetzungen.- C Eigenschaften von Folgen und Funktionen.- C.1 Folgen.- C.2 Funktionen.- Literatur.