Effiziente Algorithmen

Grundstudium
SS 2007
Vorlesung:

Veranstaltung	Zeit	Raum	Person	Ort
Vorlesung	Di, 9-11	B 138	Prof. Martin Hofmann	Theresienstrasse 39
Übung	Mi, 14-16	B 041	Nicolas Rachinsky	Theresienstrasse 39
Übung	Mi, 16-18	B 041	Hermann Gruber	Theresienstrasse 39
Übung	Do, 16-18	B 041	Hermann Gruber	Theresienstrasse 39
Vorlesung	Fr, 11:00-12:30	B 139	Prof. Martin Hofmann	Theresienstrasse 39

Schein: ja
SWS: 4 Vorlesung + 2 Übung
Zwischenklausur: Dienstag, 5. Juni 2007, 09:15 im Hörsaal B138 in der Theresienstrasse 39.
Klausur: Dienstag 24. Juli 2007, 10:00 im Hoersaal 1.14 in der Oettingenstrasse 67
Zulassung zur Klausur: mindestens 40% der erreichbaren Hausaufgabenpunkte

Hier geht's zum Anmeldungsformular...

Aktuelles

Zur Amortisierten Analyse von Union-Find habe ich fuenf Folien geschrieben.
Zulassungsvoraussetzung für die Teilnahme an der Endklausur ist die erfolgreiche Lösung der Hausaufgaben (mind. 40% der Punkte)
Klausureinsicht der Zwischenklausur ist am Dienstag, den 19.Juni 2007, 13:00 Uhr in der Oettingenstraße 63, Raum Z1.09 und am Donnerstag, 21. Juni um 17:45 Uhr (nach der Uebung) in der Theresienstraße 39, Raum B041.
Notizblockfolien fuer Kapitel V .
Notizblockfolien fuer Kapitel IV .
Notizblockfolien fuer Kapitel III .
XFIG Bild zu Rotschwarzbaeumen.
Die Freitagsvorlesung beginnt ab sofort um 11:00 s.t. statt um 11:15.
Folien fuer Kapitel I und II befinden sich hier . Die Folien sind kein Skript sondern koennen als Notizblock zum Mitschreiben genutzt werden. Sie ersetzen weder das Lehrbuch, noch die Tafelanschrift und werden in der Vorlesung auch nicht gezeigt.
Siehe auch das Forum zur Vorlesung für aktuelle Diskussionen.

Inhalt

Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen ein, welche in fast allen Gebieten der Informatik und verwandten Disziplinen Anwendung finden. Wir lehnen uns eng an das Lehrbuch von Cormen et al. an, das in mehreren Präsenzexemplaren in der Bibliothek vorhanden ist.

Gliederung

Einführung
Sortier- und Suchverfahren
- HeapSort
- QuickSort
- Sortieren in Linearzeit
- Selektion
Datenstrukturen
- Hashtabellen
- Binäre Suchbäume
- Disjunkte Mengen
Graphalgorithmen
- Minimale Spannbäume
- Kürzeste Wege
- Flüsse in Netzwerken
Entwurfsprinzipien
- Dynamische Programmierung
- Greedy Algorithmen
- Amortisierungs-Analyse
Schnelle Fouriertransformation
Geometrische Algorithmen
- Repräsentation geometrischer Daten
- "sweep line"-Verfahren
- Konvexe Hülle
Mustersuche in Zeichenketten

Literatur

siehe bitte hier

Hermann Gruber

Last modified: Tue Jul 10 09:00:20 CEST 2007