Algorithmen und Komplexität

Dozent

Prof. Dr. Thomas Holenstein

Übungsleitung

Thomas Rast

Prüfungseinsicht

Die Prüfungen können bei Marianna Berger (CAB H37.2) ab dem 1. März 2010 zu folgenden Zeiten eingesehen werden:

Zeit und Ort

Vorlesung: Dienstag 8:15 - 10:00 (HG D1.2)

Die erste Vorlesung findet am 22. September 2009 statt.

Übung: Donnerstag 16:15 - 17:00

Die erste Übung findet am 1. Oktober 2009 statt.

Inhalt

Die Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Themengebiete sind:

• Einführung: RAM-Maschine, Datenstrukturen
• Algorithmen: Sortieren, Medianbestimmung, Matrixmultiplikation, kürzeste Pfade, minimale spannende Bäume
• Paradigmen des Algorithmenentwurfs: Divide&Conquer, dynamische Programmierung, Greedy
• Datenstrukturen: Suchbäume, Wörterbücher, Priority Queues
• Komplexitätstheorie: Klassen P und NP, NP-vollständig, Satz von Cook, Beispiele für Reduktionen
• Ausblick: Optimierungsprobleme, Approximationsalgorithmen

Alte Klausuren (nur mit ETH-Login)

Übungen

Zusammenfassungen (von Mattia Bergomi)

Literatur

T. Cormen, C. Leiserson, R. Rivest:

Introduction to Algorithms, MIT Press, 1990

H.J. Prömel, A. Steger:

The Steiner Tree Problem: A Tour Through Graphs, Algorithms and Complexity, Vieweg 2002

R. Sedgewick:

Algorithmen in C++, Pearson, 2003

S Baase, A. van Gelder:

Computer Algorithms, Addison Wesley, 2000

G. Brassard, P. Bratley:

Fundamentals of Algorithms, Prentice Hall, 1996

J. Kleinberg, E. Tardos:

Algorithm Design, Addison Wesley, 2005

T. Ottmann , P. Widmayer:

Algorithmen und Datenstrukturen, Spektrum, 2002