TI5505 Graphalgorithmen für Schwere Probleme

Modulverantwortliche
  • Dr. habil. Frank Kammer
Lehrende
  • Johannes Meintrup
Notwendige Voraussetzungen zur Teilnahme

Keine

Empfohlene Voraussetzungen zur Teilnahme

Gute Programmierkenntnisse, idealerweise rudimentäre Erfahrung mit Rust oder C/C++

Kurzbeschreibung

Dieser Kurs behandelt die algorithmischen Techniken im Entwurf und der Realisierung von effizienten Graphalgorithmen zum Lösen von schweren Problemen.

Inhalte
  • Algorithmische Techniken: Dynamic Programming, Branch-and-Bound, Heuristiken, Approximationen, Parametrisierte Algorithmen, Spezielle Graphklassen
  • Implementierung von komplexeren Algorithmen und Datenstrukturen in Rust
  • Einführung zu Komplexitätsklassen: NP, P und FPT
  • Einführung in aktuelle wissenschaftliche englischsprachige Forschung im Bereich der (Graph) Algorithmen
Qualifikations- und Lernziele

Fachkompetenzen

  • Die Studierenden können verschiedenste Methoden und Techniken im Bereich der Graphalgorithmen erklären und diese zum Lösen von schweren Problemen anwenden.
  • Sie können komplexere Graphprobleme auf theoretischer Ebene identifizieren und praktische Lösungen implementieren.

Methodenkompetenzen (fachlich & überfachlich)

  • Die Studierenden können komplexere Graphalgorithmen für schwere Probleme implementieren.
  • Sie können in der Programmiersprache Rust komplexere Programme und Bibliotheken implementieren.
  • Sie können für Probleme aus der Praxis effiziente Graphalgorithmen designen und programmieren.

Sozialkompetenzen

  • Die Studierenden können im Team arbeiten und gemeinsam Lösungen für schwere Graphprobleme entwerfen.

Selbstkompetenzen

  • Die Studierenden können eigenständig englischsprachige wissenschaftliche Publikationen im Bereich der Graphalgorithmen einem Publikum verständlich präsentieren.
ECTS-Leistungspunkte (CrP)
  • 6 CrP
  • Arbeitsaufwand 180 Std.
  • Präsenzzeit 60 Std.
  • Selbststudium 120 Std.
Lehr- und Lernformen
  • 4 SWS
  • Seminaristischer Unterricht 4 SWS
Studiensemester
  • Informatik (M.Sc. 2022)
Dauer
1 Semester
Häufigkeit des Angebots
Nach Bedarf
Unterrichtssprache
Deutsch
Bonuspunkte

Nein

Bonuspunkte werden gemäß § 9 (4) der Allgemeinen Bestimmungen vergeben. Art und Weise der Zusatzleistungen wird den Studierenden zu Veranstaltungsbeginn rechtzeitig und in geeigneter Art und Weise mitgeteilt.

Prüfungsleistungen

Prüfungsvorleistung: Hausübungen (Anzahl der Hausübungen wird den Studierenden rechtzeitig und in geeigneter Weise bekannt gegeben.)

Prüfungsleistung: Projekt

Benotung
Die Bewertung des Moduls erfolgt gemäß §§ 9, ggf. 12 (Teilleistungen), ggf. 18 (Arbeiten, Kolloquien) der Allgemeinen Bestimmungen (Teil I der Prüfungsordnung).
Verwendbarkeit
Gemäß § 5 der Allgemeinen Bestimmungen (Teil I der Prüfungsordnung) Verwendbarkeit in allen Masterstudiengänge der THM möglich.
Literatur, Medien
  • Cyan et al.: Parameterized Algorithms. Springer International Publishing.
  • Klabnik, S.; Nichols, C.: The Rust Programming Language. No Starch Press.
  • Diesel, R.: Graph Theory. Springer Verlag.

Weitere Literatur wird in der Veranstaltung bekannt gegeben.

Rechtliche Hinweise