Seiteninterne Suche

Lehre

Effiziente kombinatorische Algorithmen

Dozenten:

Prof. Dr. rer. nat. Rolf Wanka

Modulbeschreibung:

Effiziente kombinatorische Algorithmen

Umfang/Stunden:

V2 + Ü2, 7.5 ECTS

Zielgruppe:

Vertiefung Theoretische Informatik
Bachelor- oder Master-Studium
Studenten der Informatik und Mathematik,
Interessierte Hörer anderer Studiengänge

Ort und Zeit der Vorlesung:

Dienstag, 10:15 – 11:45 Uhr, Raum 02.134-113

Ort und Zeit der Übungen:

Donnerstag, 10:15 – 11:45 Uhr, Raum 02.134-113

Video-Aufzeichung:

Die Video-Aufzeichung vom Wintersemester 2016/17 ist hier aus dem Uni-Netz frei zugänglich.

Anmeldung:

Bitte melden Sie sich im EST für die Vorlesung an. Benutzen Sie im EST die Veranstaltungsanmeldung. Dort können Sie die Veranstaltung Effiziente kombinatorische Algorithmen (WS 17/18) auswählen. Das Anmeldepasswort erhalten Sie in der Vorlesung und in der Übung. Als Bestätigung für die erfolgreiche Anmeldung erhalten Sie eine Email. Diese Anmeldung dient nicht der Prüfungsanmeldung sondern führt lediglich dazu, dass Sie in den Mailverteiler zu dieser Vorlesung aufgenommen werden.

Inhalte:

  • Algorithmen auf Graphen: Tiefensuche, zweifache und starke Zusammenhangskomponenten
  • Flüsse in Netzwerken und das Max-Flow-Min-Cut-Theorem
  • Parametrisierte Komplexität und das Vertex-Cover-Problem
  • Das Erfüllbarkeitsproblem SAT
  • Minimale Färbung von Graphen

Handouts:

Moore’s Law:

Hoares Quicksort-Aufsatz:

  • C. A. R. Hoare. Quicksort. The Computer Journal 5(1) (1961) 10-16.

Übungsblätter:

Blatt 1 (pdf)

Literatur:

  • A. V. Aho, J. E. Hopcroft, J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975.
  • Venkatesh Raman, Saket Saurabh, Somnath Sikdar. Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. Theory of Computing Systems 41 (2007) 563-587.
    doi:10.1007/s00224-007-1334-2
  • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke. Exakte Algorithmen für schwere Graphenprobleme. Springer 2010.
    doi:10.1007/978-3-642-04500-4
  • Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner, 2. Auflage 2009.
    doi:10.1007/978-3-8348-9592-9
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (2nd Edition). MIT Press, 2001.
  • Fedor V. Fomin, Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010.
    [doi:10.1007/978-3-642-16533-7]
  • Volker Heun. Grundlegende Algorithmen. Vieweg, 2. Auflage 2003.
  • Juraj Hromkovic. Algorithmics for Hard Problems. Springer, 2001.
  • Stephan Hußmann, Brigitte Lutz-Westphal (Hrsg.). Kombinatorische Optimierung erleben. Vieweg, 2007.
  • Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson / Addison Wesley, 2006.
  • Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner, 2. Auflage 2009.
  • Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications , 1998.
  • Volker Turau. Algorithmische Graphentheorie. Oldenbourg, 3. Auflage 2009.
  • Vöcking et al. (Hrsg.) Taschenbuch der Algorithmen. Springer 2008.
    doi:10.1007/978-3-540-76394-9