MIN111: Effiziente Algorithmen

Kernmodule

MIN111: Effiziente Algorithmen

Kurzporträt MIN111: Effiziente Algorithmen
Worum geht es? Effiziente Algorithmen vertieft den Entwurf und die Analyse leistungsfähiger Verfahren für anspruchsvolle Problemstellungen. Die Studierenden beschäftigen sich mit Entwurfsmethoden, Graphalgorithmen, Datenstrukturen, algorithmischer Geometrie sowie exakten, approximativen und randomisierten Verfahren.
Wofür braucht man es? Die Kompetenzen werden gebraucht, wenn Software nicht nur korrekt, sondern auch schnell, skalierbar und ressourcenschonend sein muss. Sie helfen, Lösungsansätze fundiert auszuwählen, Laufzeit und Speicherbedarf einzuschätzen und technische Grenzen realistisch zu bewerten.
Wieso ist es interessant? Interessant ist das Modul, weil kleine algorithmische Entscheidungen große Auswirkungen auf Machbarkeit und Performance haben können. Viele praktische Probleme wirken zunächst ähnlich, verlangen aber sehr unterschiedliche algorithmische Ideen und Abwägungen.
Modulverantwortung

Prof. Dr. Jochen Rethmann

Lehrperson(en)

Prof. Dr. Jochen Rethmann

Verwendbarkeit

Master Informatik

Fächergruppe

Informatik

Modultyp
Wahlpflicht
Sprache

Deutsch

Angebot

Wintersemester

Dauer

1 Semester

Credits

5 ECTS

Benotung

Deutsche Notenskala 1-5

SWS

4SL

Workload
Präsenzstudium: 45 Std. Selbststudium: 90 Std.
Engl. Titel

Efficient Algorithms

Empfohlene Voraussetzungen

Gute Programmierkenntnisse in mindestens einer Programmiersprache, grundlegende Kenntnisse in den Bereichen Algorithmen und Datenstrukturen, Kombinatorik, Stochastik, Berechenbarkeit, Komplexitätsklassen und Turingmaschinen.

Lernergebnisse / Kompetenzen
WAS

Mit erfolgreichem Abschluss des Moduls sind die Studierenden in der Lage, ausgehend von gelernten Konzepten effiziente Algorithmen und geeignete Datenstrukturen für viele Fragestellungen aus der Praxis zu entwickeln und zu bewerten, verschiedene Klassen von Algorithmen zu differenzieren und sich in neue technisch-wissenschaftliche Themen einzuarbeiten.

WOMIT

Die Studierenden erreichen dieses Lernergebnis, indem sie

  • verschiedene Algorithmen und Datenstrukturen in einer Programmiersprache implementieren sowie ihre Effizienz vergleichen.
  • Algorithmen hinsichtlich Laufzeit und Speicherverbrauch analysieren und geeignete Lösungsansätze für unterschiedliche Problemstellungen vergleichen.
  • die Lehrveranstaltungen nachbereiten, Literatur studieren sowie zusätzliche Übungsaufgaben eigenständig lösen.
WOZU

Die Studierenden nutzen diese Kompetenzen, um Programme zu entwickeln, die auch bei großen Eingaben schnell, ressourcenschonend und skalierbar arbeiten. Damit können sie algorithmische Lösungsansätze in Folgemodulen, Projekten und der beruflichen Praxis fundiert auswählen und bewerten.

Inhalte
  • Entwurfsmethoden wie bspw. Divide and Conquer, dynamische Programmierung, Greedy, Backtracking
  • Graph-Algorithmen wie bspw. Zusammenhangsprobleme, Netzwerkfluss, Matching
  • spezielle Graphklassen wie bspw. Co-Graphen, Vergleichbarkeits-, chordale und planare Graphen
  • Algorithmische Geometrie wie bspw. Voronoi-Diagramme, konvexe Hülle, Scan-Line-Verfahren
  • Exponentialzeit-Algorithmen bspw. für SAT, Independent Set und Vertex-Cover
  • Datenstrukturen wie bspw. Union-Find-Strukturen, Fibonacci-Heaps, balancierte Binärbäume, B-Bäume, Tries, Intervallbäume, Segmentbäume, Prioritätssuchbäume
  • spezielle Themen wie bspw. randomisierte Algorithmen, Approximations- und Online-Algorithmen
Prüfungsvorleistung

Keine angegeben.

Prüfungsleistung

Klausurarbeit (120 Minuten).

Literatur
  • Ottmann, Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag.
  • Cormen, Leiserson, Rivest: Introduction to Algorithms. MIT Press.
  • Knuth: The Art of Computer Programming. Addison-Wesley.
  • Gurski, Rothe, Rothe, Wanke: Exakte Algorithmen für schwere Graphenprobleme.
  • Klein: Algorithmische Geometrie. Springer Verlag.
  • Hromkovič: Randomisierte Algorithmen. Vieweg + Teubner Verlag.