Skip to main content
main-content

Über dieses Buch

Es gibt im Bereich der Softwaretechnik viele Werkzeuge, die den Programmentwicklungsprozeß unterstützen. Sie stellen die Korrektheit der Implementierung sicher, nicht aber ihre Effizienz. Die vorliegende Arbeit führt daher eine Methode ein, die es erlaubt, die Zeitkomplexität funktionaler Programme automatisch zu ermitteln. Die Grundidee dieser Methode besteht darin, ein funktionales Programm in ein System von Rekurrenzgleichungen zu übersetzen, dessen Lösung das Zeitverhalten des Programms angibt. Durch Einführung von bedingten Rekurrenzen und Rekurrenzfamilien ist es möglich, obere und untere Schranken für die Zeitkomplexität zu finden. Um die mittlere Zeitkomplexität zu bestimmen, müssen Wahrscheinlichkeiten dafür berechnet werden, daß im Programm vorkommende Bedingungen wahr bzw. falsch werden. Diese Wahrscheinlichkeiten werden anhand einer probabilistischen Semantik des Programms berechnet. Um möglichst genaue Schranken für die Zeitkomplexität zu erhalten, muß eine Abhängigkeitsanalyse durchgeführt werden. Dies ermöglicht eine genaue Analyse von Divide-and-Conquer-Programmen.

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Einleitung

Zusammenfassung
Es gibt eine Vielzahl von Werkzeugen, die den Prozeß des Programmierens unterstützen (z.B. Transformationssysteme, Automatisierung von Programmentwicklungsmethoden). Allen diesen Werkzeugen ist gemeinsam, daß sie eine Menge von Regeln enthalten. Die sukzessive Anwendung dieser Regeln auf eine formale Spezifikation soll zu einer effizienten und korrekten Implementierung der Spezifikation führen. In der Tat stellen diese Werkzeuge die Korrektheit einer Implementierung bezüglich ihrer Spezifikation sicher. Andererseits stellen diese Werkzeuge nicht sicher, daß eine Implementierung effizient ist. Normalerweise garantieren nur wenige Regeln und Methoden eine Verbesserung der Effizienz. Oft haben die Regeln und Methoden die Eigenschaft, daß sich bei ihrer Anwendung die Zeiteffizienz eines Programms verbessert. In manchen Fällen kann sich aber auch die Effizienz verschlechtern. Wenn man Strategien zur Programmentwicklung betrachtet, die solche Regeln verwenden, ist daher erst recht keine Effizienzverbesserung garantiert. Letztendlich ist der Benutzer solcher Werkzeuge selbst dafür verantwortlich, daß er tatsächlich effiziente Programme entwickelt. Es ist also nützlich, den Zeitaufwand von Programmen zu kennen, insbesondere, um im Programmentwicklungsprozeß Entwurfsentscheidungen treffen zu können. Keines der Werkzeuge unterstützt den Benutzer in der Aufgabe das Zeitverhalten eines Programms abzuschätzen. Der Werkzeugbenutzer nimmt daher (wenn überhaupt) nur eine oberflächliche Abschätzung seiner Zwischenresultate vor. Er wird im allgemeine höchstens die schlimmste und die günstigste Zeitkomplexität asymptotisch bestimmen. Eine weitaus wichtigere Rolle für die Praxis spielt der mittlere Zeitaufwand. Außerdem spielen die konstanten Summanden und Faktoren im Zeitaufwand eine nicht unerhebliche Rolle für die Effizienz des Programms.
Wolf Zimmermann

Kapitel 2. Ansätze zur automatischen Komplexitätsanalyse

Zusammenfassung
Es gibt zwei grundsätzlich verschiedene Ansätze zur automatischen Komplexitätsanalyse funktionaler Programme. Der eine basiert auf einem Homorphismus zwischen Typdefinitionen und Gleichungen für erzeugende Funktionen, die die Anzahl der Objekte der Größe n definiert, und auf einem Homomorphismus zwischen der Programmstruktur und Gleichung für erzeugenden Funktionen für den Zeitaufwand. Der mittlere Zeitaufwand wird dann durch Analyse der Singularitäten dieser erzeugenden Funktionen bestimmt [FSZ88].
Wolf Zimmermann

