Blatt02

Professur für Rechnerarchitektur
Prof. Dr. Armin Biere
Dr. Mathias Fleury
Freiburg, 01. Mai 2026
Technische Informatik

Übungsblatt 2

Bitte ankreuzen welches von beiden Punkte passt:

□ Ich habe die Aufgaben selbst versucht zu lösen und möchte ein Korrektur

□ Ich habe irgendwann die KI gefragt und einfach abgeschrieben. In diesem Fall:

Die Bewertung passiert nur wenn diese Aufgabe beantwortet wurde.

Hinweis: Die Programme zum Swappen von Werten, die Armin versprochen hat, kommen erst nächste Woche.

Vorgeschlagenes Lesethema der Woche: Warum wollen wir eigentlich eine mathematische Beschreibung? Wenn der Toyota-Fahrer vom Bremspedal runter muss, zum Bremsen zu können https://web.archive.org/web/20131111063302/http://www.safetyresearch.net/2013/11/07/toyota-unintended (die verlinkten Folien sind auch interessant!).

Die Fibonacci-Zahlen sind eine Folge von positiven ganzen Zahlen und wurden um ca. 1200 von Leonardo Fibonacci (Leonardo von Pisa) entdeckt. Ursprünglich dienten sie ihm dazu, das Wachstum einer Kaninchenpopulation zu beschreiben.

Die -te Fibonacci-Zahl ist für rekursiv definiert durch:

ü

Das erste was uns interessiert, ist die Anzahl an Additionen, die durchgeführt werden: . Definieren Sie rekursiv – bei Berechnen von kommen also 1 ('+') und Additionen. Berechnen Sie die ersten und bis . Was sieht man? Beweisen Sie es!

Statt die obige Definition zu nutzen, benutzen wir, weil sie weniger rekursive Aufrufe macht:

ü

Zeigen Sie, dass die Definitionen gleich sind.

Schreiben Sie ein Programm für den ReTI-Rechner, das die -te Fibonacci-Zahl berechnet und in speichert. Gehen Sie davon aus, dass der Wert von in abgelegt ist.

Stellen Sie sicher, dass Ihr Tutor die Abgabe aus Ihrer Einreichung kopieren kann, um es mit https://github.com/sebwalk/reti-emulator ausführen zu können!

Hinweis: Kommentieren Sie Ihr Programm ausführlich, fehlende Kommentare führen zu Punktverlust. Unverständliche Programme ohne Kommentare gelten nicht als bearbeitet!

Schreiben Sie ein Programm für den ReTI-Rechner, das den größten gemeinsamen Teiler von und berechnet. Das Ergebnis soll in gespeichert werden.

Erläutern Sie Ihr Programm mit Kommentaren.

Führen Sie zusätzlich Ihren Programmablauf am Beispiel , vor.

Hinweis: und

In der nächsten Woche werden wir auf dem Übungsblatt Aufgaben zum Thema ReTi haben, die mit dem von Armin in der Vorlesung vorgestellten Tool zu lösen sind. Um sich darauf vorzubereiten, müssen einige Tools installiert werden. Dies ist zwar nicht besonders schwierig, aber es braucht etwas Zeit, weshalb die Installation in dieser Woche in den Übungen schon vorweggenommen wird.

Diese Installation ist leicht System-abhängig:

Linux/BSD: Da sollte es nichts zu tun geben, da wir nur einen Compiler brauchen. Unter Ubuntu müssen Sie sudo apt install build-essential ausführen. Auf anderen Distributionen: gcc und git installieren.

macOS: Da müssen Sie im Terminal xcode-select --install ausführen, um den Compiler zu installieren (dauert mehrere Minuten und holt sich mehrere Gigabyte von den Apple Servern runter).

Windows: Da werden wir einfach Ubuntu in WSL installieren. Folgen Sie einfach https://learn.microsoft.com/de-de/windows/wsl/install mit Ubuntu als <Distribution Name>. Danach können Sie einfach WSL öffnen und dann sudo apt install build-essential ausführen.

Ab jetzt ist es für alle System gleich: ein Terminal öffnen (WSL terminal für Windows), dort dann das Repository clonen (also runterladen mit dem git Tool):

Wenn das gemacht ist, einfach in dem Verzeichnis reingehen:

und das Programm kompilieren:

Auf Windows müssen Sie vielleicht das Speicherlimit (wie groß ist der Speicher von der ReTi?) runtersetzen:

(Probieren Sie auch 8, falls die Tests nicht durchgehen.)

Wenn das ohne Fehlermeldung läuft, schreiben Sie einfach: "Es kompiliert!" als Abgabe.

Abgabe: Freitag über Ilias