MLU
INF.02604.06 - Effiziente Graphenalgorithmen (Complete module description)
Original version English
INF.02604.06 5 CP
Module label Effiziente Graphenalgorithmen
Module code INF.02604.06
Semester of first implementation
Faculty/Institute Institut für Informatik
Module used in courses of study / semesters
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation valid from SoSe 2023 > Algorithmen und Theoretische Informatik (Anteil gem. § 5 Abs. 4-6, Anlage 2)
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2009/10 - SS 2016) > Datenstrukturen und effiziente Algorithmen
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Algorithmen und Theoretische Informatik
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation valid from SoSe 2023 > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Primärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2013/14 - SS 2016) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Version of accreditation valid from WS 2022/23 > Anwendungsfach Informatik (20 LP sind zu erbringen)
  • Wirtschaftsinformatik (Business Information Systems) (MA120 LP) (Master) > Wirtschaftsinformatik WirtschaftsinformatMA120, Version of accreditation (SS 2016 - SS 2020) > II. Wahlbereich Informatik
  • Wirtschaftsinformatik (Business Information Systems) (MA120 LP) (Master) > Wirtschaftsinformatik WirtschaftsinformatMA120, Version of accreditation valid from WS 2020/21 > 1.3 Informatik
  • Wirtschaftsmathematik (MA120 LP) (Master) > Wirtschaftsmathematik WirtschaftsmatheMA120, Version of accreditation (WS 2013/14 - SoSe 2023) > Informatik
Responsible person for this module
Further responsible persons
Prof. Dr. Matthias Müller-Hannemann
Prerequisites
Skills to be acquired in this module
Studierende sollen durch dieses Modul folgende Kompetenzen erwerben:
  • Sie besitzen einen Überblick über grundlegende Basisalgorithmen für graphentheoretische Probleme und deren Anwendungen.
  • Sie können Graphenalgorithmen in Bezug auf ihre Laufzeitkomplexität hin analysieren.
  • Sie sind in der Lage, eigene Lösungsansätze für graphentheoretische Problemstellungen zu entwickeln, diese zu implementieren und zu evaluieren.
  • Sie können Beschleunigungstechniken selbstständig zur Verbesserung von Algorithmen einsetzen.
  • Sie können strukturelle Eigenschaften spezieller Graphenklassen (wie Planarität oder Dünnbesetztheit) gezielt im Algorithmenentwurf ausnutzen.
Module contents
  • Kürzeste-Wege-Probleme
  • Netzwerk-Flussprobleme (maximale Flüsse, Minimalkostenflüsse)
  • Matching-Probleme und Verallgemeinerungen
  • Algorithmen für Probleme auf planaren Graphen
  • spezielle Graphenklassen
Forms of instruction Lecture (3 SWS)
Course
Exercises (1 SWS)
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency jedes Sommersemester
Module capacity unlimited
Time of examination
Credit points 5 CP
Share on module final degree Course 1: %; Course 2: %; Course 3: %; Course 4: %.
Share of module grade on the course of study's final grade 1
Reference text
Basismodul für die Vertiefungsrichtung "Algorithmen und Theoretische Informatik" im Masterstudiengang Informatik ab Version 2013.
Module course label Course type Course title SWS Workload of compulsory attendance Workload of preparation / homework etc Workload of independent learning Workload (examination and preparation) Sum workload
Course 1 Lecture Vorlesung 3 0
Course 2 Course Selbststudium zur Vorlesung 0
Course 3 Exercises Übung 1 0
Course 4 Course Bearbeitung der Übungsaufgaben 0
Workload by module 150 150
Total module workload 150
Examination Exam prerequisites Type of examination
Course 1
Course 2
Course 3
Course 4
Final exam of module
Regelmäßige Teilnahme und aktive Mitarbeit in den Übungen (Darstellung der Problemlösung in den Übungen), erfolgreiche Bearbeitung der Übungsaufgaben, wobei 50 % der erreichbaren Punkte erzielt werden müssen
mündl. Prüfung oder Klausur
Exam repetition information
Prerequisites and conditions Prerequisites Frequency Compulsory attendance Share on module grade in percent
Course 1 Summer semester No %
Course 2 Summer semester No %
Course 3 Summer semester No %
Course 4 Summer semester No %