312.256 (18S) Kombinatorische Optimierung
Überblick
- Lehrende/r
- LV-Titel englisch Combinatorial Optimization
- LV-Art Vorlesung
- Semesterstunde/n 2.0
- ECTS-Anrechnungspunkte 4.0
- Anmeldungen 14
- Organisationseinheit
- Unterrichtssprache Deutsch
- mögliche Sprache/n der Leistungserbringung Deutsch
- LV-Beginn 06.03.2018
Zeit und Ort
LV-Beschreibung
Intendierte Lernergebnisse
Fortgeschrittene Kenntnisse im Gebiet Kombatorische Optimierung
Lehrmethodik inkl. Einsatz von eLearning-Tools
Vortrag im Hörsaal, eigenständiges Erarbeiten von Aufgaben
Inhalt/e
- Optimierungsaufgaben auf bipartiten Graphen (Matchingtheorie, Zuordnungsproblem, Gale-Shapley Matching, Stundenplanproblem)
- Linerare Algebra und Graphen (Kreise und Schnitte in Graphen, Matrix-Baum Satz, elektrische Netzwerke, Eigenwertschranken)
- Knotenfärbung auf Intervallgraphen
- Approximationsalgorithmen (Baumheuristiken für das Rundreiseproblem, Scheduling, Mengenüberdeckungsprobleme)
- Approximation mittels konvexer Optimierung (Goemans-Williamson Rundungsheuristik für Max-Cut, Graphfärben)
Erwartete Vorkenntnisse
Lineare Algebra (Basis, Dimension, lineare Gleichungen, Eigenwerte), Diskrete Mathematik
Literatur
B. Korte und J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer 2000.
D. Jungnickel, Graphs, Networks and Algorithms, Springer, 1999
Prüfungsinformationen
Prüfungsmethode/n
Am Ende der LV findet eine schriftliche Klausur statt.
Prüfungsinhalt/e
Inhalt der LV
Beurteilungskriterien/-maßstäbe
Erfolgreich abgeschlossene Abschlussprüfuing
Beurteilungsschema
Note BenotungsschemaPosition im Curriculum
- Masterstudium Technische Mathematik
(SKZ: 401, Version: 13W.1)
-
Fach: Diskrete Mathematik
(Wahlfach)
-
Kombinatorische Optimierung (
2.0h VO / 4.0 ECTS)
- 312.256 Kombinatorische Optimierung (2.0h VO / 4.0 ECTS)
-
Kombinatorische Optimierung (
2.0h VO / 4.0 ECTS)
-
Fach: Diskrete Mathematik
(Wahlfach)