Effiziente kombinatorische Algorithmen

Dozent:

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

Organisatorisches:

Alle Informationen zur Vorlesung und Übung sind in dem StudOn-Kurs der Vorlesung vermerkt. Bitte treten Sie dem Vorlesungskurs bei. Der StudOn-Kurs der Übung wird nicht benutzt.

Video-Aufzeichung:

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

Anmeldung:

Bitte melden Sie sich im Studon für die Vorlesung an. Der Kurs der Übung wird nicht verwendet. Alle Informationen sind im Kurs der Vorlesung zu finden.

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
• Permutationsprobleme: TSP, Ablaufplanungen

Handouts:

• Der Algorithmus DFS-2ZK zur Berechnung zweifacher Zusammenhangskomponenten.
• Der Algorithmus DFS-SZK zur Berechnung starker Zusammenhangskomponenten.
• Die Folien zum Vortrag über Schönings Algorithmus für 3SAT finden Sie hier.
• Die Leiterplatte mit den Bohrlöchern

Moore’s Law:

• G. E. Moore. Cramming more components onto integrated circuits. Electronics 38 (1965) 114-117.

Hoares Quicksort-Aufsatz:

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

Inoffizielles Skript:

• Einleitung, DFS, BFS, Flüsse, Parametrisierte Komplexität, SAT, Permutationsprobleme und Dynamische Programmierung

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.
• Uwe Schöning, Jacobo Torán. Das Erfüllbarkeitsproblem SAT. Lehmanns Media, 2012
• Vöcking et al. (Hrsg.) Taschenbuch der Algorithmen. Springer 2008.
  doi:10.1007/978-3-540-76394-9