 |
Dozent:
Prof. Dr. Ernst W. Mayr
Dr. Peter Ullrich |
|
Bereich:
3+2 SWS Vorlesung im Bachelorstudium Informatik (Pflichtvorlesung)
3+2 SWS Vorlesung im Aufbaustudium Informatik (Pflichtvorlesung)
3 SWS Vorlesung im Master-Studiengang Computational
Science and Engineering (Pflichtvorlesung) |
|
Zeit und Ort:
Mo 12:00 s.t. - 14:30, Hörsaal N1080 |
|
Übung:
2 SWS Übung zur Vorlesung
Zeit und Raum werden noch bekannt gegeben.
Übungsleitung: Thomas Bayer
Übungsschein: Einen Schein erhält, wer eine Gesamtnote
<= 4,0 erreicht. Die Gesamtnote errechnet sich
aus beiden Klausuren (1. Klausur: 40%, 2. Klausur: 60%) -- die Hausaufgaben
tragen nicht zur Gesamtnote bei. |
|
Klausurtermine |
|
Hörerkreis:
Studierende im Bachelorstudium Informatik
Studierende im Aufbaustudium Informatik
Studierende im Master-Studiengang Computational
Science and Engineering |
|
Voraussetzungen:
Elementare Grundkenntnisse in
Informatik |
|
Empfehlenswert für:
Grundkenntnisse im Bereich
Algorithmen |
|
Aktueller Stand der Vorlesung:
15.10.01 Einführung
(Berechnungsbeispiel), Vollständige Induktion (Peano-Axiome),
Fibonacci-Zahlen
(rekursiv)
22.10.01 Fibonacci-Zahlen
(iterativ), Fibonacci- Zahlen (iteriertes Quadrieren), schneller
Potenzierungsalgorithmus,
Landau-Symbole
29.10.01 Registermaschine
Folien
(ps) (pdf),Komplexitätsmaße,
Analysebeispiel,
Einfache Sortieralgorithmen, SelectionSort
05.11.01 InsertionSort,
MergeSort, (binäre) Bäume
12.11.01 Binäre
Bäume, Heaps, Heapsort
19.11.01 Heapsort-Varianten,
Quicksort, untere Schranke, Wörterbuch, Binäre Suchbäume
26.11.01 Binäre
Suchbäume, AVL-Bäume
03.12.01 (a,b)-Bäume,
Hashing
10.12.01 Hashing Folie
(ps) (pdf), Fragen zur
1. Klausur
17.12.01 Grundlagen der
Graphentheorie
Weihnachtsferien
07.01.02 Darstellung
von Graphen, Tiefen- und Breitensuche DFS/BFS, Anwendungen von DFS/BFS
(Zusammenhang, Spannbäume),
Minimale Spannbäume
(MST)
14.01.02 Matroide,
Greedy-Algorithmus
für Matroide, Zusammenhang mit MST, Kruskals Algorithmus, Priority
Queues (nur angesprochen),
Prims Algorithmus, kürzeste
Wege in Graphen
21.01.02 Kürzeste
Wege in Graphen, Dijkstras Algorithmus, Datenkompression,
Huffman-Kodierung
28.01.02 Huffman-Kodierung
(Korrektheit), Dynamisches Programmieren, optimale Klammerung von
Matrizen
04.02.02 Kryptographie,
Diffie-Hellman, RSA, elliptische Kurven, Fragen zur 2.Klausur |
|
Weiterführende bzw. verwandte Vorlesungen:
|
|
Skript:
Kein Skript. |
|
Literatur:
wird noch bekannt gegeben. |
|
Sprechstunde:
siehe hier |
|
