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

Lectures:

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

Empfohlene Voraussetzungen:

It is recommended to finish the following modules before starting this module:

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:

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