|
Diskrete Optimierung I (DiskOpt I)5 ECTS (englische Bezeichnung: Discrete optimization I)
(Prüfungsordnungsmodul: Discrete optimization I)
Modulverantwortliche/r: Alexander Martin Lehrende:
Lars Schewe, Frauke Liers, Andreas Bärmann
Startsemester: |
WS 2017/2018 | Dauer: |
1 Semester | Turnus: |
jährlich (WS) |
Präsenzzeit: |
45 Std. | Eigenstudium: |
105 Std. | Sprache: |
Deutsch |
Lehrveranstaltungen:
-
-
Diskrete Optimierung 1
(Vorlesung, 2 SWS, Andreas Bärmann, Do, 14:00 - 16:00, H12)
-
Übung zu Diskrete Optimierung 1
(Übung, 1 SWS, Andreas Bärmann, jede 2. Woche Mi, 14:00 - 16:00, Übung 5 / 01.254-128)
Empfohlene Voraussetzungen:
Lineare Algebra, Kombinatorische Optimierung
Inhalt:
Die Vorlesung behandelt theoretische und praktische Grundlagen zur
Lösung schwieriger gemischt-ganzzahliger linearer Optimierungsprobleme
(MIPs). Zunächst werden Kerndefinitionen der NP-Vollständigkeit behandelt und einige der bekannten NP-vollständigen Probleme vorgestellt. Im Bereich der Polyedertheorie werden die Grundlagen der Seitenstruktur konvexer Polyeder behandelt. Darauf aufbauend werden Schnittebenenverfahren sowie Branch-and-Cut Verfahren zur Lösung von MIPs gelehrt. Abschließend studieren wir einige klassische Probleme der Diskreten Optimierung wie das Rucksack-Problem, das Traveling-Salesman-Problem oder das Set-Packing-Problem.
Lernziele und Kompetenzen:
Die Studierenden
verfügen über grundlegende theoretische Erkenntnisse zur Lösungemischt-ganzzahliger linearer Optimierungsprobleme (MIPs),
können MIPs mittels verfügbarer Standard Software lösen.
Literatur:
- Vorlesungsskript zu diesem Modul
Conforti, Cornuéjols, Zambelli: Integer Programming, Springer 2014
B. Grünbaum, Convex Polytopes, Springer, 2003
B. Korte, J. Vygen: Combinatorial Optimization, Springer 2005
G. L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization, Wiley 1994
A. Schrijver: Theory of Linear and Integer Programming, Wiley 1986
L.A. Wolsey: Integer Programming, Wiley 1998
G. Ziegler, Lectures on Polytopes, Springer, 1995
Bemerkung:
- Wahlmodul: Master Mathematik, Technomathematik und Wirtschaftsmathematik
Kern-/Forschungsmodul Master Mathematik Studienrichtung „Modellierung, Simulation, Optimierung“, Master Technomathematik Studienrichtung „Optimierung“, Master Wirtschaftsmathematik Studienrichtung „Optimierung und Prozessmanagement“
Organisatorisches:
Neben der Vorlesung werden Übungen angeboten, in denen die
Studierenden von einem Übungsgruppenleiter betreut werden. Anhand von
Präsenz- und Hausaufgaben werden wesentliche Lerninhalte geübt. Bis WS 14/15 hieß das Modul "Theoretische Grundlagen der Diskreten Optimierung"!
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Informatik (Master of Science)
(Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Nebenfach | Nebenfach Mathematik | Discrete optimization I)
Dieses Modul ist daneben auch in den Studienfächern "Computational and Applied Mathematics (Master of Science)", "Mathematik (Master of Science)", "Technomathematik (Master of Science)", "Wirtschaftsmathematik (Master of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
Discrete optimization I (Prüfungsnummer: 59171)
(englischer Titel: Discrete optimization I)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 15, benotet, 5 ECTS
- Anteil an der Berechnung der Modulnote: 100.0 %
- Erstablegung: WS 2017/2018, 1. Wdh.: WS 2017/2018
1. Prüfer: | Andreas Bärmann |
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|