People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.
Mathematical models have been a crucial inspiration for all scientific activity, even though they are only approximate idealizations of real-world phenomena. Inside a computer, such models are more relevant than ever before, because computer programs create artificial worlds in which mathematical models often apply precisely. I think that's why I got hooked on analysis of algorithms when I was a graduate student, and why the subject has been my main life's work ever since.
D. E. Knuth

Analyse von Algorithmen (WS 97/98)

Peter Rossmanith

Bereich

2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Vertiefungsvorlesung im Bereich Algorithmen

Zeit und Ort

Freitag, 10.00-12.00 Uhr, Hörsaal 2100 (Stammgelände)

Vorraussetzungen

Stoff des Informatikgrundstudiums und der zugehörigen Mathematikvorlesungen. In dieser Vorlesung wird keine schwierige Mathematik verwendet, sondern lediglich Einfaches, beispielsweise endliche Summen, Binomialkoeffizienten, usw. Allerdings kann auch einfache Mathematik schwierig sein. Vor nicht langer Zeit stand ich vor der Aufgabe folgenden Ausdruck zu vereinfachen, welcher in einer Analyse eine Rolle spielte:
Mathematischer Ausdruck
Ähnliche Probleme tauchen oft in der Analyse von Algorithmen auf, weswegen die geschickte Manipulation komplizierter Summen eine wichtige Rolle spielen kann.

Eine Vorraussetzung für diese Vorlesung ist daher, bei solchen Ausdrücken nicht wegzulaufen. Mit ein wenig Übung sind solche Ausdrücke aber gar nicht so schwer zu zähmen.

Inhalt

Die Vorlesung vermittelt die notwendigen Techniken, welche zur Analyse von Algorithmen benötigt werden, und wendet sie an zahlreichen Beispielen praktisch an. Am Ende der Vorlesung werden einige wichtige und nicht triviale Probleme analysiert, z.B. hashing.
  1. Was bedeutet Analyse von Algorithmen? Wozu wird sie benötigt?
  2. Rekursionsgleichungen
  3. Generating Functions
  4. Asymptotische Abschätzungen
  5. Analyse von Hashing und anderen wichtigen Algorithmen

Handouts

Literatur

Buch

An Introduction to the Analysis of Algorithms von Robert Sedgewick und Phillippe Flajolet ist das Buch, welchem die Vorlesung folgt.

Weiterführende Literatur

Buch The Art of Computer Programming. Hier ist besonders das erste Kapitel interessant und der dritte Band. Diese Bücher sind in der Lehrbuchsammlung in ausreichender Menge vorhanden und können während des ganzen Semesters ausgeliehen werden.
Buch Analysis of Algorithms - Mathematical Methods, Computational Tools. Dieses Buch entspricht in etwa An Introduction to the Analysis of Algorithms, ist aber vielleicht ein wenig mehr mathematisch orientiert. Ebenfalls sehr gut.
Buch Concrete Mathematics. Tolles Buch, welches alle notwendigen mathematischen Methoden enthält. Es ist im Prinzip eine ausführlichere Version des ersten Kapitels von The Art of Computer Programming. Sehr viele Aufgaben mit Lösungen.
Buch Mathematics for the Analysis of Algorithms. Dieses Buch enthält fortgeschrittenere mathematische Techniken, welche an vielen Beispielen erläutert werden. Sehr schwierig!

Weitere Informationen zu Analyse von Algorithmen


Peter Rossmanith, 1997-10-14

vi powered Valid HTML 3.2!