tatsächlicher Inhalt der Vorlesung Algorithmen und Programmierung III, WS 2003/04

• Montag, 20. 10. 1999
• Überblick
• Laufzeit und Speicherbedarf von Algorithmen
• Sortieren durch Einfügen, mit Laufzeitanalyse
  
• Asymptotische Laufzeitanalyse, O-Notation (Wiederholung)
  
• Donnerstag, 23. 10. 2003
• O-Notation
• Sortieren durch Auswahl
• Sortieren durch Vergleichen (Bubblesort)
  
• Topologisches Sortieren
• Montag, 27. 10. 2003
• Analyse von Topologischem Sortieren
• Teile-und-herrsche als Algorithmenentwurfsprinzip
  
• Sortieren durch Verschmelzen (Mergesort)
• Quicksort
• Analyse von randomisiertem Quicksort
• Harmonische Reihe
• Donnerstag, 30. 10. 2003
• Untere Schranke für die Anzahl der Vergleiche zum Sortieren
• Entscheidungsbäume
  
• Prioritätswarteschlangen: Einfügen und Minimum entfernen
• Halden
• Haldenoperationen in O(log n) Zeit
• explizite und implizite Datenstrukturen
  
• Montag, 3. 11. 2003
• Sortieren mit einer Halde (heapsort)
• diskrete Ereignis-Simulation (DES) als Anwendung von Prioritätswarteschlangen
• Donnerstag, 7. 11. 2003
• diskrete Ereignis-Simulation: Beispiel Schilift
• Systematisches Durchsuchen von Lösungsbäumen (backtracking)
• Beispiel: das 8-Damen-Problem
  
• Montag, 10. 11. 2003
• 8-Damen-Problem: Beschleunigung durch Speicherung von mehr Information
• Elimination der Endrekursion
  
• Donnerstag, 13. 11. 2003
• Elimination der Endrekursion, Beispiele:
• Transformation der Rekursion in Endrekursion (Funktion n!)
  
• Quicksort mit logarithmischem Speicher
• Suchbäume (Wiederholung):
• binäre Bäume, Tiefe, Höhe, Grad von Knoten
  
• Suchbaumeigenschaft
• Suchen proportional zur Tiefe (ebenso einfügen und entfernen)
• bestmöglich und schlechteste Tiefe für einen Baum mit n Knoten
  
• Montag, 17. 11. 2003
• balancierte Bäume, Rotationen, AVL-Bäume, Rot-Schwarz-Bäume
  
• Donnerstag, 20. 11. 2003
• 2-3-Bäume, a-b-Bäume
• Montag, 24. 11. 2003
• Erweitern von Suchbäumen zur Unterstützung von weiteren Operationen, zum Beispiel zur Bestimmung des  k-größten Elements
• Sortieren durch Fachverteilung
• bucketsort
• radixsort
• optimale Wahl der Schrittzahl bei radixsort
• Sortieren von zufällig verteilten reellen Zahlen duch Fachverteilung
  
• Donnerstag, 27. 11. 2003: wegen Streik entfallen
• Kodes und Kode-Bäume, die Kraft'sche Ungleichung, Entropie
• der Huffman-Algorithmus zur Konstruktion optimaler Kodes
• Montag, 1. 12. 2003: außerhalb des eigentlichen Vorlesungsstoffes:
  • Entscheidungsfindung in Gruppen: das Condorcet-Kriterium, soziale Entscheidungsfunktionen, das Arrow'sche Paradoxon (der Satz vom Diktator)
    
  • Wahlsysteme: proportionale Aufteilung, Einzelwahlen. Strategisches Wahlverhalten. approval voting
  • kombinatorische Versteigerungen
  • rationales Entscheiden in Anbetracht von Ungewissheit: das Allais'sche Paradoxon
• Donnerstag, 4. 12. 2003: vor dem Roten Rathaus:
  Wegen der kurzfristigen Terminankündigung wird der Stoff dieser Vorlesung nicht in den Klausuren geprüft.
  
• Kodes und Kode-Bäume, die Kraft'sche Ungleichung, Entropie
• Montag, 8. 12. 2003: entfällt
  
• Donnerstag, 11. 12. 2003
  
• der Huffman-Algorithmus zur Konstruktion optimaler Kodes
• Programmiermethodik
• Überblick
  
• Qualitätsmerkmale guter Programme und Software
• Anforderung, Spezifikation, Implementierung
• Modularisierung
• Spezifikation abstrakter Datentypen
  
