Automatische Komplexitatsanalyse Funktionaler Programme

This title is printed to order. This book may have been self-published. If so, we cannot guarantee the quality of the content. In the main most books will have gone through the editing process however some may not. We therefore suggest that you be aware of this before ordering this book. If in doubt check either the author or publisher’s details as we are unable to accept any returns unless they are faulty. Please contact us if you have any questions.

Es gibt im Bereich der Softwaretechnik viele Werkzeuge, die den ProgrammentwicklungsprozeA unterstA1/4tzen. Sie stellen die Korrektheit der Implementierung sicher, nicht aber ihre Effizienz. Die vorliegende Arbeit fA1/4hrt 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 A1/4bersetzen, dessen LAsung das Zeitverhalten des Programms angibt. Durch EinfA1/4hrung von bedingten Rekurrenzen und Rekurrenzfamilien ist es mAglich, obere und untere Schranken fA1/4r die ZeitkomplexitAt zu finden. Um die mittlere ZeitkomplexitAt zu bestimmen, mA1/4ssen Wahrscheinlichkeiten dafA1/4r berechnet werden, daA im Programm vorkommende Bedingungen wahr bzw. falsch werden. Diese Wahrscheinlichkeiten werden anhand einer probabilistischen Semantik des Programms berechnet. Um mAglichst genaue Schranken fA1/4r die ZeitkomplexitAt zu erhalten, muA eine AbhAngigkeitsanalyse durchgefA1/4hrt werden. Dies ermAglicht eine genaue Analyse von Divide-and-Conquer-Programmen.