Effiziente kombinatorische Algorithmen (EffAlg)7.5 ECTS
(englische Bezeichnung: Efficient Combinatorial Algorithms)
(Prüfungsordnungsmodul: Effiziente kombinatorische Algorithmen)

Lehrveranstaltungen:

• • Effiziente kombinatorische Algorithmen
    (Vorlesung, 2 SWS, Rolf Wanka, Do, 10:15 - 11:45, 02.134-113)
  • Übung Effiziente kombinatorische Algorithmen
    (Übung, 2 SWS, Rolf Wanka)

Empfohlene Voraussetzungen:

Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:

Berechenbarkeit und Formale Sprachen (WS 2021/2022)

Inhalt:

In diesem Modul werden effiziente exakte Algorithmen für diskrete Probleme vorgestellt. Zuerst werden nichttriviale tiefensuchbasierte Linearzeitverfahren für die Berechnung zweifacher Zusammenhangskomponenten auf ungerichteten Graphen und starker Zusammenhangskomponenten auf gerichteten Graphen untersucht. Danach werden Polynomialzeit-Verfahren zur Berechnung maximaler Flüsse präsentiert. Eine Einführung in den Entwurf und die Analyse parametrisierter Algorithmen an Hand des Vertex-Cover-Problems und eine Einführung in den Bereich der sog. mild-exponentiellen Algorithmen für das Erfüllbarkeitsproblem und weiterer NP-vollständiger Probleme runden das Modul ab.

Lernziele und Kompetenzen:

Wissen

• Lernende können Wissen abrufen und wiedergeben. Sie kennen konkrete Einzelheiten wie Begriffe, Definitionen, Fakten, Regeln, Gesetzmäßigkeiten, Theorien.

Verstehen

• Lernende können Beispiele anführen, Aufgabenstellungen interpretieren oder ein Problem in eigenen Worten wiedergeben.

Anwenden

• Lernende können ein neues Problem durch Transfer des Wissens lösen.

Analysieren

• Lernende können ein Problem in einzelne Teile zerlegen und so die Struktur des Problems verstehen; sie können Zusammenhänge erkennen und Folgerungen ableiten.

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.
  

• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke. Exakte Algorithmen für schwere Graphenprobleme. Springer 2010.
  

• Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner, 2. Auflage 2009.
  

• 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.
  

• 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.
  

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Bachelor of Science)
   (Po-Vers. 2022w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Wahlpflichtbereich (Wahlpflichtmodule aus mind. 2 Vertiefungsrichtungen) | Vertiefungsrichtung Theoretische Informatik | Effiziente kombinatorische Algorithmen)

Studien-/Prüfungsleistungen:

Effiziente kombinatorische Algorithmen (Vorlesung mit Übung) (Prüfungsnummer: 843472)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet

Anteil an der Berechnung der Modulnote: 100.0 %

weitere Erläuterungen:

• Prüfungssprache: Deutsch oder Englisch. Die Unterrichts- und Prüfungssprache hängt von den Sprachkenntnissen und Präferenzen der Teilnehmerinnen und Teilnehmer ab und wird dementsprechend innerhalb der ersten zwei Wochen nach Vorlesungsbeginn festgelegt.

Erstablegung: WS 2022/2023, 1. Wdh.: SS 2023

1. Prüfer:

Rolf Wanka