312.256 (18S) Kombinatorische Optimierung

Sommersemester 2018

Anmeldefrist abgelaufen.

Erster Termin der LV
06.03.2018 08:00 - 09:30 , N.2.35
... keine weiteren Termine bekannt

Überblick

Lehrende/r
LV-Titel englisch
Combinatorial Optimization
LV-Art
Vorlesung
Semesterstunde/n
2.0
ECTS-Anrechungspunkte
4.0
Anmeldungen
14
Organisationseinheit
Unterrichtssprache
Deutsch
mögliche Sprache/n der Leistungserbringung
Deutsch
LV-Beginn
01.03.2018

LV-Beschreibung

Intendierte Lernergebnisse

Fortgeschrittene Kenntnisse im Gebiet Kombatorische Optimierung 

Lehrmethodik

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/Grade Benotungsschema

Position 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)

Gleichwertige Lehrveranstaltungen im Sinne der Prüfungsantrittszählung

Sommersemester 2016
  • 312.256 VO Kombinatorische Optimierung (2.0h / 4.0ECTS)
Sommersemester 2014
  • 312.256 VO Kombinatorische Optimierung (2.0h / 4.0ECTS)