Algorithmische Anwendungen

Literatur

• Thomas H. Cormen , Charles E. Leierson, Ronald L. Rivest u. Clifford Stein. Introduction to Algorithms. 2nd ed. The MIT Press 2001 (auch in deutsch erhältlich). Unbedingt anschaffen!
• zu Maven:
  • http://www.sonatype.com/book/index.html
  • Buch frei im Netz als pdf-Datei verfügbar: http://www.sonatype.com/book/maven-user-guide.pdf

Inhaltsübersicht (klausurrelevanter Stoff für die drei Ala-Klausuren in 2008)

1. Anwendungen binärer Suchbäume (Kap 1)
   1. Rot-Schwarz-Bäume (Kap 1.1) , Pseudocodes
   2. Treaps (Kap 1.2)
   3. Persistente dynamische Mengen (Kap 1.3)
   4. Erweitern von Datenstrukturen (Kap 1.4)
      1. Dynamische Ordnungsstatistik (Kap 1.4.1)
      2. Wie werden Datenstrukturfen erweitert? (Kap 1.4.2, 12.11.2007 )
      3. Intervallbäume (Kap 1.4.3)
   5. Quadtrees und k-d-Trees (Kap. 1.5) Schöne k-d-Baum-Animation in PowerPoint.
2. Dynamische Programmierung (Kap 2)
   1. Line Scheduling (Kap 2.1)
   2. Optimierung von Matrixkettenmultiplikationen (Kap 2.2)
   3. Theorie der dynamischen Programmierung (Kap 2.3)
3. Geometrische Algorithmen (nicht behandelt)
4. Greedy-Algorithmen (Kap 4 ) (Übung 4 !)
5. Single-Source-Shortest-Paths-Algorithmen (Kap 5, 15.11.2007)
6. Graph Drawing (nicht behandelt)
7. All-Pairs-Shortest-Paths und Matrix-Algorithmen (Kap 7) (Übung 7 !)
8. Flüsse in Netzwerken (Kap 8) (Übung 8)
9. Heuristische Algorithmen (Kap 9)
10. Lineare Programmierung (Kap 10) (empfehlenswert: Zingel)
11. Die Klassen P und NP, NP-vollständige Probleme, NP-hard-Probleme. Erfüllbarkeitstheorem und Satz von Cook. (keine Folien, sondern Tafel)