Prof. Dr. T. Grust, B. Dietrich, C. Duta, D. Hirn
WS 2020/2021
Informatik 1
Forum: https://forum-db.informatik.uni-tuebingen.de/c/ws2021-info1 U ̈bungsblatt 14 (24.02.2021)
Abgabe bis: Mittwoch, 03.03.2021, 14:00 Uhr
Sprachebene ”Die Macht der Abstraktion“
Aufgabe 1: [10 Punkte]
Mittels der Tupperschen Ungleichung (Tupper’s Formula) kann man ein Gefu ̈hl dafu ̈r entwickeln, wieviel
Information in einer (sehr!) großen natu ̈rlichen Zahl k steckt. Wir visualisieren diese Ungleichung hier.
Seien (x,y) zwei natu ̈rliche Zahlen, dann berechnet die Tuppersche Ungleichung daraus einen Booleschen Wert (hier bezeichnet ⌊x⌋ die bekannte Funktion (floor x), eine Implementation von mod stellen wir euch in File tupper.rkt zur Verfu ̈gung):
1<mody2−17⌊x⌋−mod(⌊y⌋,17),2 . 2 17
Wenn wir x ∈ [0, 105] und y ∈ [k, k + 16] wa ̈hlen, dann definiert die Ungleichung ein Bild aus 106 × 17 Pixeln (wenn die Ungleichung #t liefert, ist das Pixel an der Koordinate (x,y) gesetzt). Diese Pixelbilder sollt ihr zeichnen (dazu beno ̈tigt ihr das Teachpack image2).1
Wichtig: Verwendet in den Teilaufgaben (c) und (d) keine explizite Rekursion, sondern nur eingebaute Listenverarbeitungsfunktionen wie map und fold, sowie die in tupper.rkt vorgegebene Funktion from-to.
(a) Definiert zuna ̈chst eine Funktion
(: tupper -formula (natural natural -> boolean))
die fu ̈r zwei gegebene natu ̈rliche Zahlen x und y das Ergebnis der Tupperschen Ungleichung (Signa- tur boolean) zuru ̈ckgibt.
(b) Konstruiert eine Funktion
(: pixel (boolean -> image))
die einen Booleschen Wert in einen schwarzen (#t) oder weissen Pixel (#f) abbildet. Nutzt die Funk- tion (rectangle 1 1 “solid” …) aus Teachpack image2, um den Pixel zu erzeugen.
(c) Definiert die Funktion
(: tupper-pixels (natural -> list-of (list-of image)))
so dass (tupper-pixels k) die Tuppersche Ungleichung fu ̈r alle Punkte (x,y) im Bereich von x ∈ [0, 105] und y ∈ [k, k + 16] auswertet und die resultierenden Booleschen Werte in schwar- ze/weisse Pixel u ̈bersetzt. Das Ergebnis ist eine Liste von 17 Zeilen (y-Intervall), die jeweils als Listen mit je 106 Pixeln (x-Intervall) dargestellt sind.
(d) Definiert zuletzt die Funktion
(: tupper -image (natural -> image))
so dass (tupper-image k) die von tupper-pixels gelieferten Pixellisten zu einem Bild mittels der Funktionen above und beside aus dem Teachpack image2 zusammenfu ̈gt. tupper-image kann die Funktion (scale s img) aus dem Teachpack nutzen, um das Pixelbild bzgl. Faktor s auf eine sinnvolle Gro ̈ße zu skalieren.
1Dokumentation zum Teachpack image2 findet ihr unter https://docs.racket-lang.org/teachpack/2htdpimage.html.
Das File tupper.rkt entha ̈lt beispielhafte Werte fu ̈r die große natu ̈rliche Zahl k. Fu ̈r die dort vorgegebene Zahl k1 ≡ 96093⟨· · · 534 weitere Ziffern · · · ⟩04719 ergibt sich u ̈brigens das Bild
Ihr ko ̈nnt euch auf https://keelyhill.github.io/tuppers-formula/ in einem web-basierten Pixeledi- tor eure eigenen Bilder und deren k-Werte konstruieren.
Aufgabe 2: [4 Punkte]
Listen ko ̈nnen als Repra ̈sentation von Mengen verstanden werden. Wir gehen davon aus, dass eine solche
Liste keine Duplikate entha ̈lt.
Die Funktion P(S) berechnet die Menge aller Untermengen einer Menge S. P(S) entha ̈lt dabei immer die
leere Menge ∅ sowie S selbst:
P ({1,2,3}) = {1,2,3}, {1,2}, {2,3}, {1,3}, {1}, {3}, {2}, ∅
Schreibt eine Funktion (: subsets ((list-of %a)-> (list-of (list-of %a)))), die die Menge aller Un- termengen einer Menge mit beliebigen Elementen berechnet.
Hinweis: Um die Teilmengen der Liste (make-pair x xs) zu berechnen, sammelt alle Teilmengen von xs zweimal auf:
(a) einmal unvera ̈ndert und
(b) einmal, nachdem in jede Teilmenge das Element x eingefu ̈gt wurde.
Da wir Mengen repra ̈sentieren, ist die Reihenfolge der Teilmengen und der Elemente innerhalb der Teilmen- gen im Ergebnis von subsets nicht relevant. Geht zudem davon aus, dass die Eingabeliste duplikatfrei ist.
Aufgabe 3: [14 Punkte]
Prof. Grust liebt Sudokus in allen Varianten. In der Variante Killer Sudoku gibt es im Sudoku-Grid neben den u ̈blichen 9 Zeilen, Spalten und 3 × 3-Boxen auch die sog. Cages: . In diesem Cage
der Gro ̈ße 3 mu ̈ssen drei unterschiedliche Ziffern (1, . . . ,9) eingetragen werden, deren Summe 22 betra ̈gt. Gute Sudoku-Spieler stellen sich dann Fragen wie: “Welche Kombinationen aus drei Ziffern ergeben 22?” oder “Ist in allen m ̈oglichen Kombinationen eine 9 enthalten?”. Wirklich gute Spieler kennen sa ̈mtliche Kombinationen aus n Ziffern, die eine Summe s ergeben, auswendig (im Beispiel: n = 3, s = 22).2 Mittelma ̈ssige Spieler beno ̈tigen dazu eine tabellarische Aufstellung. Baut eine solche Tabelle fu ̈r Prof. Grust und geht dazu wie folgt vor:
(a) Wir ku ̈mmern uns zuna ̈chst um die Ziffernkombinationen selbst:
i. Definiert eine Signatur digit, die nur die gu ̈ltigen Sudoku-Ziffern 1, 2, . . . , 9 akzeptiert.
ii. Schreibt eine Funktion (: cage-sums (natural -> (list-of (list-of digit))), so dass der Aufruf (cage-sums s) die Menge aller mo ̈glichen duplikatfreien Ziffernkombinationen (jeweils
dargestellt als (list-of digit)) mit Summe s berechnet. Hierbei gilt s ∈ [1, 45]. Beispiel:
(cage-sums 7) (list (list 7) (list 3 4) (list 2 5) (list 1 6) (list 1 2 4)) Die Elementreihenfolge ist beliebig.
Hinweis: Nutzt die Funktion subsets aus Aufgabe 2 und Listenfunktionen (map, filter, . . . ) anstatt explizite Rekursion einzusetzen. (So spa ̈t in der Vorlesung ist das eine Stilfrage, die in die Bepunktung eingeht.)
(b) Jetzt geht es an die tabellarische Ausgabe. Die Tabelle wird alle Ziffernkombinationen einer gegebenen Gro ̈ße n enthalten und zeigen, wie diese jeweils die Summen s = 1, 2, . . . , 45 ergeben. Abbildung 1 zeigt die Ausgabe in der REPL fu ̈r n = 3. Die Ausgabe hat immer 2 + 45 Zeilen (Header + Zeilen mit Ziffernkombinationen). Geht wie folgt vor:
2Wer sich fu ̈r Sudokus in irgendeiner Form interessiert, der/dem kann nur der YouTube-Channel Cracking the Cryptic ans Herz gelegt werden. Im folgenden Videosegment seht ihr, wie Simon Anthony—vormals Mitglied des britischen Sudoku-Nationalteams— einen (virtuellen) 22-Cage der Gro ̈ße 3 fu ̈r den na ̈chsten Lo ̈sungsschritt nutzt: https://youtu.be/11pjL7saUno?t=2420.
22
Cage sum ——– 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
[… die Zeilen 27 bis 43 enthalten keine Ziffernkombinationen …] 44
45
Abbildung 1: Tabelle mit den Cages der Gro ̈ße n = 3 und ihre Summen. 124 ist die Ausgabe fu ̈r die Ziffern- kombination (list 1 2 4). Ein Cage der Gro ̈ße 3 kann bspw. nicht die Summe 4 ergeben (leere Zeile 4).
i. Konstruiert zuna ̈chst die Funktion (: digits->string ((list-of digit) -> string)), die eine Ziffernkombination kompakt als String repra ̈sentiert. Dabei kann die eingebaute Funktion number->string hilfreich sein.
Beispiel:
(digits->string (list 1 2 4)) “124”
ii. Baut eine Funktion (: intersperse (%a (list-of %a) -> (list-of %a)), die ein Element
zwischen alle Elemente einer Liste platziert. Beispiele:
(intersperse “, ” (list “S” “K” “I”)) (list “S” “, ” “K” “, ” “I”) (intersperse 1 (list 42)) (list 42)
(intersperse #t empty) empty
iii. Baut eine Funktion (: row (natural natural -> string)), die eine Tabellenzeile der Ausga- be erzeugt.
Beispiel:
(row 3 9) “9\t\t234, 135, 126”
erzeugt die Zeile der Ziffernkombinationen der Gro ̈ße n = 3 mit Summe s = 9 in der Ausgabe in
Abbildung 1 (“\t” steht fu ̈r einen Tabulator, siehe die Hinweise unten).
iv. Baut schliesslich die Funktion (: table (natural -> string)), so dass (table n) die Aus- gabe der Cage-Tabelle fu ̈r alle Ziffernkombinationen der Gro ̈ße n berechnet. Abbildung 1 wurde
mittels
in der REPL erzeugt.
Hinweise:
(write-string (table 3))
Possible digit sets ——————-
123
124
134, 125
234, 135, 126
235, 145, 136, 127 245, 236, 146, 137, 345, 246, 237, 156, 346, 256, 247, 238, 356, 347, 257, 248, 456, 357, 348, 267, 457, 367, 358, 349, 467, 458, 368, 359, 567, 468, 459, 378, 568, 478, 469, 379, 578, 569, 479, 389 678, 579, 489
679, 589
689
789
128
147, 138, 129
157, 148, 139
239, 167, 158, 149 258, 249, 168, 159 268, 259, 178, 169 278, 269, 179
369, 279, 189
289
• Die Funktion strings-list->string konkateniert eine Liste von Strings zu einem String.
• Trennt die Zeilen der Tabelle mit einem Newline (String “\n”) und trennt die Spalten der Tabelle mit einem horizontalen Tabulator (String “\t”). Letzteres bewahrt euch davor, fu ̈r die
formatierte Ausgabe Spaltenbreiten berechnen/ausgleichen zu mu ̈ssen.
Aufgabe 4: [5 Punkte]
Die Operation (: delay (%a -> (promise %a))) verzo ̈gert die Auswertung ihres Argumentes und er- zeugt stattdessen ein Versprechen (Signatur promise), das erst spa ̈ter—bei eventuellem Bedarf—mittels (: force ((promise %a) -> %a)) eingelo ̈st werden kann (vgl. Chapter 13 Folien 22 und 23).
Dabei ist es bedeutend, dass delay als syntaktischer Zucker und nicht als regula ̈re Funktion definiert ist. k
Zeige dies mit Hilfe der Reduktionsregeln · fu ̈r Scheme. Wichtig: Halte dich dabei streng an die Notation aus der Vorlesung zu Chapter 3 Folien 3ff. und lasse keine Schritte aus!
(a) Zeige zuna ̈chst, dass wa ̈hrend der Reduktion von (delay (+ 40 2)) das Argument (+ 40 2) nicht ausgewertet wird, sofern delay als syntaktischer Zucker definiert ist:
(delay e) ≡ (lambda () e)
(b) Zeige dann, dass wa ̈hrend der Reduktion von (delay (+ 40 2)) das Argument wider Erwarten doch
ausgewertet wird, sofern wir delay als regula ̈re Funktion definieren:
(define delay ; /!\ fragw ̈urdige Definition (lambda (e)
(lambda () e)))
(c) Zeige zuletzt, dass mit Hilfe von force das Versprechen (lambda () (+ 40 2)) tatsa ̈chlich zur Aus- wertung gebracht wird. Reduziere dazu den Ausdruck (force (lambda () (+ 40 2))) und nutze die bekannte Definition von force:
(define force (lambda (p) (p)))
Aufgabe 5: [7 Punkte]
Die Folien 7 und 8 in Chapter 9 zeigen drei Konstruktionsanleitungen (: f (natural -> t)) fu ̈r Re-
kursion u ̈ber natu ̈rlichen Zahlen.
(a) Wa ̈hlt t ≡ natural und erga ̈nzt die drei Konstruktionsanleitungen zu drei Funktionen f0, f1, f2, deren Resultat jeweils angibt, wieviele rekursive Aufrufe die Funktion zur Berechnung durch- gefu ̈hrt hat.3 Damit gilt beispielsweise (f1 n) 4 fu ̈r n = 3.
Wie verha ̈lt sich die Anzahl der rekursiven Aufrufe der drei Funktionen, wenn wir n = 0, 1, 2, . . . wach- sen lassen? Das wollen wir mit zweidimensionalen Plots visualisieren. (Dazu beno ̈tigt ihr das Teackpack image2.)
(b) Definiert dazu die Signatur (define point (signature (tuple-of real real))), die Punkte p = (x,y) in der Ebene repra ̈sentiert. Konstruiert eine Funktion
(: add-lines (image (list-of point) -> image))
so dass (add-lines img (list p1 p2 p3 … pm)) die Liste der Punkte zu einem durchgehen- den Linienzug p0—p1—p2—· · · —pm−1—pm verbindet und diesen zum bestehenden Bild img hin- zufu ̈gt. Dabei hilft euch die Funktion add-line aus dem Teachpack image2 (setzt den Parameter pen-or-color der Funktion add-line auf “black”).4
(c) Nutzt eure Funktion add-lines aus (b), um die Funktion
(: plot/xy (real real natural natural (natural -> natural) -> image))
zu konstruieren. Ein Aufruf (plot/xy sx sy s e f) geht wie folgt vor:
• Funktion f wird fu ̈r die Parameter n ∈ {s,s + 1,s + 2,…,e − 1,e} ausgewertet. Bilde daraus die Punkte pn = (n, (f n)).
• Konstruiere einen Linienzug aus den Punkten ps, ps+1, . . . , pe.
• Das Resultat ist ein Bild, das diesen Linienzug entha ̈lt, nach dem dieser in x/y-Richtung mit den
Faktoren sx/sy skaliert wurde (dabei hilft die Funktion scale/xy aus dem Teachpack image2). Beispiel: Plot fu ̈r die Funktion x2 im Wertebereich x = {1,2, . . . ,10}:
(plot/xy 5 0.5 0 10 (lambda (x) (* x x)))
(d) Nutzt plot/xy dreimal, um fu ̈r die Funktionen f0, f1 und f2 aus (a) die jeweils sehr charakteristische Entwicklung der Anzahl der rekursiven Aufrufe bei wachsendem n = 0, 1, 2, . . . zu visualisieren. Wa ̈hlt dazu die Parameter sx, sy, s, e von plot/xy jeweils geeignet.
3Funktion f0 entspricht der Konstruktionsanleitung auf Folie 7, f1 und f2 entsprechenden den beiden Konstruktionsanleitungen auf Folie 8.
4Die Dokumentation zu add-line findet ihr auf https://docs.racket-lang.org/teachpack/2htdpimage.html.