Professur Theoretische Informatik
Ehemalige Professur Theoretische Informatik

Theoretische Informatik III

Sommersemester 2007

Vorlesung: Theoretische Informatik III

SWS (V/Ü/P)

3/1/0

Inhalt

Die Vorlesung ist eine Fortsetzung der Theoretischen Informatik I. Es werden folgende Themen behandelt:

  • Komplexe Datenstrukturen und ihre Analyse (Fibonacci-Heaps, Splay-Bäume)
  • Analyse der mittleren Laufzeit von Algorithmen (Quicksort)
  • Einführung in randomisierte Algorithmen

Literatur

 Cormen, Leiserson, Rivest: "Introduction to Algorithms."
Kingston: "Algorithms and Data Structures."
Weiss: " Algorithms."
Ottmann, Widmayer: "Algorithmen und Datenstrukturen."
Schöning: "Algorithmen - kurz gefasst" und "Algorithmen"
Kozen: "The design and analysis of algorithms"
Aho; Hopcroft; Ullman: "Data structures and algorithms"
Weiss: "Algorithms, data structures, and problem solving with C++"

Links

 Binomiale Heaps
Fibonacci-Heaps
Union-Find-Datenstrukturen
Listen
Vorlesungsskript vom SS 2001 (unkorrigiert)
Vorlesungsskript vom SS 2007 (unvollständig, aber korrigiert)
Übungsaufgaben