Effiziente kombinatorische Algorithmen (EffAlg)7.5 ECTS

Lehrveranstaltungen:

• • Effiziente kombinatorische Algorithmen
    (Vorlesung, 2 SWS, Rolf Wanka, Do, 8:15 - 9:45, E 1.11)
  • Übung Effiziente kombinatorische Algorithmen
    (Übung, 2 SWS)

Lernziele und Kompetenzen:

• Algorithmen auf Graphen: Tiefensuche, zweifache und starke Zusammenhangskomponenten

• Kürzeste Wege: die Algorithmen von Ford/Bellman und von Dijkstra

• Minimale Spannbäume und das Union/Find-Problem

• Flüsse in Netzwerken: Das Max-Flow-Min-Cut-Theorem

Literatur:

• Vöcking et al. Taschenbuch der Algorithmen. Springer 2008. Download mit IP-Adresse der FAU

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (2nd Edition). MIT Press, 2001.

• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications , 1998

• Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson / Addison Wesley, 2006.

• Juraj Hromkovic. Algorithmics for Hard Problems. Springer, 2001.

Weitere Informationen:

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. Informatik (Bachelor of Science)
   (Po-Vers. 2009w | Praktika und Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsmodul Theoretische Informatik)

Studien-/Prüfungsleistungen:

Prüfung Effiziente kombinatorische Algorithmen

Studienleistung, benotet

weitere Erläuterungen:
Prüfungsform: mündlich, Dauer: 30, Gewichtung: 100.0%

Erstablegung: WS 2011/2012, 1. Wdh.: SS 2012

1. Prüfer:

Rolf Wanka