| book details |

Automatische Komplexitätsanalyse funktionaler Programme

By (author) Wolf Zimmermann

| on special |

normal price: R 2 306.95

Price: R 2 076.95

| add to trolley |

| book description |

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.