tatsächlicher Inhalt der Vorlesung Algorithmen und Programmierung III

• Donnerstag, 21. 10. 1999
• Überblick
• Asymptotische Laufzeitanalyse, O-Notation
• Sortieren durch Einfügen
• Dienstag, 26. 10. 1999
• Sortieren durch Einfügen - Laufzeitanalyse
• Sortieren durch Auswahl
• Topologisches Sortieren
• Donnerstag, 28. 10. 1999
• Topologisches Sortieren - Analyse von Laufzeit und Speicherplatz
• Teile und herrsche als Algorithmenentwurfsprinzip
• Quicksort
• Auswahl des Teilungspunktes:
• mittleres Element
• zufälliges Element
• Median von drei Elementen
• Sortieren durch Verschmelzen
• Lösung der Rekursion T(n)=O(n)+2*T(n/2)
• Dienstag, 2. 11. 1999
• Prioritätswarteschlangen: Einfügen und Minimum entfernen
• Halden
• Haldenoperationen in O(log n) Zeit
• Sortieren mit einer Halde (heapsort)
• Erstellen einer Halde in O(n) Zeit
• Donnerstag, 4. 11. 1999
• abstrakte Datentypen in Java
• abstrakte Klassen und Schnittstellen (interfaces)
• Generizität in Java durch Parameter vom Typ Object
• ereignisgesteuerte Simulation mit Prioritätswarteschlangen
• Dienstag, 9. 11. 1999
• abstrakte Datentypen in Haskell
• Typklassen
• Bäume
• Bäume als spezielle Graphen
• Wurzelbäume
• Bäume als Darstellung hierarchischer Strukturen
• Entscheidungsbäume
• Bäume als Datenstrukturen
• algebraische Datentypen in Haskell
• rekursive Datentypen
• Feldnamen
• Donnerstag, 11. 11. 1999
• binäre Bäume
• Tiefe eines Knotens, Höhe eines Baumes
• Hauptreihenfolge, Nebenreihenfolge, symetrische Reihenfolge, Niveau-Reihenfolge
• Darstellung als rekursiver Datentyp in Haskell und Java
• Suchbäume
• suchen, einfügen
• algebraische Datentypen
• "Fehler"-Typen in Haskell (Error a; Maybe a)
• Dienstag, 16. 11. 1999
• Suchbäume
• einfügen und entfernen
• Laufzeitanalyse
• Sortieren mit einem Baum (treesort)
• durchschnittliche Laufzeit; Vergleich mit Quicksort
• Donnerstag, 18. 11. 1999
• Suchbäume
• Durchlaufen in symmetrischer Reihenfolge
• ausgeglichene Bäume
• Rotationen
• AVL-Bäume (nur erwähnt, siehe auch Übungsblatt)
• 2-3-Bäume
• Dienstag, 23. 11. 1999
• Suchbäume
• a-b-Bäume, B-Bäume, externer Speicher
• Suchbäume als Datenstrukturen für Mengen (interface Set) und für Zuordnungen (Map)
• Bäume mit zusätzlichen Informationen zur Auswahl des i-größten Elements
• Modularisierung
• Moduln zur Zerlegung großer Projekte, Schnittstellen zwischen Moduln
• Kontrolle der Sichtbarkeit von innen nach außen und von außen nach innen, Export und Import
• Freiheit der Wahl von Bezeichnern
• Gründe für die Modularisierung
• Zerlegung einer Aufgabe in gleichberechtigte Teile
• nützliche Hilfsmoduln (Programmpakete und -bibliotheken)
• Moduln und Exportlisten in Haskell
• Export von Typen ohne Konstruktoren; abstrakte Datentypen
• Donnerstag, 25. 11. 1999
• Modularisierung
• Moduln und Importlisten in Haskell, qualifizierter Import
• Moduln in Java (packages), öffentliche (public) Klassen und Schnittstellen
• Klassen: Kontrolle der Sichtbarkeit (public, private, protected, package)
• Moduln in Modula und Ada: Trennung von Definition und Implementierung
• Die Collection-Klassen in java.util als Beispiel aus einer Klassenbibliothek
• die Iterator-Schnittstelle und ihre Verwendung
• Dienstag, 30. 11. 1999: erste Zwischenklausur. Stoff: Bäume, Sortieren
• Donnerstag, 2. 12. 1999: entfällt
• Dienstag, 7. 12. 1999
• Die Collection-Klassen in java.util als Beispiel aus einer Klassenbibliothek
• die Schnittstellen Set, List und Map
• Gegenüberstellung von Schnittstellen und abstrakten Klassen
• Ereignisgesteuerte Warteschlangensimulation in Java - objektorientierter Entwurf
• Donnerstag, 9. 12. 1999
• statische Klassenfelder und -methoden in Java
• Hash-Tabellen
• Speicherfunktion, hash-Funktionen
• behandeln von Überlauf: getrennter Überlaufbereich oder offene Adressierung
• durchschnittliche Such- und Einfügezeit
• Dienstag, 14. 12. 1999
• Sortieren durch Fachverteilung
• Sortieren zufälliger Daten in linearer Zeit
• Radix-Sort
• Graphen: Speichern von Graphen
• Donnerstag, 16. 12. 1999
• Graphen: Absuchen von Graphen; Tiefensuche und Breitensuche
• Dienstag, 4. 1. 2000
• Graphen: kürzeste Wege; der Algorithmus von Dijkstra
• Donnerstag, 6. 1. 2000
• Suchen in Zeichenketten; der Algorithmus von Knuth-Morris-Pratt
• Dienstag, 11. 1. 2000
• Spezifikation und Korrektheit
• Stellung der Spezifikation zwischen Anforderungen und Implementierung
• Präzision und Vollständigkeit von Spezifikationen
• natürlichsprachliche (informelle) und formale Spezifikation
• Spezifikation als Voraussetzung für Korrektheitsbeweise
• Spezifikation und Korrektheit auf verschiedenen Abstraktionsebenen
• Spezifikation abstrakter Datentypen
• Korrektheit von Implementierungen abstrakter Datentypen
• Donnerstag, 13. 1. 2000
• algebraische Spezifikation
• Beispiele:
• Stapel
• Menge mit Einfügen und Löschen einzelner Elemente
• Transformation auf eine Normalform
• Fehlerbehandlung, undefinierte Operationen
• Analogie zur Manipulation von Gleichungen in der Algebra
• automatische Implementierung mit algebraischen Datentypen in Haskell
• Herleitung zusätzlicher Unformungsregeln
• verschiedene Darstellungsmöglichkeiten, die sich daraus ergeben
• Dienstag, 18. 1. 2000
• prototypische Implementierung einer Spezifikation
• automatische Herleitung einer korrekten Implementierung aus der Spezifikation
• Gegenüberstellung der Vor- und Nachteile verschiedener Implementierungen
• [ Nebenbemerkung: Geisterstrukturen ]
• Haskell als Spezifikationssprache
• Korrektheitsbeweis durch Induktion nach den Parametern
• Donnerstag, 20. 1. 2000: zweite Zwischenklausur. Stoff: Graphen und Zeichenketten
• Dienstag, 25. 1. 2000
• digitaler Suchbaum (trie)
• komprimierter digitaler Suchbaum (mit linearer Knotenzahl)
• Codes
• eindeutig entzifferbare Codes und präfixfreie Codes
• präfixfreie Codes und Codebäume
• Gewicht eines Codes; gewichtete äußere Pfadlänge eines Baumes
• Donnerstag, 27. 1. 2000
• optimale Codes, der Huffman-Algorithmus
• geometrische Objekte
• Polygone
• Test, ob ein Punkt in einem Polygon enthalten ist
• das Maßproblem (Flächeninhalt eines Polygons)
• Dienstag, 1. 2. 2000
• geometrische Algorithmen
• konvexe Hülle einer sortierten Punktmenge
• Orientierungstest für drei Punkte
• das Streckenschnitt-Problem
• die plane-sweep-Methode
• Donnerstag, 3. 2. 2000
• dynamische Programmierung: Finden der längsten Teilfolge
• kürzeste Spannbäume
• der Algorithmus von Kruskal
• der gierige Algorithmus
• Dienstag, 8. 2. 2000
• Spielbäume, alpha-beta-Suche
• Donnerstag, 10. 2. 2000
• dynamische Speicherverwaltung
• stack und heap (Keller und Halde)
• Programmiersprachen mit Speicherfreigabe durch den Programmierer (dispose, free)
• Müllsammlung (garbage collection); Referenzzähler und Markierungsmethoden
• Freispeicherorganisation, Fragmentierung
• Dienstag, 15. 2. 2000
• dauerhafte Objekte (Persistenz und Serialisierung) in Java
• Einbrecher fangen
• Übersetzung einer informellen Spezifikation in eine formale
• als erster Schritt zur Implementierung
• Formulierung als Wegproblem in einem Graphen
• Donnerstag 17. 2. 2000: dritte Zwischenklausur. Stoff: Spezifikation und Korrektheit, Graphenalgorithmen, Codes, geometrische Algorithmen.