AG Algorithmen und Komplexität

Sommersemester 2017

Sebastian bietet im Sommersemester 2017 die Vorlesungen Advanced Algorithmics an.


 

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)

Betreuer

Die Vorlesung wird im Wintersemester 2012/13 von Raphael Reitzig und Sebastian Wild betreut.