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


Effiziente Algorithmen 1 [2018 Sommer]
Code
IEA1
Name
Effiziente Algorithmen 1
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. Mathematik
Lernziel 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
Inhalt 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
Voraussetzungen empfohlen sind: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1
Prüfungs
modalitäten
Erfolgreiche Teilnahme an den Übungen (mehr als 50% der Punkte müssen erreicht werden) und Bestehen einer schriftlichen Abschlussprüfung
Literatur Korte, B., Vygen, J.: Kombinatorische Optimierung, Springer, 2007
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization, Wiley, 1997