11405 - Algorithmische Graphentheorie Modulübersicht

Modulnummer: 11405
Modultitel:Algorithmische Graphentheorie
  Algorithmic Graph Theory
Einrichtung: Fakultät 1 - MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Verantwortlich:
  • Prof. Dr. rer. nat. habil. Köhler, Ekkehard
Lehr- und Prüfungssprache:Deutsch
Dauer:1 Semester
Angebotsturnus: sporadisch nach Ankündigung
Leistungspunkte: 8
Lernziele:Die Studierenden sollen
  • weitere Kenntnisse über Zusammenhänge und Methoden der Graphenthorie erwerben
  • algorithmische Problemstellungen der Graphentheorie verstehen und so einen wichtigen Beitrag zur weiteren Ausprägung algorithmischen Denkens leisten
  • geeignete Verfahren zur Lösung dieser Problemstellungen kennen und anwenden können
  • am Beispiel von Themen zur Graphentheorie Erfahrungen im selbstständigen wissenschaftlichen Arbeiten gewinnen.
Inhalte:Erkennungs-/ Optimierungsalgorithmen für verschiedene Graphenklassen, strukturelle Eigenschaften von Graphen zum Entwurf effizienter Algorithmen (z.B. Baumweite von Graphen), Intervallgraphen, chordale Graphen, planare Graphen
Empfohlene Voraussetzungen:Kenntnis des Stoffes der Module
  • 11103: Analysis I
  • 11104: Analysis II
  • 11214: Algorithmische Diskrete Mathematik I
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 2 SWS
  • Selbststudium / 150 Stunden
Unterrichtsmaterialien und Literaturhinweise:
  • M.C. Golumbic: Algorithmic Graph Theory and Perfect Graphs. (Academic Press, 1980)
  • A. Brandstädt, V.B. Le, J.P. Spinrad: Graph Classes: A Survey. (SIAM, 1999)
  • D.B. West: Introduction to Graph Theory - 2nd ed. (Prentice Hall, 2001)
  • J.P. Spinrad: Efficient Graph Representations. (ACM, 2003)
Modulprüfung:Modulabschlussprüfung (MAP)
Prüfungsleistung/en für Modulprüfung:Modulabschlussprüfung:
  • Klausur, 90 min. ODER
  • mündliche Prüfung, 30 min.
In der ersten Lehrveranstaltung wird bekanntgegeben, ob die Prüfungsleistung in schriftlicher oder mündlicher Form zu erbringen ist.
Bewertung der Modulprüfung:Prüfungsleistung - benotet
Teilnehmerbeschränkung:keine
Zuordnung zu Studiengängen:
  • Master (universitär) / Angewandte Mathematik / PO 2008
  • Master (universitär) / Angewandte Mathematik / PO 2019
  • Abschluss im Ausland / Informatik / keine PO
  • Bachelor (universitär) / Informatik / PO 2008 - 1. SÄ 2017
  • Master (universitär) / Informatik / PO 2008 - 2. SÄ 2017
  • Bachelor (universitär) / Mathematik / PO 2019
  • Bachelor (universitär) / Mathematik / PO 2023
  • Bachelor (universitär) - Duales Studium, praxisintegrierend / Mathematik - dual / PO 2023
  • Abschluss im Ausland / Physik / keine PO
  • Bachelor (universitär) / Wirtschaftsmathematik / PO 2007
  • Bachelor (universitär) / Wirtschaftsmathematik / PO 2023
  • Bachelor (universitär) - Duales Studium, praxisintegrierend / Wirtschaftsmathematik - dual / PO 2023
Bemerkungen:
  • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Analysis / Algebra / Kombinatorik"
  • Studiengang Mathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung“, im begrenzten Umfang
  • Studiengang Wirtschaftsmathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung“, im begrenzten Umfang
  • Studiengang Informatik B.Sc.: Wahlpflichtmodul in „Praktische Mathematik" oder im Anwendungsfach „Mathematik“
  • Studiengang Informatik M.Sc.: Wahlpflichtmodul in „Mathematik" oder im Anwendungsfach „Mathematik“
  • Studiengang Informations- und Medientechnik M.Sc.: Wahlpflichtmodul im Komplex „Methodische Grundlagen“
  • Studiengang Physik M.Sc.: Wahlpflichtmodul im Komplex „Nebenfach“
Veranstaltungen zum Modul:
  • Vorlesung: Algorithmische Graphentheorie
  • Übung zur Vorlesung
  • Zugehörige Prüfung
Veranstaltungen im aktuellen Semester:
  • keine Zuordnung vorhanden