Material

Folien 

Einführung 1, 2

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.

 

Übersicht Teil2
  

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

  



hs@inf.fu-berlin.de