Ehemalige Professur Theoretische Informatik und Informationssicherheit
Lehre

Theoretische Informatik 3

(Vorlesung, SS 2005, 3/1/0 SWS)

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:
  • Skript (vorläufige Version vom 14.7.02, 189 KB)
  • Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge 1994.
  • Ottmann, Th.; Widmayer, P.: Algorithmen und Datenstrukturen. Spektrum, Heidelberg 2002.
  • Sedgewick, R.: Algorithms. Addison-Wesley 1983.
  • Kozen, D.C.: The design and analysis of algorithms. Springer 1991.
  • Christofides, N.: Graph theory: an algorithmic approach. Academic Press 1975.
  • Kingston, J.H.: Algorithms and Data Structures. Design, Correctness, Analysis. Addison-Wesley, Harlow 1998.
  • Weiss, M.A.: Algorithms, Data Structures, and Problem Solving with C++. Addison-Wesley, Reading 1996.
Übungen:

TUCaktuell