[IEA1] - [de] - [Effiziente Algorithmen 1]


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