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 process 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

Architectures for Adaptive Software Systems: 5th International Conference on the Quality of Software Architectures, QoSA 2009, East Stroudsburg, PA, USA, ... Programming and Software Engineering)

This e-book constitutes the completely refereed lawsuits of the fifth overseas convention at the caliber of software program Architectures, QoSA 2009, held in East Stroudsbury, PA, united states in June 2009, at the side of the twelfth foreign Symposium on part established software program Engineering (CBSE 2009). The thirteen revised complete papers have been rigorously reviewed and chosen from 33 submissions.

Pro Core Data for iOS, Second Edition

Absolutely up to date for Xcode four. 2, seasoned middle information for iOS explains tips to use the center info framework for iOS SDK five utilizing Xcode four. 2. The publication explains either how and why to exploit center info, from easy to complex thoughts. overlaying universal and complicated patience styles, this ebook prepares any iOS developer to shop and retrieve facts properly and successfully.

Visual Language Theory

Kim Marriott Bernd Meyer conversation is among the hallmarks of people. once we consider hu­ guy verbal exchange, most folks first think about spoken and written lan­ guages. those are related in that symbols within the language are encountered and processed sequentially, both temporally as they're spoken or as char­ acters are learn throughout a web page.

Automatic Re-engineering of Software Using Genetic Programming

Computerized Re-engineering of software program utilizing Genetic Programming describes the appliance of Genetic Programming to a true international program zone - software program re-engineering more often than not and automated parallelization in particular. not like such a lot makes use of of Genetic Programming, this ebook evolves sequences of provable alterations instead of real courses.

Additional info for Automatische Komplexitätsanalyse funktionaler Programme

Sample text

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. • Im allgemeinen ist es unentscheidbar, ob eine Argumentposition relevant ist oder nicht (insbesondere wegen Bedingung (ii)). In [Weg75) ist aber ein Algorithmus angegeben, der hinreichend für irrelevante Argumentpositionen ist. Dort werden irrelevante Argumentpositionen allerdings über diesen hinreichenden Algorithmus eingeführt.

Schließlich werden im 3. Abschnitt die Unterschiede des Ansatzes von Le Metayer herausgearbeitet. Abschließend wird eine Bewertung dieser Ansätze vorgenommen. 1 Das Ermitteln von Rekurrenzen Die Rekurrenz für die Komplexität einer Funktion wird in vier Schritten ermittelt: 1. Berechnung einer Funktion, die die Komplexität des Programmes berechnet 2. Transformation dieser Funktion in eine Normalform 3. Erzeugen einer strukturell induktiven Definition der Funktion durch symbolische Auswertung der Funktion 4.

Die Operation op heißt in • diesem Fall Konstante. 4 {Algebren) (N, {0, +1}) ist eine nat-Algebra. esDie Menge der :E-Terme Tt(X) einer Sorte s über den Variablen X ist die kleinste Menge mit: (i) Jedes x E X. ist auch in Tt(X). (ii) Ist I :--+ s E :E, so ist auch I E Tt(X).

Download PDF sample

Rated 4.29 of 5 – based on 13 votes