6. Aufgabenblatt vom Montag, den 24. November 2008 zur Vorlesung

Informatik A(Frank Hoffmann)

Abgabe am Mittwoch, den 03. Dezember 2008 bis 830

1. List comprehension (2 Punkte) Finden Sie heraus, was folgende Funktion f tut undbeschreiben Sie deren Arbeitsweise verbal! Dies soll die Notwendigkeit von sinnvollenBezeichnern bzw. Kommentierung illustrieren.

f [] =[[]]f xs =[x:p| x<- xs , p<- f (g x xs)]

whereg x [] = []g x (y:ys)

| x==y = ys| otherwise= y:(g x ys)

2. Textverarbeitung (8 Punkte) Folgende Funktion liefert jeder bessere Texteditor undSie sollen dies in Haskell programmieren.Die Funktion

findAndReplace:: String->String->String->String

ersetzt sequentiell in einem Text jedes Vorkommen eines Strings str durch einenanderen String newstr. Zur Aufgabe gehort es, diese Funktionalitat zunachst zuspezifizieren, denn die Aufgabenstellung ist so noch nicht eindeutig. Es konnte ja sein,der neue String enthalt wieder den alten, es konnte eine Suffix–Prafix–Uberlappung instr geben, was ist mit Groß–Kleinschreibung usw.Definieren Sie geeignete Hilfsfunktionen, die entsprechende Teilprobleme losen.

3. Teilsequenztest (6 Punkte) Implementieren Sie eine FunktionisSubsequence:: (String, String) -> Bool.Diese sollen testen, ob in dem Eingabestringpaar ein String Teilsequenz des anderen ist.Ein String ist Teilstring eines anderen, wenn er als Teilwort von aufeinander folgendenZeichen auftritt. Bei der Teilsequenz mussen die Zeichen nur in der richtigen Reihenfolgeauftreten. Also IFOA ist Teilsequenz von INFORMATIKA aber kein Teilstring. ORMAware ein solcher Teilstring und automatisch auch Teilsequenz.Wie oft kann ein String der Lange k > 0 in einem String der Lange n als Teilstring bzw.Teilsequenz vorkommen? Geben Sie genaue untere und obere Schranken an!Zusatzaufgabe: (4 Punkte) Schreiben Sie eine Funktion, die zahlt, wie oft ein String alsTeilsequenz im Eingabestring vorkommt!

4. Simultanes Min-Max (4 Punkte)Schreiben Sie eine rekursive Funktion zur simultanen Bestimmung des Minimums und

des Maximums in einer Liste von ganzen Zahlen.Analysieren Sie, wie viele Vergleiche zwischen Listenelementen Ihr Verfahren macht beieiner Liste der Lange n. Diese Anzahl sollte kleiner (!) sein als 2n − 2, was entsteht,wenn man Minimum und Maximum getrennt bestimmt.

Hinweis: Achten Sie bei Programmieraufgaben immer auf eine ausreichende und klare Kom-mentierung, fur die es die Halfte der Punkte gibt, naturlich nur unter der Voraussetzung, dassdie Funktionen das Gewunschte leisten.