Vorlesung der Arbeitsgruppe Theoretische Informatik im Wintersemester 2000/2001

`` Entwurf und Analyse von Algorithmen ''

Günter Rote, Astrid Kaffanke Christian Knauer

• 1. Vorlesung am 19. Oktober.
  • Divide & Conquer, Schnelle Matrixmultiplikation
  • Dynamisches Programmieren, Optimale Klammerung bei der Matrixmultiplikation
• 2. Vorlesung am 23. Oktober.
  • Rucksackproblem
    • Systematisches Durchsuchen von Lösungsbäumen, Branch & Bound
    • Dynamische Optimierung
  • Asymptotische Analyse
• 3. Vorlesung am 26. Oktober.
  • Kürzeste Wege in Graphen mittels dynamischem Programmieren
• 4. Vorlesung am 30. Oktober.
  • Kürzeste Wege in Graphen, Kantenstraffung und Vorgängerbäume
• 5. Vorlesung am 2. November.
  • Algorithmus von Moore
  • Kürzeste Wege und Matrixmultiplikation
• 6. Vorlesung am 6. November.
  • Algebraisches Wegeproblem (Beispiel formale Sprachen)
  • Floyd-Warshall Algorithmus
• 7. Vorlesung am 13. November.
  • Gauß-Jordan Elimination und Floyd-Warshall Algorithmus
  • Idempotente Halbringe
• 8. Vorlesung am 16. November.
  • Algorithmus von Dijkstra
  • Binomialhalden
• 9. Vorlesung am 20. November.
  • Struktur von Binomialhalden
  • Amortisierte Analyse der Einfügeoperation auf Binomialhalden
  • Binomialhalden mit faulem Entfernen
• 10. Vorlesung am 23. November.
  • Fibonaccihalden
  • Amortisierte Analyse kaskadierender Schnitte
  • Auswahlproblem
  • Deterministisch optimales Auswählen
• 11. Vorlesung am 30. November.
  • Analyse deterministisch optimales Auswählen
  • Randomisiertes Auswählen
  • Kürzeste aufspannende Bäume
  • Genereische MST Algorithmus
• 12. Vorlesung am 4. Dezember.
  • Algorithmus von Kruskal
  • Das Union-Find Problem
  • Union-Find Algorithmen
• 1. Klausur am 7. Dezember.
• 13. Vorlesung am 11. Dezember.
  • Die Ackermannfunktion und ihre Inverse
  • Analyse von Pfadkompression mit Vereinigung nach Rang
• 14. Vorlesung am 14. Dezember.
  • Die inverse Ackermannfunktion (Davenport-Schinzel Folgen)
  • Anwendungen von Union-Find (Offline Minimum)
  • Treaps (Balden)
• 15. Vorlesung am 18. Dezember.
  • Analyse der erwarteten Suchzeit in Treaps
  • Analyse der erwarteten Anzahl der Rotationen beim Einfügen/Löschen in Treaps
• 16. Vorlesung am 21. Dezember.
  • Divide-and-Conquer-Rekursionen
• 17. Vorlesung am 8. Januar.
  • Master Theorem für Divide-and-Conquer Rekursionen
  • Berechnungsmodelle: RAM, TM
• 18. Vorlesung am 11. Januar.
  • Bitkomplexität
  • TM Simulation durch RAM
  • Polynomielle Algorithmen (P)
• 19. Vorlesung am 15. Januar.
  • Polynomielle Reduktionen
  • Nichtdeterministisch polynomielle Algorithmen (NP)
  • NP-Vollständigkeit
  • Satz von Cook
• 20. Vorlesung am 18. Januar.
  • Satz von Cook
  • SAT <_P Clique
• 21. Vorlesung am 22. Januar.
  • SAT <_P 3-Colorability
  • 3-Colorability <_P Planar-3-Colorability
  • Set-Cover <_P Subset-Sum
• 22. Vorlesung am 25. Januar.
  • Vertex-Cover <_P Hamiltonkreis
  • Einführung NP-schwere Probleme
• 23. Vorlesung am 5. Februar.
  • Pseudopolynomielle Algorithmen
  • Approximationsalgorithmen für NP-schwere Probleme
• 24. Vorlesung am 8. Februar.
  • Tiefensuche und starke Zusammenhangskomponenten
  • Informationstheoretische untere Schranken
• 2. Klausur am 12. Februar.