close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Aufgabenblatt Xmas (Breath-First-Traversal, kgV, Shape-Parser)

EinbettenHerunterladen
Universität Bielefeld
Technische Fakult¨
at
AG Praktische Informatik
¨
Ubung
zu den Vorlesungen Algorithmen &
Datenstrukturen
Programmieren in Haskell
Wintersemester 2014/2015
Allgemeiner Hinweis: Die Punkte die mit der L¨osung dieser Aufgaben erreicht werden k¨onnen, sind Zusatzpunkte. Die Punkte werden zu Ihren erzielten Punkten addiert,
erh¨ohen jedoch nicht die 50% H¨
urde aus der Gesamtpunktzahl.
Aufgabe Xmas.1 (6 Punkte): Implementieren Sie in Haskell eine Funktion
leavesBFT :: Tree a -> [a], die alle Bl¨atter eines Baumes als Liste zur¨
uck gibt. Die
Reihenfolge der Bl¨
atter muss sich nach der Breitensuche richten, nicht nach der Tiefensuche wie das z.B. die Funktion leaves tut. Zum Beispiel soll das Ergebnis f¨
ur folgenden
Baum "Hallo", nicht aber "oallH" lauten:
Br
Leaf
Br
Br
Nil Leaf
’H’
Br
Br
Leaf Leaf Leaf
’l’
’a’
’l’
’o’
Verwenden Sie f¨
ur Tree a die Datentypdefinition von Aufgabe 6.1
Aufgabe Xmas.2 (4 Punkte): Implementieren Sie eine Funktion
kgvL :: [Int] -> Int, die f¨
ur eine Liste von Zahlen ihr kleinestes gemeinsames Vielfaches bestimmt. Beispielsweise soll f¨
ur die Eingabe [144,160,175] der Wert 50400 als
das kleinste gemeinsame Vielfache der drei Zahlen berechnet werden. Verwenden Sie die
Primfaktorzerlegung.
Aufgabe Xmas.3 (10 Punkte): Eine RNA-Sequenz kann in verschiedene Sekund¨arstrukturen
gefaltet werden. Bei einer Faltung gehen einzelne Zeichen der Sequenz Verbindungen
miteinander ein.
Zum Beispiel kann aaaaaaacccccuuuuuuuaaaaaaaaaccccccuuuuuuu in 524721546 Sekund¨arstrukturen gefaltet werden, 2 Strukturen sind abgebildet:
1
Universität Bielefeld
Technische Fakult¨
at
AG Praktische Informatik
Die Vienna-Notation ist eine ASCII-Kodierung einer Sekund¨arstruktur. Die beiden
Strukturen sehen in Vienna-Notation so aus:
(((((((.....)))))))..(((((((......)))))))
(((((((.....)))))))......................
Die Verbindungen zwischen 2 Zeichen m¨
ussen wohlgeformt sein, d.h. f¨
ur 2 Verbindungen (i, j) und (i , j ) muss eine der folgenden Beziehungen erf¨
ullt sein:
1. i < i < j < j
2. i < i < j < j
3. i < j < i < j
4. i < j < i < j
Wobei i, j, i , j jeweils Positionen in der Eingabesequenz bezeichnen. Das heißt also, dass
¨
eine Uberkreuzung
wie i < i < j < j nicht erlaubt ist.
Um mehrere ¨
ahnliche Strukturen in Klassen einzuordnen, gibt es eine Shape-Notation.
Eine Vienna-String wird in einen Shape (Typ-5) u
uhrt, in dem die Punkte ignoriert
¨berf¨
werden und mehrfach direkte Schachtelungen ((x)) durch (x) ersetzt werden, ohne die
Wohlgeformtheit zu verletzen. Am Ende werden runde Klammern durch eckige ersetzt.
Implementieren Sie eine Funktion
vienna2shape :: String -> String
die einen Vienna-String in einen Shape umwandelt.
Beispielaufrufe:
> vienna2shape " ( ( ( ( ( ( ( . . . . . ) ) ) ) ) ) ) . . ( ( ( ( ( ( ( . . . . . . ) ) ) ) ) ) ) "
" [][] "
> vienna2shape " ( ( ( ( ( ( ( . . . . . ) ) ) ) ) ) ) . . . . . . . . . . . . . . . . . . . . . . "
" [] "
> vienna2shape " (((())(..))) "
" [[][]] "
Eine m¨
ogliche Implementation ist die Unterteilung in 3 Phasen: Zuerst wird die Eingabesequenz in eine Baum-Datenstruktur u
uhrt (Parsen), wobei jeder Knoten ein
¨berf¨
Klammerpaar repr¨
asentiert. In diesem Baum werden u
ussige Klammerpaare (rekur¨berfl¨
siv) gel¨
oscht (Konvertierung). Zum Schluss muss der Baum ausgegeben werden.
Abgabe: Mittwoch, 07.01.2015, 16:00 Uhr. Bearbeitung in 2er Gruppen (alle Namen
und Tutor auf die Abgabe schreiben).
Wir wu
¨ nschen Ihnen scho
¨ne Weihnachten und einen guten Start in
das neue Jahr 2015!
2
Document
Kategorie
Technik
Seitenansichten
11
Dateigröße
116 KB
Tags
1/--Seiten
melden