Entwurf und Analyse von Algorithmen (WS 12/13)
Diese Vorlesung richtet sich sowohl an Studierende der Informatik als auch der Angewandten Informatik bei variierenden Lernzielen, denen durch unterschiedliche Prüfungsaufgaben Rechnung getragen wird. Übergreifend behandelt die Vorlesungen Strategien zum Entwurf und zur Analyse von Algorithmen, die Entwicklung und Implementierung effizienter Algorithmen und Bestimmung unterer Schranken für verschiedene Probleme aus der Informatik. Darüber hinaus bietet sie eine Einführung in die Komplexitätstheorie und skizziert Ansätze zur Lösung schwerer Optimierungsprobleme.
Literatur
Alle für die Vorlesung wichtigen Inhalte werden umfänglich im Buch Entwurf und Analyse von Algorithmen behandelt, das im Teubner-Springer Verlag erschienen ist. Wer die verschiedenen Inhalte vertiefen möchte oder nach einer alternativen Abhandlung sucht, sei auf folgende Werke verwiesen:
- Aho, Hopcroft, Ullman: The Design and Analysis of Computer Algorithms (INF 335/001, L inf 181)
- Ottmann, Widmayer: Algorithmen und Datenstrukturen
Mathematische Grundlagen
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science
- Theoretical computer science cheat sheet
Berechnungsmodelle
- Uwe Schöning: Theoretische Informatik, kurz gefasst
Algorithmenanalyse
- Donald E. Knuth: The Art of Computer Programming, Band 1 und 3
- Robert Sedgewick & Philippe Flajolet: Introduction to the Analysis of Algorithms
Komplexitätstheorie
- Michael Garey, David Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness
Algorithmik, Datenstrukturen, Entwurfsmethoden
- Brassard, Bratley: Algorithmik
- Cormen, Leiserson, Rivest, Stein: Algorithms (auch auf Deutsch erhätlich)
- Robert Sedgewick, Kevin Wayne, Algorithms (fourth edition)
- Uwe Schöning: Algorithmik
Einführung in Java
(für die praktischen Übungen)
- Sedgewick, Wayne: Introduction to Programming in Java
Teile sind auch online erhältlich: http://introcs.cs.princeton.edu/java/home/
Betreuer
Die Vorlesung wird im Wintersemester 2012/13 von Raphael Reitzig und Sebastian Wild betreut.