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

Abgabe bis 18.12., 12.30 Uhr (verlängert wegen des Streiks)

Aufgabe 7.1 (4 Punkte)

Berechne die minimale Höhe H(k) eines n-ären Baums mit k Knoten! Zeige H(k) = O(log k)!


Aufgabe 7.2 (6 Punkte)

a) (1 P.) Gesucht ist eine Funktion
	put :: * -> num ->   [*] -> [*]
	    || item position old    new
die aus einer Liste old eine Liste new konstruiert derart, daß an der Stelle position der alte Wert durch item ersetzt wird. Die Aufgabe soll ohne Verwendung der Miranda-Standardfunktionen gelöst werden. (Die Stellen einer Liste sind mit 0,1,2,... durchnumeriert.)

b) (2 P.) Für Vielwegbäume sei der folgende Typ vereinbart:
	tree* ::= N * [tree*]
Gesucht ist eine Funktion
	put :: * -> [num] -> tree* -> tree*
            || item position old      new
die aus einem Baum old einen Baum new konstruiert derart, daß an der Stelle position der alte Wert durch item ersetzt wird. (Die Teilbäume eines Baums sind mit 0,1,2,... durchnumeriert. Die Wurzel hat die Position []; die Wurzeln der Teilbäume eines Unterbaums mit Wurzelposition p haben die Positionen p++[0], p++[1],....)

c) (3 P.) Für die Vielwegbäume aus b) ist eine Funktion
	append :: * -> [num] -> tree* -> tree*
	       || item position old      new
gesucht, die aus einem Baum old einen Baum new konstruiert derart, daß an den Knoten position ein zusätzlicher Knoten mit Wert item angehängt wird.


Aufgabe 7.3 (6 Punkte)

Ein baumstrukturiertes Dateisystem kann wie folgt beschrieben werden:

Ein Dateisystem enthält Dateien, die entweder Verzeichnisse sind oder Daten enthalten. Ein Verzeichnis ordnet gewissen Namen gewisse Dateien zu. Eine Datei kann somit identifiziert werden durch Angabe eines Startverzeichnisses und eines Wegnamens, d.i. eine Folge von Namen, die vom Startverzeichnis zur betreffenden Datei führen.

a) Formuliere einen polymorphen algebraischen Typ file * **, der dieser Beschreibung von Dateien entspricht! * ist der Typ der Dateinamen, ** ist der Typ der in einem Nicht-Verzeichnis enthaltenen Daten.

b) Folgende Funktionen sollen entwickelt werden (path* = Typ der Wegnamen):
	valid    :: path* -> file * ** -> bool
	         || valid p d  liefert die Antwort auf die Frage,
	         || ob es eine Datei gibt, die sich von d aus über p
	         || erreichen läßt.

	isdir    :: path* -> file * ** -> bool
	         || isdir p d  liefert die Antwort auf die Frage,
	         || ob die von d aus über p erreichte Datei (falls
	         || vorhanden) ein Verzeichnis ist

	list     :: path* -> file * ** -> [*]
	         || list p d  liefert eine Liste der Namen in 
	         || demjenigen Verzeichnis, das von d aus über p
	         || erreicht wird (wenn es denn ein solches gibt).

	contents :: path* -> file * ** -> **
	         || contents p d  liefert den Inhalt der von d aus
	         || über p erreichbaren Datei (sofern es sie gibt und
	         || sie kein Verzeichnis ist).


Aufgabe 7.4 (6 Punkte)

Wir betrachten ein Dateisystem gemäß Aufgabe 3, bei dem sowohl die Daten als auch die Dateinamen Zeichenfolgen sind. Zu spezifizieren und zu implementieren sind die folgenden Funktionen, welche modifizierende Operationen auf Dateien und Dateisystemen nachbilden:

append, erase für Dateiinhalte,
create, delete, rename, copy für Dateien.




25.11.1997