LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München
english

Effiziente Algorithmen und Datenstrukturen (WS 01/02)


* Dozent:
Prof. Dr. Angelika Steger

* Bereich:
4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Algorithmen

* Zeit und Ort:
Di 10h c.t. - 11:45, Hörsaal N1179 Achtung: am 6.11 noch in N1070
Do 10h c.t. - 11:45, Hörsaal N1189
Beginn: 16. Oktober

* Übung:
2 SWS Übung zur Vorlesung
Di 13:30 - 15:00, Hörsaal N1080
Übungsleitung: Ingo Rohloff
Übungsschein: Einen Schein erhält, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der Semestralklausur teilnimmt.

* Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik

* Voraussetzungen:
Stoff des Informatik Grundstudiums

* Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen

* Inhalt:
In der Vorlesung werden voraussichtlich folgende Themen behandelt:
  1. Grundlagen
    1. Ein Beispiel
    2. Analyse von Algorithmen
    3. Amortisierte Analyse
  2. Höhere Datenstrukturen
    1. Wiederholung: (a,b)-Bäume, AVL-Bäume
    2. Splay Trees
    3. Fibonacci Heaps
    4. k-level Buckets
    5. Radix Heaps
  3. Sortieren und Selektieren
    1. Analyse von QuickSort
    2. BucketSort
    3. Selektionsalgorithmus nach BFPRT
    4. Untere Schranke für Median
  4. Graphalgorithmen I
    1. Das kürzeste Wege Problem
    2. Transitive Hülle
  5. Ausgewählte Verfahren
    1. Matrizenmultiplikation nach Strassen
    2. String Matching
    3. Suffix Trees
    4. FFT
  6. Approximationsalgorithmen
    1. Knapsack
    2. Binpacking
    3. TSP
    4. MaxSat

* Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen II
Randomisierte Algorithmen

* Skript:
Skript von 1996/97. Siehe hier.

* Literatur:
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading MA, 1976
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
Introduction to Algorithms
The MIT Press, 2. Auflage, 2001
Volker Heun:
Grundlegende Algorithmen
Vieweg Verlag, 2000
(Hörerscheine für dieses Buch können bei Frau Sterl, Zi. S1430, abgeholt werden.)
Donald E. Knuth:
The art of computer programming Vol. 3 : Sorting and searching
Addison-Wesley Publishing Company, Reading MA, 1973
Thomas Ottmann, Peter Widmayer:
Algorithmen und Datenstrukturen
Spektrum, Akad. Verlag, 3. Auflage, 1996
Christos H. Papadimitriou, Kenneth Steiglitz:
Combinatorial optimization : Algorithms and complexity
Dover Publications, 1998
Uwe Schöning:
Algorithmik
Spektrum, Akad. Verlag, 2001

* Sprechstunde:
siehe hier


steger@informatik.tu-muenchen.de