Blatt03
Page 1
Professur für Rechnerarchitektur
Prof. Dr. Armin Biere
Dr. Mathias Fleury
Freiburg, 8. Mai 2026
Technische Informatik
Übungsblatt 3 (v2)
Hinweis 1: Am Donnerstag ist Feiertag (aber nicht Freitag!). Die Tutorate fallen also aus, aber nächste Woche werden Blatt 3 und 4 korrigiert.
Hinweis 2: Damit alle Tutoren gleich viele Abgaben korrigieren, werden wir manche Abgabeteams von einem Tutorat zu einer anderen Tutoren-Gruppe bewegen in Ilias (wahrscheinlich Dienstag). Dies ändert nur bei wem Sie abgeben auf Ilias. Sie sollen ganz normal weiter zum selben Tutorat gehen, wo Sie jetzt schon gehen. Sie werden über Mail informiert werden.
Achtung 1: Diese Abgabe muss mit dem Computer geschrieben worden sein. Handgeschriebene Antworten werden nicht benotet.
Achtung 2: Aufgabe 4 wurde in v2 ersetzt (baut auf der Übung von letzter Woche auf).
Vorgeschlagenes Lesethema der Woche: Wie viel vereinfacht ist die ReTi eigentlich? Wie setze ich am besten Register auf 0 https://xania.org/202512/01-xor-eax-eax? Wie kann ich am besten Zahlen aufsummieren https://xania.org/202512/02-adding-integers? Alle Einträge sind interessant, aber die anderen werden Sie besser verstehen in der Rechnerarchitektur Vorlesung.
Aufgabe 1 (2 + 4 + 2 Punkte)
a)
Folgender Text hat die angegebene Häufigkeitsverteilung:
HEUTE BESTEHE ICH HEUTE DIESE KLAUSUR T
| Zeichen | Häufigkeit |
|---|---|
| E | 9 |
| U | 4 |
| I | 2 |
| S | 3 |
| H | 4 |
| T | 4 |
| B | 1 |
| D | 1 |
| C | 1 |
| A | 1 |
| L | 1 |
| R | 1 |
| K | 1 |
Erzeugen Sie für diese Häufigkeitsverteilung einen binären Baum. Gehen Sie dabei analog zur Vorlesung und Übungen vor.
Um die Korrektur zu erleichtern, falls es mehrere Möglichkeiten gibt, arbeiten Sie erst in den Teilen UE und ISHT und BDCALRK separat, bis Sie im ganzen Baum arbeiten müssen.
Page 2
Hinweis: Auf der nächsten Seite ist die Tabelle kopiert. Zeichnen Sie den Baum dort!
Hinweis 2: In Klausuren geben wir gerne die Reihenfolge der Buchstaben vor! Der Code für die Tabelle ist:
\usepackage{tikz}
\usepackage{substr}
\newcommand\myTextToEncodeTwo{HEUTE BESTEHE ICH HEUTE DIESE KLAUSUR T}
\newcommand\myLettersTwo{E,U,I,S,H,T,B,D,C,A,L,R,K}
\begin{tikzpicture}[scale=1.2]
\foreach \letter [count=\xi] in \myLettersTwo {
\node (letter-\xi) at (\xi, 0) {\letter};
\node (count-\xi) at (\xi, -1) {\CountSubStrings{\letter}\myTextToEncodeTwo};
}
\node (question) at (0,0) {b)};
\draw (6.5,0.5) -- (6.5,-1.5);
\draw (2.5,0.5) -- (2.5,-1.5);
\end{tikzpicture}
Hinweis 3: Ein Baum ohne 0/1 ist nicht eindeutig.
b)
Geben Sie den resultierenden Huffman-Code in der folgenden Tabelle an. Gehen Sie dabei analog zur Vorlesung vor.
| Buchstabe | Huffman-Code |
|---|---|
| K | |
| B | |
| I | |
| E |
c)
Ein anderer Student hat eine kürzere Lösung gefunden für das Encoding vom vollständigen Text. Ist dies möglich? Begründen Sie!
Page 3
| Zeichen | Häufigkeit |
|---|---|
| E | 9 |
| U | 4 |
| I | 2 |
| S | 3 |
| H | 4 |
| T | 4 |
| B | 1 |
| D | 1 |
| C | 1 |
| A | 1 |
| L | 1 |
| R | 1 |
| K | 1 |
b)
Page 4
Aufgabe 2 (1 + 1 + 1 + 1 Punkte)
Konvertieren Sie die Zahlen in Betrag & Vorzeichen, Einerkomplement und Zweierkomplement Darstellung.
Aufgabe 3 (3 Punkte)
Beweisen Sie das folgende Lemma aus der Vorlesung:
Lemma: Sei
Hierbei sei
Verwenden Sie dazu nur die Definition des Zweier-Komplements und die geometrische Summenformel.
Aufgabe 4 (2 + 5 Punkte)
In dieser Übung benutzen wir wieder die Fibonacci-Sequenz
Betrachten wir eine leicht abgeänderte Version des Algorithmus von der Aufgabe von letzter Woche:
a)
Erklären Sie in 3-4 Sätzen, warum dieser Algorithmus und der von letzter Woche das Selbe rechnen.
b)
Zeigen Sie per Induktion, dass
Es ist übrigens möglich zu zeigen, dass
Aufgabe 5 (5 Punkte)
In dieser Übung werden wir ein VSCode Plugin nutzen. Das Plugin ist das Resultat von der Arbeit von zwei Studenten, Malte Pullich und Tuvia Navon. Es könnte aber Bugs geben. Falls Sie welche finden, öffnen Sie bitte eine Issue auf dem Github Repository und beschreiben Sie den Fehler auf Ilias.
Page 5
a) VSCode Installation
Installieren Sie Visual Studio Code (VSCode) von der offiziellen Website: https://code.visualstudio.com/. Stellen Sie sicher, dass die Installation erfolgreich abgeschlossen ist. Installieren Sie docker und die "Dev Containers" Extension in VSCode (siehe https://code.visualstudio.com/docs/devcontainers/tutorial).
b)
Clonen Sie https://github.com/m-fleury/reti-vscode
c) ReTi Plugin Installation
- Öffnen Sie in VSCode das Verzeichnis
reti-vscode. - Drücken Sie F5 und starten Sie die Erweiterung mit "Extension Development Host".
d) Debugging mit ReTi
Lesen Sie die Debugging-Anleitung im ReTi-GitHub-Repository: https://github.com/mlt279/vscode-reti/blob/main/documentation/Features.md.
e) Vorbereitung auf die nächste Übung
In der nächsten Übung werden wir den Step-by-Step-Debugger intensiver nutzen. Öffnen Sie Dateien aus https://github.com/m-fleury/reti-vscode/tree/main/artifact/vscode-extension/pullich_reti_tools_vscode/sampleWorkspace. Nutzen Sie den Step-by-Step-Debugger, um ein einfaches ReTi-Programm zu debuggen.
- Laden Sie ein Beispiel-ReTi-Programm.
- Setzen Sie Breakpoints.
- Starten Sie den Debugger und gehen Sie Schritt für Schritt durch das Programm.
f)
Geben Sie ein Screenshot ab.
Aufgabe 6 (2 + 2 + 1 Punkte)
Implementieren Sie jetzt das Swappen von zwei Werten ohne extra Speicherplatz zu benutzen. Dafür gibt es zwei Methoden:
a) Mit XOR
void swap(int &a, int &b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
Erklären Sie warum das funktioniert und implementieren Sie es dann in der ReTi. Prüfen Sie Ihre Erklärung mit dem Step-by-Step-Debugger und mit verschiedenen Werten für
b) Alternativ
void swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
Page 6
Selbe Frage wie in a).
c)
Ist diese Methode zum Swappen nützlich bei der ReTi? In der ReTi von Betriebssysteme funktioniert XOR mit beliebigen Registern.
Hinweis: Es ist auf gewöhnlichen CPUs keine gute Idee, diesen Trick zu benutzen. Der Compiler erkennt und optimiert auch solche Motive.
Abgabe: Nächsten Freitag, 1600