Download Automatische Komplexitätsanalyse funktionaler Programme by Wolf Zimmermann PDF

By Wolf Zimmermann

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 approach 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 examine von Divide-and-Conquer-Programmen.

Show description

Read Online or Download Automatische Komplexitätsanalyse funktionaler Programme PDF

Best compilers books

Advances in Computers, Vol. 37

Seeing that its first quantity in 1960, "Advances in Computing" has got down to current precise assurance of ideas in undefined, software program, computing device thought, layout and functions. It has additionally supplied participants with a medium during which they could study their topics in better intensity and breadth than that allowed via average magazine articles.

Learn Lua for iOS Game Development

So that you have an outstanding video game notion for iPhone or iPad, yet Objective-C simply turns out a piece daunting. What are your choices? The App shop is particularly choosy approximately languages, yet there's desire: Lua is a flexible, light-weight, quick, and straightforward to profit language so that you can use to construct your iOS video games and get them approved into the App shop.

A Pipelined Multi-core MIPS Machine Hardware Implementation and Correctness Proof

This monograph is predicated at the 3rd author's lectures on laptop structure, given in the summertime semester 2013 at Saarland college, Germany. It includes a gate point development of a multi-core computing device with pipelined MIPS processor cores and a sequentially constant shared reminiscence. The publication comprises the 1st correctness proofs for either the gate point implementation of a multi-core processor and likewise of a cache dependent sequentially constant shared reminiscence.

Extra resources for Automatische Komplexitätsanalyse funktionaler Programme

Example text

I. bn :<:> an < bn bis auf endlich viele n (fast immer) Beweis: Angenommen es gelte R-n (1- E)n < I/ni nur für endlich vielen. Der Konvergenzradius einer in z = a analytischen Funktion f beträgt min{ls- all s E Sing(J)}. Falls also R-n (1- E)n < I/ni nur für endlich vielen sein würde, hätte fn einen grösseren Konvergenzradius und somit eine betragsmäßig größere kleinste Singularität. Dies ist ein Widerspruch zur Voraussetzung, daß R die betragsmäßig kleinste Singularität von f ist. 29 die obere Schranke.

Xn) = R[xt, ... , Xn] eine direkt rekursive Funktionsdefinition. Der Rumpf R[xt, ... , Xn] enthalte außer Prädikaten in bedingten Anweisungen, Aufruf von LISP-Grundfunktionen und rekursiven Aufrufen keine weiteren Funktionsaufrufe. Die Argumentposition f / i heißt irrelevant, wenn (i) jeder rekursive Aufruf in R[xt, ... , Xn] die Gestalt f(tt, ... , t;-t, x;, t;+l, ... , tn) für beliebige Ausdrücke t1, ... , t;-1, t;+t, ... , tn hat, oder (ii) für alle Argumente t1, ... , tn und Eine Argumentposition t~ von f gilt: f fi heißt relevant, wenn sie nicht irrelevant ist.

L und 3. l für alle i ft, ... , ln Funktionen, so ist die Funktion {ft, ... , ln} gegeben = [ft o 1, .. 3. 5: Zeitvariablen für FP-Programme 1. Ist = e eine Funktionsdefinition, dann f 2. Für Grundfunktionen primist tpnm(w) = Tprim 3. Sind f und g FP-Ausdrücke, dann tfog(w) = Tcompo,. + tJ(g(w)) + t 9 (w) 4. Sind e, f und g FP-Ausdrücke, dann t(e-+J;g)(w) 5. Sind e1, ... J(w) = Tcon•truct,n + :~:::>e;(w) i=l und falls w = (wlo ... , wm) mit m ~ n, dann n t{e 1 , ... 6: Zeitformeln für FP-Programme 51 KAPITEL 2.

Download PDF sample

Rated 4.59 of 5 – based on 27 votes