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. 6

Abgabe: Freitag 16. Januar 1998 vor der Vorlesung

Aufgabe 1 (10 Punkte)

In der Vorlesung wurde die Funktion for definiert. So wie sie dort definiert ist, ist der Zählerstand im Schleifenkörper nicht sichtbar. Verändern Sie die Definition so, daß der Zählerstand im Schleifenkörper beliebig verändert werden kann und für jeden erneuten Aufruf von for dieser (möglicherweise) veränderte Zählerstand um schritt weiterzählt. Erweitern Sie dazu den Datentyp auf dem der Schleifenkörper operiert zu einem Tupel, dessen erste Komponente der Zählerstand ist.

Aufgabe 2 (10 Punkte)

Schreiben Sie zu

  1. concat xs = foldr (++) []
  2. length xs = foldl (\n _-> n + 1) 0
  3. reverse xs = foldl (flip (:)) []
  4. sum xs = foldl (+) 0

entsprechende Funktionen mit while. Vergleichen Sie die Zahl der Schritte für 3 Beispiele jeweils für die Definitionen mit foldl/foldr und while. Vergleichen Sie für length und sum auch mit den Definitionen, die foldl' verwenden.

Aufgabe 3 (10 Punkte)

Programmieren Sie mit list comprehensions:

1. die Liste der Quadrate aller geraden und durch 3 teilbaren natürlichen Zahlen

2. die Liste der Liste von Paaren, wobei die erste Komponente jedes Paares einer inneren Liste gleich ist, die zweite Komponente größer als die erste ist und die inneren Listen in der äußeren bzgl. ihrer ersten Komponente eine aufsteigende Folge bilden

Programmieren Sie die Ausdrücke nun ohne list comprehensions mit map und filter.

Aufgabe 4 (10 Punkte)

Betrachten wir folgende Relationen zwischen Menschen:

• ‘ist bekannt mit‘

• ‘ist Geschwister von‘

• ‘ist verheiratet mit‘

• ‘ist geschieden von‘

• ‘ist Elternteil von‘

• ‘ist Kind von‘

1. Welche der Relationen sind reflexiv, transitiv, symmetrisch, antisymmettrisch, asymmetrisch oder linear?

2. Für welche der Kompositionen von zwei der Relationen oben kennen Sie gewöhnlich benutzte Bezeichnungen?

3. Beschreiben Sie die Relationen, die sich aus der reflexiven bzw. der transitiven Hülle der obigen Relationen ergeben.

Aufgabe 5 (10 Punkte)

Eine Zeichenkette über einem Alphabet Σ ist eine endliche Folge von Elementen aus Σ (Buchstaben). Ein Sonderfall ist die leere Zeichenfolge ϵ. Unten stehen drei Relationen auf Zeichenketten, zwei davon sind fundiert eine ist es nicht. Geben Sie für jede fundierte Ralation eine kurze Begründung warum sie fundiert ist. Geben Sie für die Relation die nicht fundiert ist eine unendliche absteigende Folge an.

1. Die Relation ≺_{1} ist die gewöhnliche alphabetische Ordnung auf Zeichenketten (die “Wörterbuch”-Ordnung). Sie kann durch die folgenden zwei Axiome charakterisiert werden.

ϵ ≺_{1} s genau dann, wenn s ≠ ϵ
a_{1}s ≺_{1} a_{2}t genau dann, wenn a_{1} kommt im Alphabet vor a_{2} oder [a_{1} = a_{2} und s ≺_{1} t]

2. Die zweite Relation ordnet Zeichenketten nach deren Länge:

a_{1} … a_{k} ≺_{2} b_{1} … b_{l} genau dann, wenn k < l

3. Die dritte Relation, ≺_{3}, kombiniert die vorigen beiden, indem ≺_{2} auf Zeichenketten verschiedener Länge verwendet wird und ≺_{1} auf Zeichenketten gleicher Länge.

a_{1} … a_{k} ≺_{3} b_{1} … b_{l} genau dann, wenn k < l oder [k = l und a_{1} … a_{k} ≺_{1} b_{1} … b_{l}]