PRG-2

PRG-2 Homepage


Bonuspunkte-Rechner Blatt 2 Blatt 4 Blatt 5 Blatt 6 Blatt 10 Blatt 11 Blatt 12


Blatt 2

Lösung zu Aufgabe 3c (verzögerte Reihenfolge):

fun (2*18) (2*2)
-D-> if (2*18)-(2*2) <= 30 then (2*2)*2 else (2*18)+(fun ((2*18)-5) ((2*2)+5))
-A-> if 36-(2*2) <= 30 then (2*2)*2 else 36+(fun (36-5) ((2*2)+5))
-A-> if 36-4 <= 30 then 4*2 else 36+(fun (36-5) (4+5))
-A-> if 32 <= 30 then 4*2 else 36+(fun (36-5) (4+5))
-A-> if False then 4*2 else 36+(fun (36-5) (4+5))
-I-> 36 + (fun (36-5) (4+5))
-D-> 36 + (if (36-5)-(4+5) <= 30 then (4+5)*2 else (36-5)+(fun ((36-5)-5) ((4+5)+5)))
-A-> 36 + (if 31-(4+5) <= 30 then (4+5)*2 else 31+(fun (31-5) ((4+5)+5)))
-A-> 36 + (if 31-9 <= 30 then 9*2 else 31+(fun (31-5) (9+5)))
-A-> 36 + (if 22 <= 30 then 9*2 else 31+(fun (31-5) (9+5)))
-A-> 36 + (if True then 9*2 else 31+(fun (31-5) (9+5)))
-I-> 36 + (9*2)
-A-> 36 + 18
-A-> 54


Blatt 4

Lösung zu Aufgabe 3c (faire List Comprehension):

[(a,b) | z <- [1..], a <- [3*x | x <- [1..z]], b <- [y^2 | y <- [1..z]], a+b==z]

Hinweis zu List-Comprehensions:

Auf der PRG-2 Homepage findet ihr einen Link zum List-Comprehension-Online-Tool. Aufgabe 8 hat keine Lösung, deshalb bietet es sich an, hier ein kleines Musterbeispiel für geschachtelte Listen zu machen. List-Comprehensions auf verschachtelte Listen anzuwenden ist sehr tricky! Nach langem Tüfteln habe ich es schließlich so gemacht, dass ich mir eine "normale" Funktion überlegt habe, und (anhand von Beispiel 2.2.6, Skript1&2, Seite 63) Schritt für Schritt jede Funktionalität in die List-Comprehension eingefügt habe.

  1. Zuerst habe ich die gegebene Liste in eine List-Comprehension umgewandelt:
    [xs | xs <- [[[1,2],[3],[5,6,7]],[[8],[9,10]],[[11],[12,13],[14]]] ]
    Ergebnis: [[[1,2],[3],[5,6,7]],[[8],[9,10]],[[11],[12,13],[14]]] (unverändert)
  2. Auf die äußerste Liste habe ich das concat aus dem Beispiel angewendet:
    [ [y | x <- xs, y <- x] | xs <- [[[1,2],[3],[5,6,7]],[[8],[9,10]],[[11],[12,13],[14]]] ]
    Ergebnis: [[1,2,3,5,6,7],[8,9,10],[11,12,13,14]]
  3. Als nächstes müssen wir ungerade Elemente herausfiltern, deshalb müssen wir auf die Elemente der äußeren Liste zugreifen, also neue äußere List-Comprehension:
    [ zs | zs <- [ [y | x <- xs, y <- x] | xs <- [[[1,2],[3],[5,6,7]],[[8],[9,10]],[[11],[12,13],[14]]] ] ]
    Ergebnis: [[1,2,3,5,6,7],[8,9,10],[11,12,13,14]] (unverändert)
  4. Jetzt den Filter umsetzen, wie im Beispiel:
    [ [ z | z <- zs, even z] | zs <- [ [y | x <- xs, y <- x] | xs <- [[[1,2],[3],[5,6,7]],[[8],[9,10]],[[11],[12,13],[14]]] ] ]
    Ergebnis: [[2,6],[8,10],[12,14]]
  5. Als letztes die Halbierung umsetzen:
    [ [ div z 2 | z <- zs, even z] | zs <- [ [y | x <- xs, y <- x] | xs <- [[[1,2],[3],[5,6,7]],[[8],[9,10]],[[11],[12,13],[14]]] ] ]
    Ergebnis: [[1,3],[4,5],[6,7]]


Blatt 5

