CS代考计算机代写 Prof. Dr. T. Grust, B. Dietrich, C. Duta, D. Hirn WS 2020/2021

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 10 (27.01.2021)
Abgabe bis: Mittwoch, 3.2.2021, 14:00 Uhr
v Relevante Videos: bis einschließlich Informatik 1 – Chapter 10 – Video #48. ® https://tinyurl.com/Informatik1-WS2021
Sprachebene ”Die Macht der Abstraktion“
Aufgabe 1: [20 Punkte]
Stellen wir uns ein Szenario vor, in dem sehr viele kurze Listen nacheinander u ̈bermittelt werden und
jeweils einzeln am Ende einer Ergebnisliste eingefu ̈gt werden mu ̈ssen:
(append (append … (append (append (list 1) (list 2))
(list 3))
…
(list 9999)) (list 10000))
Beachte, dass diese Kolonne von append-Operationen links-tief geklammert ist.
Wenn wir uns die Implementation der Listenfunktion append vergegenwa ̈rtigen, ko ̈nnen wir erahnen, dass das obige ein sehr aufwa ̈ndiges Unterfangen werden kann: Fu ̈r jeden Aufruf von append wird die bisherige Liste durchlaufen, die leere Liste am Ende gesucht und an ihrer Stelle das neue Element eingeha ̈ngt. Es ergibt sich eine Laufzeit, die quadratisch (nicht linear) mit der La ̈nge der Resultatliste anwa ̈chst. Die Ursache dieser Ineffizienz wurde in Chapter 09 im Video #042 und auf Slide 17 thematisiert (siehe die Diskussion der Funktion backwards). Dem Effekt kann mit einer alternativen Repra ̈sentation von sogenannten unvollst ̈andigen Listen durch Funktionen begegnet werden.
Eine unvollst ̈andige Liste ist eine Funktion der Signatur ((list-of t) -> (list-of t)), die den An- fang einer Liste repra ̈sentiert (bzw. beinhaltet) und als Argument eine weitere, regula ̈re Liste (Signa- tur (list-of t)) erwartet, mit der der Listenanfang zu einer Ergebnisliste (Signatur (list-of t)) ver- vollsta ̈ndigt wird.
(a) Definiere zuna ̈chst die parametrische Signatur (incomplete-list-of t) der unvollst ̈andigen Listen mit Elementen der Signatur t durch ((list-of t) -> (list-of t)).
(b) Definiere nun eine Funktion ho ̈herer Ordnung list->incomplete mit der Signatur (: list->incomplete ((list-of %a) -> (incomplete-list-of %a)))
die eine gegebene regula ̈re Liste xs in eine unvollsta ̈ndige Liste l umwandelt. Das Ergebnis von list->incomplete ist eine Funktion l, die als Argument eine weitere Liste ys erwartet und diese am Ende der Liste xs anha ̈ngt, um diese zu vervollsta ̈ndigen.
(c) Definiere eine Funktion ho ̈herer Ordnung
(: incomplete-append ((incomplete-list-of %a) (incomplete-list-of %a) -> (incomplete-list-of %a)))
die zwei unvollsta ̈ndige Listen l1 und l2 zu einer neuen unvollsta ̈ndigen Liste verknu ̈pft. Die resultie- rende unvollsta ̈ndige Liste nutzt ein gegebenes Listenende zuna ̈chst, um l2 zu vervollsta ̈ndigen, und verwendet das Ergebnis dann zur Vervollsta ̈ndigung von l1.
(d) Schreibe zuletzt eine Funktion
(: incomplete->list ((incomplete-list-of %a) -> (list-of %a)))
die eine unvollst ̈andige Liste in eine regula ̈re Liste umwandelt, indem die leere Liste zur Vervollsta ̈ndi- gung genutzt wird.

