Übungen - Verarbeitung von Zeichenketten

Aufgabe 1 (Löffelsprache)

Die Löffelsprache ist eine Geheimsprache, bei der man die Vokale durch andere Zeichenketten ersetzt.

Hier ein Beispiel für eine Ersetzung:

A -> ALI
E -> EVA
I -> IDA
O -> OKA
U -> URI

Mit dieser Festlegung kann man jetzt Texte (die nur aus Großbuchstaben bestehen) so umwandel, dass sie kaum noch verständlich sind.

KAUM ZU VERSTEHEN -> KALIURIM ZURI VEVARSTEVAHEVAN

Ziel dieser Aufgabe ist es, die Erzeugung von solchen Texten mit der Funktion verschluesselterText durchzuführen.

Signatur:
verschluesselterText: String -> String
Beispiele:
verschluesselterText "HALLO" -> "HALILLOKA"

(a) Implementiere die Funktion verschluesselterText. Erkläre dabei auch die verwendete rekursive Problemreduktionsstrategie.

(b) Ändere die Geheimsprache nach deinen Wünschen ab.

Aufgabe 2 (Geheimsprache)

Im dem Buch Die wilden Hühner von Cornelia Funke benutzt eine Gruppe von Schüler*innen eine Art Geheimschrift, um Nachrichten verschlüsselt weiterzugeben. Hier ein Beispiel für eine verschlüsselte Nachricht:

neffert mmedfua knehcdä shcänol esuapet rowedoc nhuht

Alles klar? Hast du die Nachricht bereits entschlüsselt? Wenn nicht, dann benutze diese Hilfe:

treffen aufdemm ...

Ziel dieser Aufgabe ist es, das hier benutzte Verschlüsselungsverfahren mit einer Funktion verschluesselterText zu implementieren.

Bei der Verschlüsselung gehen wir davon aus, dass eine Schlüsselzahl gegeben ist, mit der die Aufteilung des Textes beschrieben wird.

Schlüsselzahl 4:
hallowelt -> hall owel t -> llah lewo t
Schlüsselzahl 5:
hallowelt -> hallo welt -> ollah tlew

Das Verschlüsselungsverfahren führt dann zur folgenden Übergabe-Rückgabe-Situation:

Übergabe: 
- Text: "hallowelt"
- Schlüsselzahl: 4
Rückgabe: 
- verschlüsselter Text: "llah lewo t"

(a) Ergänze die bereits begonnene Modellierung der Funktion verschluesselterText.

Signatur:
verschluesselterText: ...
Beispiele:
verschluesselterText "hallowelt" 4 -> "llah lewo t"

(b) Im Rekursionsschritt wird ein Problem auf ein entsprechendes in verkleinerter Form zurückgeführt. Im vorliegendes Kontext kann die Verkleinerung darin bestehen, dass ein Block mit der durch die Schlüsselzahl vorgegebenen Länge abgespalten wird. Für das Abspalten eines Anfangsblocks aus einer Zeichenkette kannst du die vordefinierten Funktionen String.left und String.dropLeft verwenden.

Ein Rekursionsschritt muss korrekt in dem Sinne sein, dass der Ausdruck nach dem Rekursionsschritt denselben Wert wie der Ausdruck vor dem Rekursionsschritt hat. Ergänze den noch fehlenden Teil im Rekursionsschritt.

Rekursionsschritt (Beispiel):

verschluesselterText "hallowelt" 4 -> ... (verschluesselterText "owelt" 4)

[1]

Rekursionsschritt (allgemein):

Falls die Länge von text ...
verschluesselterText text schluesselzahl -> ... (verschluesselterText (String.dropLeft schluesselzahl text) schluesselzahl)

[2]

(c) Im Rekursionsanfang wird ein Problem direkt gelöst. Im vorliegendes Kontext kann das durch folgende Reduktionsregel beschrieben werden. Es fehlt aber noch die Bedingung für den Rekursionsanfang. Ergänze diese Bedingung.

Falls die Länge von text ...
verschluesselterText text schluesselzahl -> String.reverse text

(d) Entwickle aus den Reduktionsregeln eine Funktionsdefinition für die Funktion verschluesselterText.

Aufgabe 3 (Überlappung von Zeichenketten - für Experten)

Wir betrachten ein Problem bei der DNA-Rekonstruktion. Gegeben sind Bruchstücke einer DNA, die zusammengesetzt werden sollen. Solche Bruchstücke kann man mit Hilfe von Zeichenketten darstellen, wie z.B. accgttaaagcaaagatta und aagattattgaaccgtt. Die Buchstaben a, t, g, c stehen hierbei für die Bausteine einer DNA: Adenin (a), Thymin (t), Guanin (g) und Cytosin (c).

Beim Zusammensetzen geht es u.a. darum, eine möglichst lange Überlappung bei zwei gegebenen Bruchstücken zu bestimmen.

accgttaaagcaaagatta
            aagattattgaaccgtt

Wir betrachten folgende Übergabe-Rückgabe-Situation:

Übergabe: 
- Text1: "accgttaaagcaaagatta"
- Text2: "aagattattgaaccgtt"
Rückgabe: 
- Überlappung: "aagatta"

Passend hierzu modellieren wir die Funktion ueberlappung.

Signatur:
ueberlappung: String -> String -> String
Beispiele:
ueberlappung "accgttaaagcaaagatta" "aagattattgaaccgtt" -> "aagatta"

Entwicke selbstständig eine Funktionsdefinition für die Funktion ueberlappung. Beginne damit, rekursive Reduktionsregeln zu entwickeln. Bemutze bei der Implementierung geeignete vordefinnierte Funktion zur Verarbeitung von Zeichenketten (siehe Elm - String).