Vorlesung: Algorithmentheorie (GL-1) (WS 2007/2008)

Vorlesung über 3 SWS mit Übungen über 2 SWS

Pflichtveranstaltung des Moduls B-GL

Vorlesung

Prof. Dr. Ulrich Meyer
Donnerstag 7:45 s.t. - 10:00
Magnus-Hörsaal (R-M-S 11-15)

Übungsbetrieb

Dipl-Inf. Andrei Negoescu (E-Mail: negoescu@cs.uni-frankfurt.de)
Raum 311
Sprechzeiten: Immer, wenn im Büro anzutreffen und nach Vereinbarung.

Das Lösen von Übungsaufgaben ist für eine erfolgreiche Teilnahme an der Vorlesung unbedingt zu empfehlen. Die Aufgaben der Klausur werden sich an Übungsaufgaben orientieren. Der Übungsbetrieb ist im wöchentlichen Rhythmus organisiert.

An jedem Donnerstag wird ein Aufgabenzettel ausgegeben. Abgaben für diesen Zettel sind bis zum Vorlesungstermin der Folgewoche entweder vor der Vorlesung oder bis 7:45 in den Briefkasten neben Raum 312 abzugeben.

Die Ergebnisse der Nachklausur befinden sich im geschützten Bereich.

Termine Repetitorium

Komplexität (P, NP), Tahirovic, Di 04.03 10-14 Uhr, SR 11
Graphalgorithmen, Schmid, Do 06.03 10-14 Uhr, SR 11
Entwurfsmethoden, Jäger, Di 11.03, 10-14 Uhr, SR 11
Sortieren, Besser, Do 13.03, 10-14 Uhr, SR 11

Desweiteren finden Fragestunden an folgenden Terminen im Raum 309 statt:

Fr 14.03, 12-15 Uhr
Mo 17.03, 12-15 Uhr
Di 18.03, 14-17 Uhr

Inhalt

Die Vorlesung behandelt fundamentale Algorithmen und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen sowie die NP-Vollständigkeit. Algorithmen für Ordnungsprobleme wie Sortieren und Mischen wie auch Algorithmen für Graphprobleme wie die Berechnung kürzester Wege und minimaler Spannbäume werden beschrieben und analysiert. Algorithmentypen bzw. Entwurfsmethoden wie Greedy-Algorithmen, Teile-und-Beherrsche und dynamisches Programmieren werden eingeführt und angewandt. Das Konzept der NP-Vollständigkeit erlaubt die Untersuchung der algorithmischen Komplexität von Problemen. Die NP-Vollständigkeit des Erfüllbarkeitsproblems und weiterer Berechnungsprobleme wird gezeigt. Abschließend wird ein Ausblick auf die Behandlung komplexer algorithmischer Probleme unter Betonung der Approximationsalgorithmen gegeben. Dazu werden Branch & Bound und Backtracking Verfahren wie auch verschiedene Varianten der lokalen Suche vorgestellt für den Entwurf. Lernziele: Die Kenntniss fundamentaler Algorithmen sowie die Fähigkeit, den Prozess des Entwurfs und der Analyse von Algorithmen eigenständig durchführen zu können.

Literatur

J. Kleinberg und E. Tardos, Algorithm Design, Addison Wesley 2005, ISBN 0321372913
T. H. Cormen, C. E. Leiserson, R. L. Rivest und C. Stein, Introduction to Algorithms, Second Edition, McGraw Hill 2001, ISBN 0070131511

Scheinkriterien

Bachelor Informatik (B-GL): Eine 180-minütige Klausur zum Erwerb einer benoteten Studienleistung.

Die Klausur ist bestanden, wenn mindestens 50% aller erreichbaren Punkte erzielt wurden.
Zur Benotung werden neben dem Klausurergebnis Bonuspunkte aus den Übungen mit einem Maximalgewicht von 10% eingehen.

Klausurtermine

Hauptklausur: 12.02.08, 14:00-17:00
Nachklausur : 28.03.08, 14:00-17:00, Hörsaal V (römisch 5)

Ressourcen

Materialien für Studierende befinden sich hier.