Hauptinhalt

CS 627 — Höhere Algorithmik
(engl. Advanced Algorithmics)

Niveaustufe, Verpflichtungsgrad Vertiefungsmodul, abhängig vom importierenden Studiengang
Lehr- und Lernformen,
Arbeitsaufwand		 Vorlesung (4 SWS), Übung (2 SWS),
270 Stunden (90 Std. Präsenzzeit, 180 Std. Selbststudium)
Leistungspunkte,
Voraussetzungen zum Erwerb		 9 LP
Studienleistung(en): Erreichen von mindestens 50 Prozent der Punkte aus den wöchentlich zu bearbeitenden Übungsaufgaben und mündliche Präsentation der Lösung von mindestens zwei der Übungsaufgaben.
Prüfungsleistung: Mündliche Prüfung (Einzelprüfung)
Sprache,
Benotung		 Englisch,
Die Benotung erfolgt mit 0 bis 15 Punkten gemäß der Prüfungsordnung für den Studiengang M.Sc. Informatik.
Exportfach, Ursprung Informatik, M.Sc. Informatik
Dauer des Moduls,
Häufigkeit		 Ein Semester,
Unregelmäßig
Modulverantwortliche(r) Prof. Dr. Sebastian Wild

Inhalt

  • Approximationalgorithmen
  • Parametrisierte und Exakte Algorithmen
  • Randomisierte Algorithmen
  • Linear Programming, Primal-Dual-Algorithmen
  • Komplexitätstheorie

Qualifikationsziele

Die Studierenden

  • können Algorithmen für Berechnungsprobleme aus verschiedensten Anwendungskontexten entwerfen,
  • können für ein konkretes Berechnungsproblem einen adäquaten algorithmischen Ansatz aus einer Reihe fortgeschrittener algorithmischer Techniken auswählen,
  • können die Güte von Algorithmen in verschiedenen Analysemodellen beurteilen,
  • können die algorithmische Schwierigkeit von Berechnungsproblemen nachweisen.

Voraussetzungen

Keine. Empfohlen werden die Kompetenzen, die in den Modulen Algorithmen und Datenstrukturen sowie Effiziente Algorithmen vermittelt werden.


Literatur

  • J. Hromkovič: Algorithmics for Hard Problems.
  • Cygan et al. Parameterized Algorithms. Springer Verlag, 2015.
  • J. Flum, M. Grohe: Parametrized Complexity Theory.
  • M. Mitzenmachen, E. Upfal: Probability and Computing - Randomized Algorithms and Probabilistic Analysis.
  • S. Arora, B. Barak: Computation Complexity - A Modern Approach.
  • V. Vazirani: Approximation Algorithms.
  • Kleinberg, Tardos. Algorithm Design. Pearson/Addison-Wesley, 2006.
  • Skiena, Steven S. The Algorithm Design Manual. Springer Verlag, 2008.
  • Williamson, Shmoys. The Design Of Approximation Algorithms. Cambridge University Press, 2011.



Bitte beachten Sie:

Diese Seite beschreibt ein Modul gemäß dem im Wintersemester 2025/26 aktuellsten gültigen Modulhandbuch. Die meisten für ein Modul gültigen Regeln werden nicht durch die Prüfungsordnung festgelegt, und können daher von Semester zu Semester aktualisiert werden. Folgende Versionen liegen im Online-Modulhandbuch vor:

Das Modulhandbuch enthält alle Module, unabhängig vom aktuellen Veranstaltungsangebot, vergleichen Sie dazu bitte das aktuelle Vorlesungsverzeichnis in Marvin.

Die Angaben im Online-Modulhandbuch wurden automatisch erstellt. Rechtsverbindlich sind die Angaben der Prüfungsordnung. Wenn Ihnen Unstimmigkeiten oder Fehler auffallen, sind wir für Hinweise dankbar.