[IEA2] - [2017/18 Winter] - [de] - [Effiziente Algorithmen 2]


Effiziente Algorithmen 2 [2017/18 Winter]
Code
IEA2
Name
Effiziente Algorithmen 2
LP
8 LP
Dauer
ein Semester
Angebotsturnus
jedes 4. Semester
Format
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. Mathematik,
M.Sc. Scientific Computing
Sprache
Lehrende
Prüfungsschema
Lernziele 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
Lerninhalte 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.
Teilnahme-
voraus-
setzungen
empfohlen sind: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1; Absolvierung des Moduls Effiziente Algorithmen 1 (IEA1) ist nützlich, aber nicht Voraussetzung
Vergabe der LP und Modulendnote Bestehen der Modulprüfung
Nützliche Literatur Korte, B., Vygen, J.: Kombinatorische Optimierung, Springer, 2007
Nemhauser, G.L., Wolsey, L.A.: Integer Combinatorial Optimization, Wiley, 1988