Blatt04

Page 1

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

Übungsblatt 4

Vorgeschlagenes Lesethema der Woche: Wenn die Analyse einen sehr seltenen Bug im Sortieren findet https://web.archive.org/web/20150910081347/http://www.envisage-project.eu/proving-andro

Achtung 2: Nächste Woche ist Pfingstpause. Da gibt es also keine Tutorate und keine Abgabe.

Achtung 3: Am 4. Juni ist wieder Feiertag. Die Tutorate von Donnerstag fallen also aus.

Aufgabe 1 (KI/Pflicht Punkte)

Bitte ankreuzen welches von beiden Punkte passt:

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

  • a) mir ist bewusst, dass signifikante Bearbeitung reicht zum Bestehen des Blatts
  • b) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

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

  • a) muss ich alle Aufgaben abgeben, das reicht zum Bestehen dieses Blatts
  • b) mir ist bewusst, dass ich keine Korrektur bekommen werde
  • c) mir ist bewusst, dass ich vielleicht trotzdem Vorrechnung muss (ohne meine Notizen!)

Die Bewertung passiert nur wenn diese Aufgabe beantwortet wurde.

Aufgabe 2 (5 Punkte)

Nutzen Sie das retiquiz Programm von Prof. Biere, das Sie letzte Woche installiert haben. Nutzen Sie es mit ./retiquiz <ihre-matrikel-nummer>. Schreiben Sie hier das Resultat auf, mit der Anzahl an Punkten, die Sie bekommen haben. Falls Sie zu zweit abgeben, reicht es, wenn es die Matrikelnummer von einem von Ihnen ist. Geben Sie Ihre ganze Lösung an, also sowohl der Aufruf, das Programm mit den fehlenden Bits und auch die Punktzahl, wie zum Beispiel (wo ich immer '0' geraten habe):

Page 2

$ ./retiquiz 42
ReTI Machine Code Quiz Version 0.0.2
retiquiz 42 16
Enter hexadecimal digits as an answer or
space ' ' to skip a question or 'q' to quit.
For irrelevant '*' in the machine code use '0'.
Asking 16 questions.
INSTRUCTION                    ; PC        CODE
STOREIN1 13                    ; 00000000  0000000d ✗
  expected 9 in 9000000d at I[31:28]
LOADIN2 IN1 5                  ; 00000001  61000005 ✓
STOREIN2 12                    ; 00000002  0000000c ✗
  expected a in a000000c at I[31:28]
LOADI IN1 28                   ; 00000003  0100001c ✗
  expected 7 in 7100001c at I[31:28]
LOADIN1 ACC 17                 ; 00000004  53000001 ✗
  expected 1 in 53000011 at I[7:4]
JUMP!= -28                     ; 00000005  e80fffe4 ✗
  expected f in e8ffffe4 at I[23:20]
JUMP> -7                       ; 00000006  c8f0fff9 ✗
  expected f in c8fffff9 at I[19:16]
JUMP> -27                      ; 00000007  08ffffe5 ✗
  expected c in c8ffffe5 at I[31:28]
LOADIN2 ACC 3                  ; 00000008  63000003 ✓
LOADIN1 ACC 19                 ; 00000009  50000013 ✗
  expected 3 in 53000013 at I[27:24]
LOADIN2 IN1 13                 ; 0000000a  6000000d ✗
  expected 1 in 6100000d at I[27:24]
LOADIN2 ACC 0                  ; 0000000b  63000000 ✓
STORE 29                       ; 0000000c  8000000d ✗
  expected 1 in 8000001d at I[7:4]
LOADIN2 IN2 24                 ; 0000000d  62000008 ✗
  expected 1 in 62000018 at I[7:4]
JUMP!= -27                     ; 0000000e  e8fff0e5 ✗
  expected f in e8ffffe5 at I[11:8]
LOADIN2 IN1 8                  ; 0000000f  61000008 ✓
RESULT
  asked       100%  16/16
  answered    100%  16/16
  skipped       0%   0/16
  correct  ✓     25%   4/16
  incorrect ✗    75%  12/16
POINTS
  0 points (more answers incorrect than correct)
TIME
  18.10 seconds

Wenn Sie ./retiquiz aufrufen, kommt jedes Mal ein neues Quiz raus, aber mit ./retiquiz <ihre-matrikel-nummer> werden Sie immer über dasselbe Programm abgefragt. So können Sie zum Beispiel das Quiz nochmal machen.

