392118 Analyse von Algorithmen (V) (SoSe 2004)

Diese Vorlesung führt in die grundlegenden Methoden und Konzepte der
Komplexitätsanalyse von Algorithmen ein. Nach einer kurzen Wiederholung
bereits bekannter Begriffe wie Rekursion und O-Notation werden wir die
Laufzeiten konkreter Algorithmen analysieren und dabei das notwendige
Handwerkszeug aus Kombinatorik, Wahrscheinlichkeitstheorie und
Graphentheorie erarbeiten. Dazu gehören insbesondere das Aufstellen von
Rekurrenzgleichungen zur Beschreibung des Algorithmus, deren Lösung mit
erzeugenden Funktionen sowie Bäume als spezielle Graphen mit ihren
Eigenschaften. Ziel der Vorlesung ist es, den Hörern die wichtigsten
Werkzeuge zur Analyse von Algorithmen zu vermitteln und ihre Anwendung an
Beispielen zu zeigen.

Requirements for participation, required level

Algorithmen und Datenstrukturen I + II

Bibliography

• Robert Sedgewick and Philippe Flajolet, An Introduction to

the Analysis of Algorithms, Addison-Wesley, 1996.

• Donald E. Knuth, The Art of Computer Programming,

Addison-Wesley, 3rd ed., 1997.

External comments page

http://www.cebitec.uni-bielefeld.de/groups/ims/teaching/algoanalyse.html