| Effiziente Algorithmen 1 [2019 SoSe] | ||
|---|---|---|
| Code IEA1 |
Name Effiziente Algorithmen 1 |
|
| 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 verstehen die grundlegenden Konzepte der Graphentheorie können Fragestellungen als kombinatorische Optimierungsprobleme modellieren können die Komplexität von Optimierungsproblemen analysieren kennen die Methoden zum Beweis der Korrektheit kombinatorischer Algorithmen und der Analyse ihrer Laufzeit kennen die grundlegenden algorithmischen Ansätze sind mit den Fragen der effizienten Implementierung vertraut haben Einblick in die vielfältigen Anwendungsgebiete der kombinatorischen Optimierung |
|
| Lerninhalte | Grundbegriffe der Graphentheorie Grundlegende Graphenalgorithmen Optimale Bäume und Branchings Kürzeste Wege Das Zuordnungsproblem Maximale Flüsse Minimale Schnitte in ungerichteten Graphen Flüsse mit minimalen Kosten Matchingprobleme |
|
| Teilnahme- voraus- setzungen |
empfohlen sind: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1 (MA4) | |
| 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 Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization, Wiley, 1997 |
|