Automatische Komplexittsanalyse funktionaler Programme [Paperback]

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.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 bereclc'