|
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 - 11101 Lineare Algebra und analytische Geometrie I
- 12868 Algorithmische Diskrete Mathematik
oder der Module - 11112 Mathematik IT-1 (Diskrete Mathematik)
- 11113 Mathematik IT-2 (Lineare Algebra)
|
| Zwingende Voraussetzungen: | Keine Teilnahme an Modul - 14274 Algorithmic Graph Theory
|
| 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: | Voraussetzung + Modulabschlussprüfung (MAP) |
| Prüfungsleistung/en für Modulprüfung: | Voraussetzung für die Modulabschlussprüfung: - erfolgreiche Bearbeitung von Hausaufgaben (zweiwöchentlich) oder erfolgreiche Bearbeitung von Hörsaaltests (ca. 4 je 15-30 Minuten)
Modulabschlussprüfung: - Klausur, 90 min. ODER
- mündliche Prüfung, 30 min.
In der ersten Lehrveranstaltung wird bekanntgegeben, wie die Voraussetzung organisiert wird und 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 2019
- 1. SÄ 2021
-
Abschluss im Ausland /
Informatik /
keine PO
-
Bachelor (universitär) /
Informatik /
PO 2008
- 2. SÄ 2024
-
Master (universitär) /
Informatik /
PO 2008
- 3. SÄ 2024
-
Bachelor (universitär) /
Künstliche Intelligenz /
PO 2022
-
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 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 Künstliche Intellgenz B.Sc.: Wahlpflichtmodul im Komplex „Wissensakquise, -repräsentation und -verarbeitung”
- Studiengang Informatik B.Sc.: Wahlpflichtmodul in „Praktische Mathematik" oder im Anwendungsfach „Mathematik”
- Studiengang Informatik M.Sc.: Wahlpflichtmodul in „Mathematik" oder im Anwendungsfach „Mathematik”
|
| Veranstaltungen zum Modul: | - Vorlesung: Algorithmische Graphentheorie
- Übung zur Vorlesung
- Zugehörige Prüfung
|
| Veranstaltungen im aktuellen Semester: | |
