Effiziente Algorithmen (SS 2006)

Peter Rossmanith

Bereich

4+2 SWS Vorlesung im Bereich Theoretische Informatik
und im Vertiefungsgebiet Effiziente Algorithmen

Zeit und Ort

Mittwochs 10:00-11:30 Uhr und Freitags 10:00-11:30 Uhr im Raum AH VI (Informatikgebäude)

Voraussetzungen

Stoff des Informatikgrundstudiums und der zugehörigen Mathematikvorlesungen.

Inhalt

Die Vorlesung gibt einen Überblick über verschiedene Gebiete der Algorithmik. Im Zentrum der Vorlesung steht die theoretische Analyse der vorgestellten Algorithmen bezüglich ihrer Korrektheit, Laufzeit und Güte. Die Themenauswahl berücksichtigt insbesondere die praktische Relevanz der vorgestellten algorithmischen Konzepte. Im Einzelnen widmen wir uns den folgenden Themen.

• Flüsse und Matchings
• Lineare Programmierung
• Algorithmische Geometrie
• Randomisierte Algorithmen
• Approximationsalgorithmen
• Online-Algorithmen

Literatur

Hier sind einige Folien (hier mit vier Folien pro Seite zum Drucken) über Flußalgorithmen, die nützlich sein könnten und hier ist ein Skript von Berthold Vöcking zu finden, das für die ganze Vorlesung relevant ist.

	Introduction to Algorithms. Will man, aus welch merkwürdigen Gründen auch immer, nur ein Buch über Algorithmen lesen, dann sollte es dieses sein.
	The Art of Computer Programming. Hier ist besonders der dritte Band interessant. Diese Bücher sind in der Fachbereichsbibliothek und in der Lehrbuchsammlung in ausreichender Menge vorhanden.

---

Peter Rossmanith