Algorithmik (Spektrum Lehrbuch) by Uwe Schöning

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

Bayesian estimation of state-space models using the Metropolis-Hastings algorithm within Gibbs sampling

During this paper, an try is made to teach a basic strategy to nonlinear and/or non-Gaussian state-space modeling in a Bayesian framework, which corresponds to an extension of Carlin et al. (J. Amer. Statist. Assoc. 87(418} (1992) 493-500) and Carter and Kohn (Biometrika 81(3} (1994) 541-553; Biometrika 83(3) (1996) 589-601).

Statistical Analysis of Spherical Data

This can be the 1st accomplished, but truly offered, account of statistical equipment for analysing round facts. The research of knowledge, within the type of instructions in house or of positions of issues on a round floor, is needed in lots of contexts within the earth sciences, astrophysics and different fields, but the technique required is disseminated in the course of the literature.

Algorithmic Problem Solving (2007)

Algorithmic challenge fixing by means of Roland Backhouse.

2007 variation (latest version is 2011).

Additional resources for Algorithmik (Spektrum Lehrbuch)

Example text

N], n > 1, und wir verstehen n als die Eingabelänge). (1) (2) (3) max := o[l] FOR i := 2 TO n DO IF a[i] > max THEN max := a[i] * 5) ' Sei Ci der Aufwand zur Ausführung von (1). Sei C2 der Aufwand, der mit jedem einzelnen Schleifendurchlauf in (2) und (3) verbunden ist. Sei C3 der Aufwand für (4). Dann ergibt sich: wc-time^n) = ci + (n - l)(c 2 + C3) Wie sieht es mit dem average-case aus? , n darstellen. Alle n! solchen Permutationen seien gleichwahrscheinlich. ,a[n-1])) = l/n Sei Xj (j = r , .

0 < Pr(E) < 1. • Pr(Hj) = 0, Pr(M) = 1. • Pr(E) = 1 - Pr(E), wobei E das Komplementärereignis von E darstellt, also E = M-E (Negationsformel). • Pr(E UF) = Pr(E) + Pr(F) - Pr(E D F) (Siebformel). Die Siebformel lässt sich verallgemeinem auf den Fall von n Ereignissen. Es gilt: i=1 i=1 - + • • • ± Pr(Ei n • • • n En) Diese alternierende Summe berücksichtigt im ersten Term Einzelelemente, dann 2elementige Mengen, 3-elementige Mengen, usw. Der erste Term überschätzt die tatsächliche Wahrscheinlichkeit, also Pr(U^ = 1 ^i) < S L i ^ r ( ^ i ) (dies nennt man die Boole-Ungleichung).

Gn. Die einzuhaltende Randbedingung ist, dass die Gesamtgröße der eingepackten Objekte die Rucksackgröße nicht übersteigt. , Vn. Es soll eine Auswahl mitzunehmender Objekte solcherart getroffen werden, so dass der Gesamtwert der im Rucksack eingepackten Objekte maximiert wird. Formal: Gesucht ist ein 0/1-Vektor (au . . , an) e {0, l } n mit öi<7i < G und Y^ üiVi -> max i=1 i=1 Es ist bekannt, dass das 0/1 -Rucksackproblem NP-vollständig ist. Einen effizienten Algorithmus werden wir also nicht erwarten können.

Download PDF sample

Rated 4.34 of 5 – based on 17 votes