• Montag, 15. 12. 2003
• Korrektheitsbeweis einer Implementierung eines abstrakten Datentyps (Beispiel: Menge)
• Dienstag, 16. 12. 2003, 14-16 Uhr: Zwischenklausur, im Hörsaal AC für Anorganische Chemie, Fabeckstraße 34-36
• Stoff: Vorlesungsstoff bis einschließlich 24.11. und 6. Übungsblatt.
• Donnerstag, 18. 12. 2003
• Modellierende Spezifikation eines abstrakten Datentyps. Beispiel: Stapel
• Algebraische Spezifikation eines abstrakten Datentyps. Beispiel: Menge
• Terme, strukturelle Induktion
• Entsprechung zu algebraischen Datentypen in Haskell
• Herleitung einer Implementierung als algebraischer Datentyp aus einer algebraischen Spezifikation
• Montag, 5. 1. 2004
  • Einführung der Gleichheitsrelation für Terme
  • Herleitung zusätzlicher Regeln
    
  • Herleitung von verschiedenen Implementierungen aus einer algebraischen Spezifikation
  • Die Collection-Klassen in Java
    
• Donnerstag, 8. 1. 2004
• Das Iterator-Konzept und die Iterator-Schnittstelle in Java
• Wörterbücher als abstrakte Datentypen in Java (die Map-Klassen)
• Graphen
• Wiederholung der Grundbegriffe
• Speicherung von Graphen im Computer: Adjazenzmatrix und Adjazenzlisten
  
• Montag, 12. 1. 2004
• Graphenalgorithmen
• Tiefensuche und Breitensuche
• Donnerstag, 15. 1. 2004
• Graphenalgorithmen
• Breitensuche, der kürzeste-Wege-Baum
  
• kürzeste Wege, der Algorithmus von Dijkstra
  
• Montag, 19. 1. 2004
• Implementierung einer Prioritätswarteschlange mit "verkleinereSchlüssel"-Operation
• Realisierung als gekapselter Datentyp, Zugriff durch Rückgabe eines Zugriffszeigers beim Einfügen
• Bäume: Wiederholung von Definitionen und Eigenschaften aus der Graphentheorie
• Das Problem des kürzesten Spannbaumes (minimum spanning tree)
• Der gierige Algorithmus
  
• Dienstag, 20. 1. 2004, 16-18 Uhr: Ersatzklausur zur Zwischenklausur
• Stoff: Vorlesungsstoff bis einschließlich 24.11. und 6. Übungsblatt.
• Donnerstag, 22. 1. 2004
• Der Algorithmus von Kruskal (gierige Algorithmus) für kürzeste Spannbäume: Korrektheitsbeweis und Implementierung
• Bearbeitung von Zeichenketten, das Teilwort-Problem
• Der Algorithmus von Knuth, Morris, und Pratt; Definition der Verschiebefunktion.
• Montag, 26. 1. 2004
• Berechnung der Verschiebefunktion
• Digitale Suchbäume (tries), komprimierte digitale Suchbäume,
• Donnerstag, 29. 1. 2004
  
• Suffixbäume
• andere Algorithmen für das Teilwortproblem (erwähnt)
  
• Geometrische Daten: Punkte, Geraden, und Strecken;
• Grundlegende geometrische Operationen, Probleme mit Sonderfällen, numerische Robustheit von Algorithmen
  
• Montag, 2. 2. 2004
• Berechnung des Flächeninhalts
• Orientierungstest
  
• Donnerstag, 5. 2. 2004
• Konvexe Hülle in der Ebene: inkrementeller Algorithmus für sortierte Punkte
  
• Überstreichen der Ebene (plane-sweep), das Streckenschnittproblem
• Montag, 9. 2. 2004
• dynamische Speicherverwaltung, "garbage collection"
• Modularisierung und Sichtbarkeit, Module in Haskell
  
• Donnerstag, 12. 2. 2004
• Modularisierung und Sichtbarkeit
• packages in Java
• Persistenz von Daten und Serialisierung
• Dateiein- und -ausgabe
  
• Montag, 16. 2. 2004
• Bewertung von Spielbäumen, alpha-beta-Suche
• Donnerstag, 19. 2. 2004: Zweite Klausur.
• Stoff: Vorlesungsstoff ab 11.12. und 7. Übungsblatt.