Algorithmen und Datenstrukturen (WS 2014/2015)

Veranstalter	Petra Mutzel
Modul	Modulhandbuch INF-MSc-241 (Master Informatik / Angewandte Informatik)
Schwerpunktgebiet	4, 6, 7 (Diplom Informatik / Angewandte Informatik)
EWS	EWS-Anmeldung
Veranstaltungsnummer:	041235 (lsf Eintrag zur Vorlesung)
SWS	4

Ort und Zeit

Vorlesungzeiten: Dienstag 12:15-13:45 Uhr, SRG1 SR1.001 und Donnerstag 12:15-13:45 Uhr, OH12 E.003
Beginn der Vorlesungen: Di 07.10.2014
Ende der Vorlesungen: Do 29.01.2015 (zur Prüfungsvorbereitung, wegen 16. Semesterwoche)
Informationen zu den Übungen finden Sie hier: Übung zu Algorithmen und Datenstrukturen (WS 2014/2015)

Materialien

Alle Materialien sind im internen Bereich des EWS-Arbeitsraums ( EWS-Anmeldung) zu finden. Für den internen Bereich ist eine separate Anmeldung und Freischaltung notwendig.

Zusammenfassung

Diese Vorlesung mit der begleitenden Übung gibt einerseits die Grundlagen für die meisten weiterführenden Spezialvorlesungen im Bereich Algorithmische und formale Grundlagen, zum anderen behandelt sie weiterführende und komplexere Algorithmen und Datenstrukturen. Sie kann als Weiterführung von DAP2, mit fast leerer Überschneidung zu Effiziente Algorithmen gesehen werden. Im Einzelnen werden die folgenden Themen behandelt:

Komplexe Datenstrukturen und deren Analyse, wie z.B. Fibonacci-Heaps
Strings, z.B. Suffix Trees, Suffix Arrays, Pattern Matching
Lineare Programmierung: Modellierung, Dualität, Simplexalgorithmus
Ganzzahlige Lineare Programmierung: z.B. Gomory
Kombinatorische Optimierung, z.B. primal-duale Algorithmen, Branch-and-Cut
Approximationsalgorithmen, z.B. Set Cover
Graphenalgorithmen: z.B. Flussalgorithmen, Minimaler Schnitt, bipartites Matching
Geometrische Algorithmen: z.B. konvexe Hülle
Analysemethoden, wie z.B. amortisierte Analyse