Hinweis: Falls Sie LaTeX benutzen, müssen Sie ✓ und ✗ definieren, zum Beispiel mit:

\usepackage{pifont}
\usepackage{newunicodechar}
\newunicodechar{✓}{\ding{51}}
\newunicodechar{✗}{\ding{55}}

Page 3

Aufgabe 3 (3 + 2 + 2 + 1 Punkte)

Der Wert einer nichtnegativen Festkommazahl mit Vorkommastellen und ohne Nachkommastellen im Dezimalsystem ist gegeben durch

Betrachtet man auch negative Festkommazahlen, dann ist es im Dezimalsystem am verbreitetsten, die Darstellung durch Betrag und Vorzeichen zu wählen. Dabei wird die höchstwertige Stelle als "Vorzeichenbit" interpretiert. ist dann auf den Wertebereich beschränkt. Wenn , dann handelt es sich um eine nichtnegative Zahl. Die Darstellung durch Betrag und Vorzeichen ordnet den folgenden Wert zu:

Es gibt aber auch im Dezimalsystem Alternativen zur Betrag- und Vorzeichendarstellung.

Sei , mit und für .

a)

Betrachten Sie (analog zur Einer-Komplement-Darstellung im Binärsystem) eine Neuner-Komplement-Darstellung im Dezimalsystem mit dem Wert

Geben Sie die größte darstellbare Zahl für und für beliebige an. Wählen Sie so, dass in der Neuner-Komplement-Darstellung der Zahlenbereich symmetrisch ist, d.h. dass die kleinste und die größte darstellbare Zahl den gleichen Betrag haben. Begründen Sie kurz Ihre Wahl.

b)

Überlegen Sie sich nun, wie das Komplementieren der Ziffern in der Neuner-Komplement-Darstellung definiert werden muss, damit das folgende Lemma 1 gilt.

Lemma 1: Sei eine Festkommazahl im Dezimalsystem, die Festkommazahl im Dezimalsystem, die aus durch Komplementieren aller Ziffern hervorgeht. Dann gilt .

Rechnen Sie nach, dass für die Dezimalzahl () mit Ihrer Komplementierung die Aussage von Lemma 1 gilt.

c)

Definieren Sie nun (analog zur Zweier-Komplement-Darstellung im Binärsystem) eine Zehner-Komplement-Darstellung im Dezimalsystem mit dem Wert

Page 4

Wählen Sie so, dass in der Zehner-Komplement-Darstellung die Zahlendarstellung eindeutig und zusammenhängend ist (d.h. es gibt im Bereich der darstellbaren Zahlen keine Lücke). Beweisen Sie, dass das von Ihnen gewählte , zusammen mit Ihrer Komplementierung aus Aufgabenteil b), das folgende Lemma 2 erfüllt:

Lemma 2: Sei eine Festkommazahl im Dezimalsystem, die Festkommazahl im Dezimalsystem, die aus durch Komplementieren aller Ziffern hervorgeht. Dann gilt .

d)

Wie muss das "Komplementieren" einer Ziffer definiert werden, damit Lemmata 1 und 2 für ein Zahlensystem mit der Basis gelten? Begründen Sie Ihre Antwort.

Aufgabe 4 (2 + 3 Punkte)

a)

Gegeben sei . Geben Sie den Wert von als Einerkomplementzahl mit Nachkommastellen und als Zweierkomplementzahl mit Nachkommastellen an.

Hinweis: Für ergibt sich der Wert einer Einerkomplementzahl analog zu dem in der Vorlesung vorgestellten Fall aus dem entsprechenden Wert für durch Subtraktion der größten darstellbaren Zahl mit Vorkommastellen und Nachkommastellen. Um den Wert einer Zweierkomplementzahl zu erhalten, wird bei im Vergleich zum Einerkomplement eine entsprechend größere Zahl subtrahiert, um zu verhindern, dass es zwei verschiedene Darstellungen für die 0 gibt.

b)

Stellen Sie die folgenden Zahlen als Zweierkomplementzahlen mit insgesamt 8 Bit und zwei Nachkommastellen dar.

  1. Die Dezimalzahl
  2. Die Dezimalzahl
  3. Die Hexadezimalzahl
  4. Die größte darstellbare Zahl.
  5. Die größte darstellbare Zahl, die kleiner als 1 ist.
  6. Die größte darstellbare Zahl, die kleiner als 0 ist.

Abgabe: Freitag, 1600