Tipps zu Aufgabe 3: Folien 3A ab Folie 17 (bzw. 39 von 106)

Kurz zum Verständnis anhand der 3a:
Gesucht ist der Typ des Ausdrucks map fst. map mit dem Typ (a -> b) -> [a] -> [b] ist eine Funktion, die als erstes Argument eine Funktion mit dem Typ a -> b erwartet und als zweites eine Liste mit Elementen vom Typ a, also [a]. Bei diesem Ausdruck greift die Anwendungsregel, denn map wird auf das erste Argument fst angewendet, als Ergebnis hat die Funktion also nur noch ein Argument, auf das sie angewendet wird, und zwar die Liste mit dem Typ [a]. Der Rückgabetyp bleibt eine Liste des Typs b, also [b].
Um den Typ zu berechnen gibt es nun zwei Schritte:
1. Den Ausdruck in die Anwendungsregel einsetzen (von unten nach oben).

s :: σ -> τ, t :: ρ und γ(σ) = γ(ρ)
(s t) :: γ(τ)

Für die 3a setzt ihr beispielsweise für s genau den Typ von map ein und für t den Typ von fst. Für τ setzt ihr den Typ [a] -> [b] ein, was den Typ der resultierenden Funktion darstellt. Bzw. nachdem map auf eine Funktion angewendet wurde, hat die resultierende Funktion den Typ [a] -> [b], nimmt also als Argument nur noch eine Liste mit Elementen des Typs a an und hat als Rückgabetyp eine Liste des Typs b.
2. Unifizieren (das heißt striktes Anwenden der Regeln für die Unifikation)

Hier ein Beispiel für den Ausdruck (map id), wobei map :: (a -> b) -> [a] -> [b] und id :: k -> k
Einsetzen in Anwendungsregel (von unten nach oben):

map :: (a -> b) -> [a] -> [b], id :: k -> k und γ(a -> b) = γ(k -> k)
(map id) :: γ([a] -> [b])

Unifizieren (Regeln genau einhalten):

a -> b = k -> k
a = k, b = k (Dekomposition)
a -> k b = k (Ersetzung)
a -> k, b -> k (Ersetzung)

Typsubstitution angeben: γ = {a -> k, b -> k}
Typ angeben: map id :: [k] -> [k]

Kleiner Hinweis zu den Unifikations-Regeln:

Ein (polymorpher) Typ kann Folgendes sein:
Basistyp (Int, Float, ...), ein Typ, eine Typvariable, ein Typkonstruktor (so etwas wie [a] oder Baum a) oder ein n-stelliger Typ (also sowas Typ1 -> Typ2 -> Typ1)
Die Unifikationsregeln beziehen sich auf (allgemeine) Typen wie τ und Typvariablen wie a.


Blatt 6

Tipps zu Aufgabe 1c:

Hier geht es darum, Terminalsymbole zu identifizieren. Bei TokenVar handelt es sich um ZeichenKETTEN aus Buchstaben beliebiger Länge. Um TokenVar's zu verarbeiten, bieten sich die Funktionen span und isAlpha (Data.Char) an:
Data.Char> span isAlpha "ab1c2"
("ab", "1c2")

Tipps zu Aufgabe 1d:

Hier geht es darum, die Parserkombinatoren zu verwenden, um den Tokenstrom auf syntaktische Korrektheit entsprechend der Grammatik der Sprache L zu überprüfen. Schaut euch dazu die Funktionsweise der Parserkombinatoren aus der Vorlesung an (CombParser.hs: <*>, <*, *>, <|>, <!>, <@) und das Beispielprogramm. Arbeitet dann einfach die Nicht-Terminale ab und haltet euch an das Beispiel für FAnd, das ich an die Tafel geschrieben hatte:

parseF =
  (symbol TokenAnd *> symbol (TokenSymbol '{') *>
    parse FS <*
      ... ( ... '}')) <@ (\x -> FAnd x)
  <|>
  ... (Entsprechung für FOr)
  ...
parseFS =
  ...

Für TokenVar und TokenVal definiert ihr am besten eigene kleine Parser. Und achtet außerdem auf alle Terminalsymbole in den Definitionen der Nichtterminale!

Lösung zu Aufgabe 1d (Parser):

parseF :: Parser Token Formula
parseF =
   (symbol TokenAnd *> symbol (TokenSymbol '{') *> parseFS <* symbol (TokenSymbol '}')) <@ (\x -> FAnd x)
   <|>
   (symbol TokenOr *> symbol (TokenSymbol '{') *> parseFS <* symbol (TokenSymbol '}')) <@ (\x -> FOr x)
   <|>
   parseA

