Theoretische Informatik 3
Inhalt: |
Die Vorlesung behandelt ein Kerngebiet der Theoretischen Informatik: effiziente Algorithmen, und setzt damit die Inhalte der Vorlesung Theoretische Informatik I fort. Dass Kenntnisse der Prinzipien effizienter Algorithmen auch für die Praxis wertvoll sind, sollte einleuchtend sein. Im Einzelnen behandelt die Vorlesung kompliziertere Datenstrukturen. Besonderer Wert wird auf den Bereich der dynamischen Datenstrukturen gelegt. Das sind Datenstrukturen, die ihre Struktur dem Zugriffsverhalten dynamisch anpassen können. Des Weiteren werden wahrscheinlichkeitstheoretische Aspekte der Theorie effizienter Algorithmen untersucht. Hier geht es zum einen um den Nachweis, dass das Sortierverfahren Quicksort im Mittel optimal ist. Zum anderen wird die Datenspeicherung durch hashing analysiert. |
Literatur: |
|
Übungen: |