Vollbildmodus (F11) und Google Chrome empfohlen

Klicken oder Tippen Sie irgendwo, um anzufangen

Programmierung

eine Einführung in die Informatik mit Dieter Schlau

fun fortytwo (f : 'a -> ('a * bool)) (s : 'a) =
let val (n, b) = f s
in  if b then fortytwo f n
         else n
end
Kaminfeuer
Flamme
Glühbirne
Ich bin Dark Dieter
Dieter Schlau
Pergament
f n x y = x ⋅ y falls n = 0
f n x y = x falls n > 0 und y = 0
f n x y = f (n - 1) (f n x (y - 1)) ((f n x (y - 1)) + y)
Dark Dieter Rises
Aufgabe Felix Freiberger
Geschichte Yannick Forster
Musik
The Thunderstorm Karstenholymoly
They're coming... Zapac
Never Heard a Rhyme Like This Before Scott Altham
Sprecher Felix Freiberger
Web-Entwicklung Felix Freiberger
mit Dank an Gregory Stock
Bilder
Blitz bei Nacht AndreasF Kopfhörer-Logo George Shuklin
Kaminfeuer David Boozer Flamme Ryan Mahle
Lampe Pexels Pergament ArtsyBee
Dieter Schlau Joaquim Alves Gaspar
Schriftarten Jenna Sue Jenna Sue Design Co. Zombie Holocaust Sinister Fonts

Die Aufgabenstellung dieser kNobelaufgabe wird in Form eines Hörspiels bereitgestellt.

Stellen Sie sicher, dass Ihr Audio-Setup funktioniert, und dann kann es losgehen!

Alternativ können Sie sich notfalls auch die schriftliche Version anschauen.

Programmierung – eine Einführung in die Informatik mit Dieter Schlau

Teil 1


Es ist mal wieder spät geworden, und Sie sitzen mit Ihrem zukünftigen ehemaligen besten Freund Dieter Schlau abends gemütlich auf der Couch vor dem Kamin und stöbern im Programmierung-1-Buch. Während Sie über den Unterschied zwischen statischen und dynamischen Bindungen nachdenken, überkommt Sie der Schlaf...


Sie werden von einem leisen Summen geweckt.

Als Sie Ihre Augen öffnen, sehen Sie entsetzt, dass sich Dieter Schlau Ihren Laptop geschnappt hat und im Interpreter herumexperimentiert – und natürlich drückt er nur die falschen Knöpfe. Entsetzt rennen Sie zu Ihrem Laptop, doch es ist zu spät: Alle bisher deklarierten Prozeduren sind gelöscht (ja, auch Ihre geliebten Prozeduren iter, first, iterup und iterdn sind alle weg)!

Immer noch im Halbschlaf können Sie gerade noch

fun fortytwo (f : 'a -> ('a * bool)) (s : 'a) =
let val (n, b) = f s
in  if b then fortytwo f n
         else n
end

in Ihren Interpreter eingeben, bevor Dieters Aktionen das Schlüsselwort fun permanent unbenutzbar gemacht haben.

Entsetzt schauen Sie Dieter an. Doch gerade, als Sie ihn zur Rede stellen wollen, murmelt er schnell irgendetwas, was grob wie „muss​​ mal​ weg“ klingt, und rennt zur Tür. Nach nur kurzer Verfolgungsjagd geben Sie auf: Dieter ist entkommen.

Leider müssen Sie nun die folgenden Aufgaben ohne fun und ohne jegliche Hilfsprozedur außer fortytwo lösen.

Hinweis: Falls Sie das Schlüsselwort val rec kennen: Das ist leider auch nicht mehr benutzbar. Wenn Sie von diesem Schlüsselwort noch nie gehört haben, ignorieren Sie es einfach.

  1. Nachdem Sie realisiert haben, dass fortytwo nun Ihre einzige Möglichkeit ist, Rekursion zu benutzen, betrachten Sie diese Prozedur genauer. Was ist ihr Typschema? Was tut sie? Wie kann Sie Ihnen helfen, rekursive Prozeduren zu schreiben?

  2. Machen Sie sich mit fortytwo vertraut: Schreiben Sie eine Prozedur fak : int -> int, so dass fak n die Fakultät n! durch wiederholte Multiplikation berechnet. Denken Sie an obige Einschränkungen!

  3. Richten Sie sich Ihren Interpreter wieder gemütlich ein! Deklarieren Sie sich ihre Lieblingsprozeduren iter, first, iterup und iterdn erneut.

Teil 2


Hundemüde, aber auch etwas zufrieden, legen Sie Ihr Programmierung-1-Buch wieder auf den Tisch vor dem Kamin und gehen endlich ins Bett. Sie ziehen sich die Decke über den Kopf und schlafen ein.


Als Sie wieder wach werden, erkennen Sie Ihre Umgebung kaum wieder: Es ist kalt, und irgendwie flackert das Licht...

Dieter scheint zurück in Ihrem Zimmer zu sein und sitzt den Rücken zu Ihnen gewandt am Kamin. Mühsam stehen Sie auf und murmeln verschlafen: „Dieter, warum ist es so kalt? Hast du das Feuer ausgemacht?“. Statt einer Antwort steht Dieter langsam auf und wendet sich Ihnen zu. Dabei scheint es immer kälter und kälter im Zimmer zu werden. „Ich bin nicht Dieter.“, sagt Dieter, und schaut Ihnen nun direkt in die Augen. Und er scheint Recht zu haben: Die Gestalt, die dort steht, sieht zwar überraschend nach ihrem Freund Dieter Schlau aus, aber sie ist blasser, dünner und irgendwie ein wenig gruselig. „Ich bin Dark Dieter. Dein lieber Freund Dieter Schlau ist ...“, und in diesem Moment kräuseln sich die Lippen von Dark Dieter zu einem teuflischen Grinsen, „...für immer verloren.“ Sie atmen scharf ein und Ihre Knie werden plötzlich weich. „Dieter? Verloren?“, keuchen Sie.

„Es gibt nur einen Weg, ihn zu retten. Implementiere diese Prozedur, bevor die Sonne wieder aufgeht:

fnxy=xyfalls n=0xfalls n>0 und y=0f(n1)(fnx(y1))((fnx(y1))+y)falls n>0 und y>0

Gelingt dir das nicht, wird Dieter nie mehr zurückkehren. Ein unmögliches Unterfangen, nachdem dein kleiner Freund so viel Unfug angerichtet hat. Er hat seinen eigenen Untergang eingeleitet!“

Und mit diesen Worten und einem schallenden Lachen wirft Dark Dieter Ihr Programmierung-1-Buch in Richtung Kamin und verschwindet aus dem Zimmer. Die lodernden Flammen vernichten jede Chance auf Rettung.

Seit Dark Dieter den Raum verlassen hat, ist es deutlich wärmer geworden. Schweißnass setzen Sie sich wieder an den Kamin.

So knifflig kann es schon nicht sein, die Prozedur zu implementieren. Oder etwa doch?

  1. Hat Dark Dieter Recht? Gibt es Funktionen, die Sie in Ihrem Interpreter nun nicht mehr implementieren können?

    Falls ja: Geben Sie eine solche Funktion an, und erklären Sie knapp, wieso sie nun nicht mehr implementiert werden kann. Falls nein: Erklären Sie knapp, warum.

    Gesucht ist in beiden Fällen nur eine kurze, intuitive Begründung.

  2. Lösen Sie nun die Aufgabe des Geistes.

    Deklarieren Sie unter den bekannten Einschränkungen eine Prozedur f: int -> int -> int -> int mit dem oben angegebenen Verhalten. Verwenden Sie nur fortytwo und Hilfsprozeduren, die Sie bereits mit fortytwo deklariert haben.

    Eventuell können Sie den Geist milde stimmen, in dem Sie dabei nur auf Konstrukte zurückzugreifen, die in den ersten drei Kapiteln des Buches eingeführt wurden (insbesondere also keine Listen verwenden). Milde gestimmte Geister pflegen Größzügigkeit bei der Vergabe von Bonusdietern an den Tag zu legen!

Teil 3


Kaum nachdem Sie mit letzten Kräften die letzte schließende Klammer Ihrer Implementierung in den Interpreter getippt haben, werden Sie wieder vom Schlaf übermannt...


Die Sonne scheint. Ein lautes „Ding Dong!“ reißt Sie aus dem Schlaf. War das die Türklingel? Immer noch müde schlurfen Sie zur Tür, öffnen Sie – und vor Ihnen steht Ihr Freund Dieter und lächelt Sie an. Mit einem frohen „Gestern habe ich da wohl irgendwas kaputtgemacht, aber das kriegen wir wieder hin!“ hüpft er in Ihre Wohnung. An die nächtlichen Abenteuer scheint er sich nicht mehr zu erinnern. Während Sie Dieter wieder zur Couch folgen, beginnen Sie sich zu fragen, ob Dark Dieter nur ein Traum war.

Der Tisch vor dem Kamin ist leer.

Formalien

Bitte geben Sie Ihre SML-Programme in einer .sml-Datei ab, damit diese direkt in einem Interpreter ausführbar sind. Geben Sie bitte zusätzlich stets auch eine Erklärung zu Ihrem Code ab. Die Erklärungen und Antworten können Sie wahlweise in eine separate .txt- oder .pdf-Datei schreiben. Bitte geben Sie zum Schluss alle Dateien in gepackter Form als eine .zip-Datei ab.

Testen Sie Ihre Lösungen vor der Abgabe. Nicht lauffähige Abgaben können mit 0 Punkten bewertet werden.

Sie können, wenn Sie glauben eine besonders schöne Lösung gefunden zu haben, versuchen zu erklären, warum Ihre Lösung besonders schön ist und dadurch möglicherweise Bonusdieter gewinnen.

Laden Sie Ihren Lösungsvorschlag bis spätestens zum 15.11.2018 um 23:59 Uhr auf Ihrer persönlichen Statusseite hoch.

Der Rechtsweg ist ausgeschlossenen. Angehörige und Angestellte von Dieter Schlau und Dark Dieter dürfen leider nicht teilnehmen.

Die Aufgabe und damit verbundene weiterführende Themen aus verschiedenen Bereichen der Informatik werden in einem kNobeltutorium besprochen. Das kNobeltutorium zu dieser Aufgabe findet am Donnerstag, 22.11.2018 um 14:15 in E1 3, Raum 528 statt.

Alle Aufgaben gelöst? Prima, dann kann es weitergehen.