Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik (20) Künstliche Intelligenz/Softwaretechnologie Johann Wolfgang Goethe-Universität Frankfurt am Main

Praktische Informatik 1

Wintersemester 1997/98

Übungsblatt Nr. 8

Abgabe: Freitag 30. Januar 1998 vor der Vorlesung

Aufgabe 1 (15 Punkte)

Schreiben Sie eine Funktion, die gegeben ein 2-dimensionales Feld Zeilen und Spalten des Feldes vertauscht (das Feld transponiert). Das Feld ist als Haskell array gegeben und der Index ist ein Paar von Ints.

Aufgabe 2 (15 Punkte)

Im Skript, Kapitel 3, Seite 23, ist eine Implementierung von Datenbanken mit Assoziationslisten angegeben. Beschreiben Sie Stärken und Schwächen und evtl. vorhandene Fehler der dort angegebenen Implementierung. Bestimmen Sie die Größenordnung des Resourcenbedarfs für die einzelnen Funktionen und korrigieren Sie evtl. vorhandene Fehler.

Bonus-Aufgabe 3 (10 Punkte)

Argumentieren Sie warum der Schnitt von Mengen, die als Suchbäume vorliegen mit dem naheliegenden Algorithmus nicht in linearer Zeit berechenbar ist.

Aufgabe 4 (10 Punkte)

Schreiben Sie die Funktionen merge_vereinigung und merge_differenz für sortierte Listen.

Aufgabe 5 (15 Punkte)

Schreiben Sie eine Funktion, die die Potenzmenge, P(M), einer Menge M berechnet, wenn M als endliche Liste vorliegt. In P(M) soll jedes Element nur einmal vorkommen.