ALP III - Übungsblatt 11

WS 97/98: Algorithmen und Programmierung III - Übungsblatt 11

Abgabe bis 29.1., 12.30 Uhr

Beachte: Der Allquantor über Mengen/Listen kann in Miranda wie folgt formuliert werden:

	all list predicate = and (map predicate list)

Aufgabe 1 (4 Punkte)

Ein abstrakter Typ Abbildung sei wie folgt spezifiziert:

abstype mapping * ** || Modell:     Abbildung von * nach **;
                     || alternativ: ein Wert vom Typ [(*,**)]
                     ||             (bei Ignorierung der Reihenfolge)

with notdef   :: mapping * **
              || Die überall undefinierte Abbildung

     change   :: mapping * ** -> * -> ** -> mapping * **
              || a = change m x y  unterscheidet sich von m allenfalls
              || an der Stelle x:  a(x)=y

     restrict :: mapping * ** -> * -> mapping * **
              || a = restrict m x  unterscheidet sich von m allenfalls
              || an der Stelle x:  a(x) ist undefiniert

     apply    :: mapping * ** -> * -> **
              || apply m x = m(x), falls m(x) definiert ist

     isdef    :: mapping * ** -> * -> bool
              || isdef m x  gibt Antwort auf die Frage, ob m(x) definiert ist

     invar    :: mapping * ** -> bool
	      || Die konkrete Invariante:  ?

     abstr    :: mapping * ** -> [(*,**)]
              || Die Abstraktionsfunktion: ?

Repräsentiere mapping in Miranda als einfachen binären Suchbaum, in dem die Einträge (s,d) gemäß s sortiert sind! Gib die konkrete Invariante invar und die Abstraktionsfunktion abstr an - ebenfalls in Miranda!

Aufgabe 2 (6 Punkte)

Unter Verwendung von mapping aus Aufgabe 1 werde der abstrakte Datentyp Wörterbuch (= Menge von Wörtern) wie folgt als trie repräsentiert:

	abstype dict
	with .....

	trie ::= F(mapping char trie)
	dict == trie

Ein Wort findet man im trie als Folge von Kleinbuchstaben von der Wurzel zu einem Blatt wieder. In einem Blatt kann - muß aber nicht - das Sonderzeichen '.' als Wortende-Markierung auftreten. Beispiel:


                          /|\
                         / | \
                        d  e  s
                       /|\  \  \
                      a e u  r  o
                     / \ \ \    |\
                    .  s r .    . g

Gib in Miranda die konkrete Invariante und die Abstraktionsfunktion an!

Aufgabe 3 (4 Punkte)

a) Implementiere die Operation insert :: [char]->dict->dict, die ein Wort in das Wörterbuch aus Aufgabe 2 einfügt!

[ b) optional ] Es sollen Wörter mit maximaler Wortlänge l gespeichert werden. Bestimme die worst-case-Komplexität des Suchens nach einem Wort, wenn für die Speicherung das Wörterbuch aus Aufgabe 2 verwendet wird! Ist das besser oder schlechter als wenn die Wörter direkt in einem Suchbaum von Wörtern gespeichert würden? Wie kann die Komplexität weiter verringert werden?

20.1.1998