Algorithmen und Programmierung III
VL 19510
WS 2001/2002
| Di. 16 - 18 | HS Informatikgebäude | Dozent: Prof. Dr. H. Schweppe | |
| Do. 12 - 14 | HS Informatikgebäude | Sprechstunde: Mi. 14 - 16 |
Inhalt der Veranstaltung
Im 3. Semester des Zyklus Algorithmen und Programmierung werden Daten- und Programmstrukturen behandelt. Ausgangspunkt ist das Geheimnisprinzip und seine Bedeutung für die Strukturierung von Programmen und die Konstruktion von Datenobjekten mittels Modulen und Klassen. Eine zentrale Rolle bei der Modellierung von Daten spielt der Begriff der Datenabstraktion verbunden mit der Unterscheidung zwischen Spezifikation und Implementierung abstrakter Datenobjekte und Datentypen. Mengen, Relationen, Listen, Bäume, Graphen u.a. werden als abstrakte Typen eingeführt. Anschließend werden effizient manipulierbare Repräsentationen dieser Typen betrachtet und die zugehörigen Algorithmen auf ihre Komplexität hin untersucht. Zu den für die Repräsentation verwendeten Verfahren und Datenstrukturen gehören Hashtransformationen, binäre Bäume und Suffixbäume.
In der objektorientierten Programmierung
spielen neben der Datenabstraktion Vererbung und Polymorphie eine wesentliche
Rolle. Wir werden daher abstrakte Datentypen häufig unter Verwendung
von Vererbungsmechanismen spezifizieren und implementieren. Programmiert
wird imperativ mit Java und funktional mit Haskell.
Material
Folien-1 (pdf)
Verifikation-Folien (pdf)
Programmentwicklung-Folien (pdf)
Datenabstraktion-Folien (I) (pdf)
Datenabstraktion-Folien (II) (pdf)
Datenabstraktion-Folien (III) (pdf)
Modellierung mit Java (I) (pdf)
Modellierung mit Java (II) (Power Point Folien) (pdf)
UML Tutorial Eine nette Einführung in UML
Datenstrukturen-Folien (I) (pdf)
Datenstrukturen-Folien (II) (pdf)
Effiziente Repräsentation von Mengen (Übersicht) (pdf)
Programm "Einfügen in binären Suchbaum" (s. VL)
NEU: Folien zu AVL- und B-Bäumen, Hash-Verfahren (nicht vollständig!)
Programm "Hash mit Verkettung"
Programm Binary Heap
Folien Graphen (1)
Folien Graphen (2)