311.250 (16W) Algorithmische Graphentheorie
Überblick
- Lehrende/r
- LV-Titel englisch Algorithmic Graph Theory
- LV-Art Vorlesung
- Semesterstunde/n 2.0
- ECTS-Anrechnungspunkte 3.0
- Anmeldungen 13
- Organisationseinheit
- Unterrichtssprache es wurde keine Unterrichtssprache angegeben
- LV-Beginn 01.10.2016
- eLearning zum Moodle-Kurs
- Seniorstudium Liberale Ja
Zeit und Ort
LV-Beschreibung
Intendierte Lernergebnisse
- Graphentheorie: Grundbegriffe
- Aufspannende Bäume
- Kürzeste Wege in Graphen
- Flussprobleme
- Eulersche Graphen
- Matching-Theorie
- Komplexitätstheorie
- Approximationsalgorithmen
- (Matroide)
Lehrmethodik inkl. Einsatz von eLearning-Tools
Tafelvortrag
Inhalt/e
Der erste Teil der Vorlesung (bis "Eulersche Graphen") befasst sich mit Algorithmen auf Graphen. Im zweiten Teil (Matching-Theorie) werden "einfache" Probleme der kombinatorischen Optimierung besprochen. Im dritte Teil werden die Komplexität von Problemen (Klassen P und NP) und Approximationsalgorithmen für NP-schwere Optimierungsprobleme behandelt.
Literatur
D. Jungnickel: Graphs, Networks and Algorithms, Springer, 2008. B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms, Springer. 2012. (deutsche oder englische Version) A. Schrijver: Combinatorial Optimization, Springer, 2003. A. Gibbons: Algorithmic Graph Theory, Cambridge University Press, 1985.
Prüfungsinformationen
Prüfungsmethode/n
Schriftliche Prüfung
Prüfungsinhalt/e
Theoretische Grundlagen: Definitionen, Sätze, Beweise Praktische Umsetzung: Eigenständiges Lösen von relevanten Aufgabestellungen
Beurteilungsschema
Note BenotungsschemaPosition im Curriculum
- Bachelorstudium Angewandte Informatik
(SKZ: 511, Version: 12W.1)
-
Fach: Mathematik und Statistik
(Wahlfach)
-
Wahl einer Vorlesung aus dem Vertiefungsfach Diskrete Mathematik des Bachelorstudiums Technische Mathematik (
2.0h VO / 3.0 ECTS)
- 311.250 Algorithmische Graphentheorie (2.0h VO / 3.0 ECTS)
-
Wahl einer Vorlesung aus dem Vertiefungsfach Diskrete Mathematik des Bachelorstudiums Technische Mathematik (
2.0h VO / 3.0 ECTS)
-
Fach: Mathematik und Statistik
(Wahlfach)
- Bachelorstudium Technische Mathematik
(SKZ: 201, Version: 12W.2)
-
Fach: Diskrete Mathematik
(Wahlfach)
-
Algorithmische Graphentheorie (
2.0h VO / 3.0 ECTS)
- 311.250 Algorithmische Graphentheorie (2.0h VO / 3.0 ECTS)
-
Algorithmische Graphentheorie (
2.0h VO / 3.0 ECTS)
-
Fach: Diskrete Mathematik
(Wahlfach)
Gleichwertige Lehrveranstaltungen im Sinne der Prüfungsantrittszählung
-
Wintersemester 2020/21
- 311.250 VO Algorithmische Graphentheorie (2.0h / 3.0ECTS)
-
Wintersemester 2018/19
- 311.250 VO Algorithmische Graphentheorie (2.0h / 3.0ECTS)
-
Sommersemester 2015
- 311.250 VO Algorithmische Graphentheorie (2.0h / 3.0ECTS)
-
Wintersemester 2013/14
- 311.250 VO Algorithmische Graphentheorie (2.0h / 3.0ECTS)
-
Wintersemester 2012/13
- 311.250 VO Algorithmische Graphentheorie (2.0h / 3.0ECTS)