Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Hauptstudium Vorlesung: Entwurf und Analyse von Algorithmen (SS00)
- Vorlesung:
-
Dr. Jan Johannsen:
Hauptstudium Vorlesung: Entwurf und Analyse von
Algorithmen, 3-stündig
- Zeit und Ort: Mo 14 - 16 Uhr, Raum 13 ;
Do 9-10 Uhr, Raum 15
- Übung:
-
Dr. Jan Johannsen
- Zeit und Ort der Übung: Do 10 - 11 Uhr, Raum 15
- Vorkenntnisse:
- Grundkenntnisse in Informatik
- Hörerkreis: :
- Studierende im Hauptstudium der Informatik
- Studierende mit Nebenfach Informatik
- Schein:
- bei ausreichender Bearbeitung von Hausaufgaben
und mündlicher Prüfung.
- Schein gilt für Diplomprüfung in
Haupt- und Nebenfach Informatik
zurück zum
Inhaltsverzeichnis dieser Seite
Anhand von Beispielen sollen Prinzipien des Algorithmen-Entwurfs und
Methoden zur Analyse des Resourcenbedarfs (Laufzeit, Speicherplatz)
von Algorithmen dargelegt werden. Neben dem worst-case- soll dabei
vor allem auch das average-case-Verhalten betrachtet werden.
Ein Schwerpunkt der Vorlesung soll auf den probabilistischen
Algorithmen liegen.
- Einführung
- worst-case- vs. average-case-Analyse
- Asymptotik
- Ein einfaches Beispiel
- Zum Aufwärmen: Sortieren
- Sortieren durch Einfügen: InsertionSort
- Untere Schranke für vergleichsbasiertes Sortieren
- QuickSort
- Divide-and-Conquer Verfahren
- MergeSort
- Analyse von Divide-and-Conquer Algorithmen
- Multiplikation von Polynomen und Matrizen
- Schnelle Fourier-Transformation
- Greedy Algorithmen
- Huffman-Codes, Datenkompression
- Matroide
- Kruskal's Algorithmus für Minimale Spannbäume
- Probabilistische Algorithmen
- Einführung
- Las Vegas vs. Monte Carlo
- Die Markov- und Tschebyscheff-Ungleichungen
- Ein Selektionsalgorithmus
- Wahrscheinlichkeitsverstärkung
- Fingerprinting
- Verifikation von Polynomgleichungen
- Matchings in Graphen
- Pattern Matching
- Die "Probabilistische Methode"
- Markov-Ketten und Irrfahrten
- 2 SAT
- Irrfahrten auf Graphen
- Erreichbarkeit
- Wahrscheinlichkeitsverstärkung
- T. H. Cormen, C. E Leiserson and R. L. Rivest,
Introduction to Algorithms, MIT Press (1990)
Das Standardlehrbuch für Algorithmen am MIT.
- R. Motwani and P. Raghavan, Randomized Algorithms,
Cambridge University Press (1995)
Sehr gute und verständliche Einführung.
- D.E.Knuth, The Art of Computer Programming,
Addison-Wesley, Vol. 1-2 (31997), Vol. 3
(21998)
Der Klassiker schlechthin, soeben neu
aufgelegt. Sollte jeder Informatiker kennen
und schätzen.
- U. Schöning, Algorithmen - kurz gefasst,
Spektrum Akademischer Verlag (1997)
zurück zum
Inhaltsverzeichnis dieser Seite
zurück zum
Inhaltsverzeichnis dieser Seite