WS 97/98: Algorithmen und Programmierung III - Ersatz-Aufgabenblatt



Aufgabe 1 (7 Punkte)

Wir betrachten die Implementierung tabellierter Abbildungen. Bei Mehrweg-Suchbäumen auf Hintergrundspeichern entscheidet man sich häufig dafür, die Daten nur in den Blättern unterzubringen, so daß die Nichtblätter nur Schlüssel enthalten. Wenn man für binäre Suchbäume entsprechend vorgeht, kann man wie folgt spezifizieren und repräsentieren (all = Allquantor): 
model * ** == [(*,**)]     || tabulated mapping
invariant m = all[1..#m-1]less
              where lees i = fst(m!(i-1)) < fst(m!i)

abstype mapping * **
with notdef :: mapping * **
            || the undefined mapping (empty table)
     change :: mapping * ** -> (*,**) -> mapping * **
            || change m(k,d)  is m modified to map k to d
            || (table update)
     apply  :: mapping * ** -> * -> **
            || apply m x  is the result of applying m to x
            || if x in domain of m (table lookup)

bst * ** ::= Empty | Leaf * ** | Node(bst * **)*(bst * **)

mapping * ** == bst * **

abstr Empty       = []
abstr(Leaf k d)   = [(k,d)]
abstr(Node l x r) = abstr l ++ abstr r

invar Empty = True
invar(Leaf k d) = True
invar(Node l x r) = l~=Empty & r~=Empty &
                    invar l  & invar r  &
                    all[fst y|y<-abstr l](>x)  &
                    all[fst y|y<-abstr r](>=x) &
                    min[fst y|y<-abstr r] = x
Gesucht ist die Implementierung von change.


Aufgabe 2 (7 Punkte)

In Aufgabe 11.2 ging es um die Implementierung eines Wörterbuchs als trie. Für die dort verwendete Repräsentation soll eine Miranda-Funktion list entwickelt werden, die alle im Wörterbuch vorhandenen Wörter auflistet. (Achtung: Dies erfordert mehr als ein einfaches Traversieren.)




14.2.1998