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

Grundlegende Algorithmen (WS 00/01)

Die Scheine für die Wiederholungsklausur und die Übungsscheine können ab Montag, 21.5., im Zimmer S1430 abgeholt werden.

Dozent: Prof. Dr. Ernst W. Mayr Dr. Michal Mnuk Bereich: 3 SWS Vorlesung im Bachelor-Studiengang Informatik Pflichtvorlesung 3 SWS Vorlesung im Aufbaustudium Informatik Pflichtvorlesung 3 SWS Vorlesung im Master-Studiengang Computational Science and Engineering Pflichtvorlesung Zeit und Ort: Mi 8:30 - 10:00, Hörsaal 0602 Do 12h c.t. - 13:00, Hörsaal 1100 Beginn: 18. Oktober Ende: 9. Februar Übung: 2 SWS Übung zur Vorlesung Mi 16h c.t. - 17:45, Hörsaal 1100 Beginn: 25. Oktober Übungsleitung: Thomas Bayer Übungsschein: Einen Schein erhält, wer mindestens 50% der Punkte zu den Hausaufgaben erreicht. Hörerkreis: Studierende im Aufbaustudium Informatik Voraussetzungen: Elementare Grundkenntnisse in Informatik Empfehlenswert für: Grundkenntnisse im Bereich Algorithmen Inhalt: Grundlagen Maschinenmodelle, Komplexitätsmaße Paradigma I: Divide and Conquer Sortieren Merge-Sort, Heap-Sort, Quick-Sort Paradigma II: Dynamisches Programmieren Suchen Hashing, Suchbäume (AVL-Bäume, (a,b)-Bäume) Paradigma III: Greedy Algorithmen Elementare Graphalgorithmen Traversieren von Graphen, Transitive Hülle, kürzeste Wege Algorithmen, minimale Spannbäume, Union-Find Strukturen Arithmetische Probleme modulare Arithmetik, Primzahltests, RSA Weiterführende bzw. verwandte Vorlesungen: Skript: Kein Skript. Folien zur Vorlesung (PostScript) Einführung: Euklidischer Algorithmus, Sortieren durch Einfügen Divide and Conquer: Sortieren durch Einfügen (rekursiv), Multiplikation von Polynomen (Algorithmus von Karatsuba) Binäre Bäume: Einführung Sortieren: Merge Sort, Heap Sort, QuickSort Dynamische Programmierung: Optimale Klammerung Hashing: Hashfunktionen, offenes Hashing AVL Bäume: einfache und doppelte Rotation $(a,b)$-Bäume: Beispiel (Einfügen in einem $(2,3)$-Baum) Greedy Methode: Beispiel Graphen: Depth first search (DFS) und Breadth first search (BFS) Kürzeste Wege in Graphen: Dijkstra Algorithmus Arithmetik: Potenzberechnung, der erweiterte euklidische Algorithmus RSA Verschlüsselung: RSA Algorithmus; Beispiele Einfache Primzahltests: mit Satz von Fermat; Beispiel Literatur: Volker Heun, Grundlegende Algorithmen. Vieweg, Oktober 2000. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms. The MIT Press u.a. , Cambridge, Massachusetts u.a. , 1990 , 1028 S., ISBN 0262031418. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Reading (MA), 1976. Donald E. Knuth, The art of computer programming, Vol. 1-3. Addison-Wesley Publiching Company, Reading MA, 1973. Kurt Melhorn, Data structures and algorithms, Vol. 1-2. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1984. Sprechstunde: siehe hier