Material
Folien
Abstrakte
Datentypen 1 Allgemeines, Algebraische Spezifikation
ADT 2 : Modellierende Spezifikation
ADT 3 : Anwendung Stack, "Factory
Pattern"
Hinweise zur Postfix-Darstellung von
arithmetischen Ausdrücken
ADT 4: Modell und Repräsentation
ADT 5: Abstraktionsfunktion, Repräsentationsinvariante,
Mengen und Vektoren
ADT 6: Datenabstraktion und Objektorientierung
ADT 7: Polymorphie, Spezifikation und
Vererbung (siehe auch unter Programme: FooBar, C1)
DS 1: Folgen, Collections,
Iteratoren
Tree 1: Bäume: Grundlagen, Beweis
zur Anzahl äußerer und innerer Knoten
Tree 2: Spezifikation, funktionale
Implementierung, Operatorbaum
Tree 3: Anwendung Huffman
- Code , Artikel von
Shannon
Tree 4: Implementierung von Bäumen
(1+2)
SetMap 1: Effiziente Implementierung
von Mengen: Übersicht.
SetMap 2: Binärer Suchbaum,
AVL-Baum(1)
Skiplist:: Sprunglisten -
randomisierte Indexstrukturen (Originalliteratur
dazu)
B-Baum: ausgelichener Mehrweg-Suchbaum,
Speziell: (2,4)-Baum
Rot-Schwarz-Baum: effizienter binärer
Suchbaum
Hash-Verfahren: Def, Kollisionsbehandlung,
Laufzeit, Hash-Funktionen, Universelle H-Fkt.,
(Die Folien sind gegenüber vergangener Woche ergänzt worden!)
Erweiterung und Anwendung: HashTable
in Java, Erweiterbare Hash-Funktionen, Bloom-Filter.
Heap
Graphen (1): Anwendungen,
Terminologie, Implementierungen, Tiefen-, Breitensuche.
Graphen(2): Kürzeste Weg (Dijkstra).
Graphen(3): Minimale spannende Bäume,
Topologische Sortierung (ergänzt, 6.2.)
Digitalbäume und Tries
Suffixbäume. Ein Übersichtsartikel dazu
hier.
Programme
VL 1 und 2, 3
MaxDiff.java
MaxDiffSlow.java
MaxDiff1.java
MaxDiffexperiment (Vergleich von 2 Algorithmen durch Messung, s. VL)
Hier noch einige Anmerkungen zu Messungen mit dem erwähnten Messwerkzeug.
VL 4.11.:
Programme zur Anwendung von Stapeln (stacks),
Auswertung von arithmetisch
Ausdrücken in Postfix-Darstellung.
VL 11.11
Spezifikation und Implementierung von Mengen mit Vektoren u.a. : IF,
Impl1, Impl2
Haskell Modul Set
VL 19.11.
Aufruf und dynamischer Methoden FooBar, C1.
Sonstige Software
jds.jar Bibliothek
mit Datenstrukturen von T. Budd , u.a. mit
Hilfmitteln
für Laufzeitmessungen.
Dokumentation dazu.
Die in MaxDiff etc verwendete Klasse
Random sowie andere.
Wegen Namenskollisionen mit Java Bibliothek mit Vorsicht zu geniessen!
Rahmenprogramm für Messungen mit graphischer Ausgabe
Linearer versus quadratischer Algorithmus für max. Kursgewinn
(siehe VL)
Ein professionelles
Programmpaket (open source) für Graphen
(Autor: J.M.Salvo jr,
http://openjgraph.sourceforge.net ),
zip-Datei (lokal)
Allgemeines
UML Tutorial Eine Einführung in UML