[IEA2] - [de] - [Effiziente Algorithmen 2]


Effiziente Algorithmen 2 [2019 Sommer]
Code
IEA2
Name
Effiziente Algorithmen 2
Leistungspunkte
8 LP
Dauer
ein Semester
Turnus
jedes 4. Semester
Lehrform
Vorlesung 4 SWS, Übungen 2 SWS
Arbeitsaufwand
240 h; davon
90 h Präsenzstudium
15 h Prüfungsvorbereitung
135 h Selbststudium und Aufgabenbearbeitung (evtl. in Gruppen)
Verwendbarkeit
B.Sc. Angewandte Informatik,
Lehramt Informatik,
M.Sc. Angewandte Informatik,
M.Sc. Scientific Computing,
M.Sc. Mathematik
Lernziel Die Studierenden
können polynomiale und NP-schwere Optimierungsprobleme klassifizeren
kennen die gesamte Bandbreite von Lösungsansätzen für schwierige Probleme
können geeignete Modellierungen für Anwendungsprobleme selbst erstellen
sind in der Lage, geeignete Lösungsverfahren auszuwählen
können selbst Lösungsverfahren konzipieren und implementieren
Inhalt NP-schwere Optimirungsprobleme
approximative Algorithmen und Heuristiken (Bin-Packing, Scheduling, Knapsack, Traveling Salesman)
Relaxierungen (lineare, kombinatorische, semidefinite, Lagrange-Relaxierungen)
Verfahren zur Bestimmung optimaler Lösungen (dynamische Optimierung, Branch-and-Bound, Branch-and-Cut)
lineare 0/1- Optimierung (Modellierung, Schnittebenen)
polyedrische Kombinatorik,
Spaltengenerierung und Dekomposition
Fallstudien (Traveling-Salesman_Problem, Max-Cut-Problem.)
Es wird somit das gesamte Spektrum von Lösungsverfahren für schwierige kombinatorische Probleme vermittelt.
Voraussetzungen empfohlen sind: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1 (MA4); Absolvierung des Moduls Effiziente Algorithmen 1 (IEA1) ist nützlich, aber nicht Voraussetzung
Prüfungs
modalitäten
eine schriftliche Abschlussprüfung
Literatur Korte, B., Vygen, J.: Kombinatorische Optimierung, Springer, 2007
Nemhauser, G.L., Wolsey, L.A.: Integer Combinatorial Optimization, Wiley, 1988