311.250 (12W) Algorithmische Graphentheorie
Überblick
- Lehrende/r
- LV-Titel englisch Algorithmic Graph Theory
- LV-Art Vorlesung
- Semesterstunde/n 2.0
- ECTS-Anrechnungspunkte 3.0
- Anmeldungen 10
- Organisationseinheit
- Unterrichtssprache Deutsch
- LV-Beginn 01.10.2012
Zeit und Ort
Liste der Termine wird geladen...
LV-Beschreibung
Lehrmethodik inkl. Einsatz von eLearning-Tools
TafelvortragInhalt/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.Themen
- Graphentheorie: Grundbegriffe
- Aufspannende Bäume
- Kürzeste Wege in Graphen
- Orientierung ungerichteter Graphen
- Eulersche Graphen
- Matching-Theorie
- Komplexitätstheorie
- Approximationsalgorithmen
- (Matroide)
Erwartete Vorkenntnisse
keineSonstige Studienbehelfe
Vorlesungsskripten: A. Schrijver: A Course in Combinatorial Optimization, 2012. A. Wiegele: Algorithmische Graphentheorie, 2007. M. Grötschel: Kombinatorische Optimierung, 1998.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
Im Fall von online durchgeführten Prüfungen sind die Standards zu beachten, die die technischen Geräte der Studierenden erfüllen müssen, um an diesen Prüfungen teilnehmen zu können.
Prüfungsinhalt/e
Theoretische Grundlagen: Definitionen, Sätze, Beweise Praktische Umsetzung: Eigenständiges Lösen von relevanten AufgabestellungenBeurteilungskriterien/-maßstäbe
SchriftlichBeurteilungsschema
Note BenotungsschemaPosition im Curriculum
- 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)
- Bachelorstudium Technische Mathematik und Datenanalyse
(SKZ: 201, Version: 03W.3)
-
Fach: Operations Research
(Wahlfach)
-
Algorithmische Graphentheorie (
3.0h VK / 4.5 ECTS)
- 311.250 Algorithmische Graphentheorie (2.0h VO / 3.0 ECTS)
-
Algorithmische Graphentheorie (
3.0h VK / 4.5 ECTS)
-
Fach: Operations Research
(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)
-
Wintersemester 2016/17
- 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)