| Effiziente Algorithmen 2 [2019 SoSe] | ||
|---|---|---|
| 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. Scientific Computing, M.Sc. Mathematik |
| 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 (MA4); Absolvierung des Moduls Effiziente Algorithmen 1 (IEA1) ist nützlich, aber nicht Voraussetzung | |
| Vergabe der LP und Modulendnote | Erfolgreiche Teilnahme an den Gruppenübungen und 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 |
|