MLU
INF.02604.06 - Effiziente Graphenalgorithmen (Vollständige Modulbeschreibung)
Originalfassung Englisch
INF.02604.06 5 CP
Modulbezeichnung Effiziente Graphenalgorithmen
Modulcode INF.02604.06
Semester der erstmaligen Durchführung
Fachbereich/Institut Institut für Informatik
Verwendet in Studiengängen / Semestern
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Akkreditierungsfassung gültig ab SoSe 2023 > Algorithmen und Theoretische Informatik (Anteil gem. § 5 Abs. 4-6, Anlage 2)
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Akkreditierungsfassung (WS 2009/10 - SS 2016) > Datenstrukturen und effiziente Algorithmen
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Akkreditierungsfassung (WS 2016/17 - WS 2022/23) > Algorithmen und Theoretische Informatik
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung gültig ab SoSe 2023 > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Primärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2013/14 - SS 2016) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2016/17 - WS 2022/23) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Akkreditierungsfassung gültig ab WS 2022/23 > Anwendungsfach Informatik (20 LP sind zu erbringen)
  • Wirtschaftsinformatik (Business Information Systems) (MA120 LP) (Master) > Wirtschaftsinformatik WirtschaftsinformatMA120, Akkreditierungsfassung gültig ab WS 2020/21 > 1.3 Informatik
  • Wirtschaftsinformatik (Business Information Systems) (MA120 LP) (Master) > Wirtschaftsinformatik WirtschaftsinformatMA120, Akkreditierungsfassung (SS 2016 - SS 2020) > II. Wahlbereich Informatik
  • Wirtschaftsmathematik (MA120 LP) (Master) > Wirtschaftsmathematik WirtschaftsmatheMA120, Akkreditierungsfassung (WS 2013/14 - SoSe 2023) > Informatik
Modulverantwortliche/r
Weitere verantwortliche Personen
Prof. Dr. Matthias Müller-Hannemann
Teilnahmevoraussetzungen
Kompetenzziele
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.
Modulinhalte
  • Kürzeste-Wege-Probleme
  • Netzwerk-Flussprobleme (maximale Flüsse, Minimalkostenflüsse)
  • Matching-Probleme und Verallgemeinerungen
  • Algorithmen für Probleme auf planaren Graphen
  • spezielle Graphenklassen
Lehrveranstaltungsformen Vorlesung (3 SWS)
Kursus
Übung (1 SWS)
Kursus
Unterrichtsprachen Deutsch, Englisch
Dauer in Semestern 1 Semester Semester
Angebotsrhythmus Modul jedes Sommersemester
Aufnahmekapazität Modul unbegrenzt
Prüfungsebene
Credit-Points 5 CP
Modulabschlussnote LV 1: %; LV 2: %; LV 3: %; LV 4: %.
Faktor der Modulnote für die Endnote des Studiengangs 1
Hinweise
Basismodul für die Vertiefungsrichtung "Algorithmen und Theoretische Informatik" im Masterstudiengang Informatik ab Version 2013.
Modulveran­staltung Lehrveranstaltungs­form Veranstaltungs­titel SWS Workload Präsenz Workload Vor- / Nach­bereitung Workload selbstge­staltete Arbeit Workload Prüfung incl. Vorbereitung Workload Summe
LV 1 Vorlesung Vorlesung 3 0
LV 2 Kursus Selbststudium zur Vorlesung 0
LV 3 Übung Übung 1 0
LV 4 Kursus Bearbeitung der Übungsaufgaben 0
Workload modulbezogen 150 150
Workload Modul insgesamt 150
Prüfung Prüfungsvorleistung Prüfungsform
LV 1
LV 2
LV 3
LV 4
Gesamtmodul
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
Wiederholungsprüfung
Regularien Teilnahme­voraussetzungen Angebots­rhythmus Anwesenheits­pflicht Gewicht an Modulnote in %
LV 1 Sommersemester Nein %
LV 2 Sommersemester Nein %
LV 3 Sommersemester Nein %
LV 4 Sommersemester Nein %