Kapitel 3. Das Maschinenmodell

Zusammenfassung
In diesem Kapitel wird die Sprache STYFL (“Simple Typed Functional Language”) definiert. Dazu werden Regeln angegeben, die beschreiben, wie man Ausdrücke in dieser Sprache reduziert. Zusammen mit einer Strategie zur Auswertung ergibt sich dann die Semantik dieser Sprache. Im 2. Abschnitt schließlich wird ein Zeitbegriff auf dieser Sprache eingeführt.
Wolf Zimmermann

Kapitel 4. Das Abbilden auf Rekurrenzen

Zusammenfassung
In diesem Kapitel wird gezeigt, wie aus einem gegebenen Programm und einer gegebenen Funktion Rekurrenzen abgeleitet werden können, die die Komplexität dieser Funktion definieren. Im nächsten Kapitel wird dann gezeigt wie diese gelöst werden.
Wolf Zimmermann

Kapitel 5. Das Lösen von Rekurrenzen

Zusammenfassung
In diesem Kapitel wird die 2. Phase der Komplexitätsanalyse diskutiert. Nachdem in der ersten Phase Rekurrenzsysteme erzeugt wurden, werden diese in der zweiten Phase gelöst. In einem Vorverarbeitungsschritt werden die einzelnen Rekurrenzen so geordnet, daß sie in der sortierten Reihenfolge bearbeitet werden können. Die Rekurrenzsysteme, die man nach der 1. Phase erhält, enthalten evtl. verschachtelte Rekurrenzen. Lösungen von Rekurrenzen werden dann in die noch nicht gelösten Rekurrenzen eingesetzt. Man kann dann folgende Fälle unterscheiden:
(i)
Die Rekurrenz oder das Rekurrenzsystem kann nach Standardmethoden gelöst werden (vgl. Anhang A).
 
(ii)
Die zu lösende Rekurrenz ist eine bedingte Rekurrenz
 
(iii)
Die zu lösende Rekurrenz benutzt bedingte Rekurrenzen
 
Wolf Zimmermann

Kapitel 6. Probabilistische Semantik

Zusammenfassung
Es soll gezeigt werden, daß eine probabilistische Semantik (nach [Koz81]) dazu benutzt werden kann, um Wahrscheinlichkeiten dafür zu berechnen, daß im Programm vorkommende Bedingungen wahr sind. In der probabilistischen Semantik werden Funktionen als wahrscheinlichkeitsmaßtransformierende Funktionen angesehen. Es wird eine Transformation und Methodik angegeben, die die benutzerdefinierten Funktionen in wahrscheinlichkeitsmaßtransformierende Funktionen überführt. Einen Ansatz der ähnliches erreichen soll, und auf Kozens Semantik basiert wurde für FP-Programme in [HC88] durchgeführt. Er definiert und verwendet attributierte probabilistische Grammatiken, um Maße auf FP-Listen zu definieren. Seine Methodik erscheint allerdings schwer automatisierbar. In diesem Kapitel werden Techniken zur Definition von Maßen für allgemeine, algebraisch spezifizierte Datenstrukturen eingeführt.
Wolf Zimmermann

Kapitel 7. Zusammenfassung und Ausblick

Zusammenfassung
Im Zusammenhang mit der Programmentwicklung durch Programmtransformationen gewinnen Systeme zur automatischen Komplexitätsanalyse zunehmend an Bedeutung. Sie dienen u.a. dazu, Zwischenresultate, die während einer solchen Entwicklung entstehen, zu beurteilen und unterstützen damit den Entwickler. Oft sind viele Regeln auf einen solchen Zwischenzustand anwendbar, wobei der Effekt bzgl. der Komplexität bei der Anwendung einer Regel oft nicht bestimmt werden kann. Das Beispiel der Sortieralgorithmen zeigte, daß neben dem schlechtesten und besten Fall auch der mittlere Fall analysiert werden muß, und daß eine Berechnung der Konstanten unumgänglich ist. Die Zeitkomplexität wird in Abhängigkeit von der Größe der Eingabe ausgedrückt.
Wolf Zimmermann

Backmatter

Weitere Informationen