(e) Nun man kann mit den unvollsta ̈ndigen Listen genauso programmieren, wie mit den klassischen Listen. Man muss nur fu ̈r die Konversion von klassischen in unvollsta ̈ndige Listen und zuru ̈ck sorgen. Es gilt etwa:
(incomplete->list (incomplete-append (list->incomplete (list 2 1)) (list->incomplete (list 8 7))))
􏰀 (list 2 1 8 7)
Nutze check-property, um das erwartete Zusammenspiel der drei Funktionen zu testen.
(f) Vergleiche nun die Laufzeiten von (sehr) vielen append-Operationen auf den klassischen und den neu- en unvollsta ̈ndigen Listen. Dazu findest du vorgegebene Funktionen in der Datei list-benchmark.rkt.
i. Gib die Laufzeiten fu ̈r test-append und test-incomplete-append (wie in der REPL ausgege- ben) an.
Wichtig: Um mit dem Benchmark aussagekra ̈ftige Zeiten messen zu ko ̈nnen, muss die Signa- turu ̈berpru ̈fung deaktiviert werden (in der Menu ̈leiste: Racket 􏰁→ Signaturu ̈berpru ̈fung deakti- vieren). Anderenfalls wird der Aufwand der eigentlichen Berechnung von der zur Laufzeit sehr teuren U ̈berpru ̈fung der Signaturen u ̈berlagert. Vergiss nicht, die Signaturu ̈berpru ̈fung anschlie- ßend wieder zu aktivieren.
ii. Betrachte die Ausdru ̈cke (append (append xs ys) zs) und (append xs (append ys zs)). Sind die Ausdru ̈cke a ̈quivalent? Wenn du die Wahl ha ̈ttest, welche Variante wu ̈rdest du einsetzen und wieso?
iii. Ersetze in dem folgenden links-tief geklammerten Ausdruck zuna ̈chst die Funktionen incomplete->list, incomplete-append und list->incomplete durch ihre Definitionen, so dass nur die Funktion append, lambda-Ausdru ̈cke und Listen-Literale verbleiben.
Fu ̈hre dann (wiederholt) die Reduktionsregel apply λ durch, bis du einen Ausdruck erha ̈ltst der keine lambdas mehr beinhaltet. Begru ̈nde mit dem Resultat, warum unvollst ̈andige Listen so effizient sind.
(incomplete ->list
(incomplete-append (incomplete-append (list->incomplete xs)
(list->incomplete ys)) (list->incomplete zs)))
Aufgabe 2: [20 Punkte]
Die Kreiszahl π la ̈sst sich durch die folgende Gleichung anna ̈hern:
􏰆􏰅􏰅 􏰃∞ 1
π = 􏰄6 ·
Der Ausdruck 􏰂∞ 1 stellt dabei eine (unendliche) Reihe dar. Ihr n-tes Glied (d.h. die n-te Partialsumme)
i2
s3 = 1 + 1 + 1 ≈ 1.36 49
s4 = 1 + 1 + 1 + 1 ≈ 1.42 4 9 16
s5 =···
In dieser Aufgabe gilt es, mithilfe von Streams die obige Anna ̈herung von π zu implementieren.
Hinweis: Die im Forum bereitgestellte Datei streams.rkt entha ̈lt die fu ̈r die Arbeit mit Streams no ̈tigen Definitionen promise, force und stream-of sowie den parametrischen Record cons. Zusa ̈tzlich sind darin die aus der Vorlesung bekannten Funktionen from und stream-take vorgegeben.
i=1
i=1 i2 n 1 wird berechnet als sn = 􏰂i=1 i2 .
Die ersten Glieder nehmen also die folgenden Werte an: s1 = 1
s2 = 1 + 1 = 1.25 4

(a) Schreibe zuna ̈chst eine Funktion
(: stream-drop (natural (stream-of %a)-> (stream-of %a))),
die, gegeben eine natu ̈rliche Zahl n, die ersten n Elemente eines Eingabestreams verwirft. Beispiel: (stream -take 3 (stream -drop 5 (from 1))) 􏰀 (list 6 7 8)
(b) Schreibe eine Funktion
(: stream-map ((%a -> %b)(stream-of %a)-> (stream-of %b))),
die eine Funktion f und einen Stream s akzeptiert und den Stream zuru ̈ckliefert, der aus der Anwen- dung von f auf die Elemente von s entsteht.
Beispiel:
(stream-take 3 (stream-map (lambda (x) (* x x)) (from 1))) 􏰀 (list 1 4 9)
(c) Verwende steam-map und die aus der Vorlesung bekannte Funktion from, um eine Funktion (: pi-series (stream-of real))
zu formulieren, die einen Stream der Zahlen 1 fu ̈r i = {1, 2, . . . , ∞} erzeugt. i2
Beispiel:
(stream-take 3 pi-series) 􏰀 (list 1 1/4 1/9)
(d) Schreibe eine Funktion
(: stream-sum ((stream-of number) -> (stream-of number)))
die einen Stream der laufenden Summe u ̈ber die Elemente des u ̈bergebenen Stream s erzeugt. Wenn s der Stream x1,x2,x3,… ist, dann ist (stream-sum s) der Stream x1,x1 +x2,x1 +x2 +x3,…. Mathematisch ausgedru ̈ckt: Fasst man den Eingabestream als Folge auf, berechnet stream-sum einen Stream der Partialsummen der entsprechenden Reihe.
Beispiele:
(stream -take 4 (stream -sum (from 1))) 􏰀 (list 1 3 6 10)
(stream-take 3 (stream-sum pi-series)) 􏰀 (list 1 5/4 49/36)
(e) [2 Punkte] Verwende nun pi-series, stream-sum und stream-drop, um eine Funktion (: approx-pi (natural -> real))
mit einem Parameter n zu definieren, die mittels der n-ten Partialsumme der obigen Reihe eine Na ̈herung fu ̈r π berechnet.
Beispiele:
(approx -pi (approx -pi (approx -pi … (approx -pi
1) 􏰀 2.449 2) 􏰀 2.739 3) 􏰀 2.858
1000) 􏰀 3.141