parseFS =
   parseF <@ (\x -> [x])
   <|>
   (parseF <*> (symbol (TokenSymbol ',')) *> parseFS) <@ (\(f,fs) -> f:fs)

parseA =
   parseVar
   <|>
   (symbol (TokenSymbol '(') *> (parseA <*> symbol TokenAnd *> parseA) <* symbol (TokenSymbol ')') <@ (\(a,b) -> And a b))
   <|>
   (symbol (TokenSymbol '(') *> (parseA <*> symbol TokenOr *> parseA) <* symbol (TokenSymbol ')') <@ (\(a,b) -> Or a b))
   <|>
   (symbol (TokenSymbol '(') *> (symbol TokenNeg *> parseA) <* symbol (TokenSymbol ')') <@ (\x -> Neg x))
   <|>
   (symbol (TokenSymbol '(') *> (parseA <*> symbol TokenImp *> parseA) <* symbol (TokenSymbol ')') <@ (\(a,b) -> Imp a b))
   <|>
   (symbol (TokenSymbol '(') *> (parseA <*> symbol TokenBiimp *> parseA) <* symbol (TokenSymbol ')') <@ (\(a,b) -> Biimp a b))
   <|>
   parseVal

parseVar = satisfy isVar <@ (\(TokenVar s) -> Var s)
parseVal = satisfy isVal <@ (\(TokenVal s) -> Val s)

isVar (TokenVar _) = True
isVar _ = False

isVal (TokenVal _) = True
isVal _ = False


Blatt 10

ML zur Aufgabe 3

3b)

select l.id, l.hoehe_ueber_nn as Lagerhöhe, b.hoehe_ueber_nn as Berghöhe
from lager l, berge b, hat h
where b.id = h.id_berge and l.id = h.id_lager and l.hoehe_ueber_nn > b.hoehe_ueber_nn;

3c)

select g.id as Gefäß, f.fundzeitpunkt as Fundzeitpunkt_Gefäß, m.id as Münze, f2.fundzeitpunkt as Fundzeitpunkt_Münze, m.praegeherr as Prägeherr, i.lage as Lage
from funde f, funde f2, muenzen m, gefaesse g, gefunden_in i
where m.id = f2.id and g.id = f.id and m.id = i.id_muenze and g.id = i.id_gefaess
order by g.id, m.praegeherr;


Blatt 11

Hinweis zu Aufgabe 3: Video anschauen - V12, 1h52min

Kleine Zusammenfassung (ohne Garantie):

  1. Attribute, die auf beiden Seiten eines Pfeiles vorkommen, auf der rechten Seite des Pfeiles wegdenken.
  2. Unter Beachtung von 1. alle Attribute herausschreiben, die insgesamt auf der rechten Seite der Pfeile nicht vorkommen.
  3. a) Bei 2. keine Attribute gefunden: Kombinatorisch herausfinden, durch welche Attribute ihr die Relation (schrittweise) erschließen könnt.
    b) Bei 2. Attribute gefunden: diese sind Teil jedes Schlüssels.
  4. Oberschlüssel sind keine Schlüssel, also ggf. wegstreichen.

Blatt 12

Hinweis zu Aufgabe 1: Video anschauen - V13, 0h27min

Um zu prüfen, ob sich ein gegebenes Relationenschema R in 2. Normalform (2.NF) befindet, müsst ihr Folgendes machen:

  1. Ist R in 1.NF? Wenn R nicht in 1.NF ist, kann R auch nicht in 2.NF sein.
  2. Alle Schlüsselkandidaten von R herausfinden (bereits bekannt aus Blatt 11).
  3. Alle nicht primen Attribute herausfinden.
  4. Für jedes nicht prime Attribut prüfen, ob es von allen Schlüsselkandidaten von R voll funktional abhängig ist. Ist dies nicht der Fall, ist R nicht in 2.NF.

Beispiel aus VL:

  1. ist gegeben
  2. A und B nicht rechts von den Pfeilen -> AB muss in jedem Schlüssel vorkommen. Aus AB ergibt sich R und es gibt auch keine weiteren Schlüssel.
  3. nicht prim sind entsprechend dem einzigen Schlüsselkandidaten AB: C und D
  4. D ist nicht von AB sondern nur von B abhängig und somit ist D nicht voll funktional abhängig ⇒ R ist nicht in 2.NF !

Alle Angaben ohne Gewähr.


Zum Seitenanfang