By Uwe Schöning

Dieses Lehrbuch der Algorithmik stellt die grundlegenden Algorithmen dar und vermittelt die Prinzipien von Algorithmusanalyse und -entwurf. In einem einführenden Kapitel werden die benötigten Grundbegriffe aus der Theoretischen Informatik, der Stochastik und der Komplexitätsanalyse bereitgestellt. Die folgenden Kapiteln behandeln die Gebiete Sortieren und Selektion, Hashing, Dynamisches Programmieren, Greedy-Algorithmen, Algorithmen auf Graphen, Optimiertes Suchen in Bäumen, Datenkompression sowie algebraische Algorithmen, String Matching und Heuristiken. Im abschließenden Kapitel werden die effizientesten Algorithmen für das Erfüllbarkeitsproblem der Aussagenlogik diskutiert. Prof. Schöning gelingt durch seinen verständlichen Stil, viele Beispiele und das Aufzeigen von Querverbindungen eine lebendige und intestine verständliche Gesamtdarstellung der Algorithmik.

Show description

Read Online or Download Algorithmik (Spektrum Lehrbuch) PDF

Best algorithms and data structures books

Music-inspired harmony search algorithm: theory and applications

Calculus has been utilized in fixing many medical and engineering difficulties. For optimization difficulties, in spite of the fact that, the differential calculus method occasionally has a disadvantage while the target functionality is step-wise, discontinuous, or multi-modal, or whilst determination variables are discrete instead of non-stop.

Abstract Data Types Algorithms

Meant as a moment path on programming with information constructions, this ebook is predicated at the suggestion of an summary facts style that is outlined as an summary mathematical version with an outlined set of operations. The specification of information forms and their corresponding operations are provided in a sort at once representable in a Pascal-like language.

Genetic Algorithms - Principles and Perspectives: A Guide to GA Theory

Genetic Algorithms (GAs) became a powerful software for fixing not easy optimization difficulties. As their recognition has elevated, the variety of GA purposes has grown in additional than equivalent degree. Genetic set of rules conception, even if, has no longer stored speed with the becoming use and alertness of gasoline.

Parsing Theory. Volume 1: Languages and Parsing

The idea of parsing is a crucial program zone of the idea of formal languages and automata. The evolution of modem high-level programming languages created a necessity for a basic and theoretically dean technique for writing compilers for those languages. It used to be perceived that the compilation method needed to be "syntax-directed", that's, the functioning of a programming language compiler needed to be outlined thoroughly by means of the underlying formal syntax of the language.

Extra resources for Algorithmik (Spektrum Lehrbuch)

Example text

T(l+6)E[S] (Unabhängigkeit) t(l+6)E[S\ t(l+6)E[S] - (wegen 1 + x < e x ) f(l+*)£[S] t(l+S)E[S] * Durch Wahl von t = 1 + S wird dieser Ausdruck minimiert und wir erhalten: „6 Pr(S > (1 + S)E[S]) < \ E W Die zweite Chernoff-Ungleichung beweist man analog. Nachdem man zunächst die Abschätzung Pr(S <(1-S)E[S)) < erhält, setzt man t = 1/(1 — S) ein. 12 werden wir noch einen Spezialfall (und eine Verschärfung) dieser Abschätzung herleiten. Das folgende Diagramm zeigt den Funktions verlauf von e5/(l -f (1 + S)E[S]) < Pr(S < (1 - S)E[S]) < Seien X und Y zwei unabhängige Zufallsv^ablen, die nur Werte aus der endlichen Menge M annehmen können.

Da uns am Ende nur eine Lösungsfunktion T der Form T(n) — 0 ( . . ) interessiert, können wir die asymptotische Notation auch schon in der Rekursionsgleichung selber verwenden (Beispiel: T(n) = Q(n) + T (n/2)) und dadurch die Analyse wesentlich vereinfachen. Eine gewisse Vorsicht ist hierbei aber vonnöten. Betrachten wir zum Beispiel die iterative Einsetzungsmethode: T(n) = 0(n)+T(n/2) = 6(n) + 0(n/2) + T(n/4) = 0(n) + 0(n/2) + 0(n/4) + . . Bei dem letzten Ausdruck muss man nun aber wissen, dass die in den verschiedenen 0-Notationen versteckten Konstanten immer dieselben sind!

Im Folgenden sei 0 < p < \: pn n / \ Tl[i)pi(l-p)n-i l = (p+(i-p)) i=0 ^ ' ^ (1 — p)n / i=0 Hieraus ergibt sich P n /

Download PDF sample

Download Algorithmik (Spektrum Lehrbuch) by Uwe Schöning PDF
Rated 4.77 of 5 – based on 33 votes