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

Lehrveranstaltungen:

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

Empfohlene Voraussetzungen:

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

Berechenbarkeit und Formale Sprachen (WS 2013/2014)

Inhalt:

• Erste Algorithmen auf Graphen: Tiefensuche, zweifache und starke Zusammenhangskomponenten

• Flüsse in Netzwerken und das Max-Flow-Min-Cut-Theorem

• Mild-exponentielle Algorithmen

• Parametrisierte Komplexität und das Vertex-Cover-Problem

• Das Erfüllbarkeitsproblem SAT
  

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

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. 2009s | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsmodul Theoretische Informatik)
2. Informatik (Bachelor of Science)
   (Po-Vers. 2009w | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsmodul Theoretische Informatik)
3. Informatik (Master of Science)
   (Po-Vers. 2010 | Wahlpflichtbereich | Säule der theoretisch orientierten Vertiefungsrichtungen | Vertiefungsmodul Theoretische Informatik)

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 %

Erstablegung: WS 2014/2015, 1. Wdh.: SS 2015

1. Prüfer:

Rolf Wanka