TI02-1

Page 1

Technische Informatik
Sommersemester 2026
[Name], [Name]
Übungsblatt 02
06.05.2026

Aufgabe 1

Ich habe die Aufgaben selbst versucht zu lösen und möchte eine Korrektur.

Aufgabe 2

a) Es gilt zu zeigen, dass die folgend rekursiv definierte Folge die Anzahl der Additionen in der Fibonacci-Folge darstellt.

Für stimmt die Definition:

Also sind und offenbar äquivalent.

Page 2

Beweis der Richtigkeit per Induktion über :

IA: Basisfälle und

IV: Für ein beliebiges gelte und .

IS:

b)

Beweis der Äquivalenz per Induktion über :

IA: Basisfälle

IV: Für alle gelte .

IS: , für

Page 3

c)

# Speicherbelegung
# S(30) = n
# S(31) = s(n-2)
# S(32) = s(n-1)
# S(33) = s(n)
# S(34) = i (Loop Counter)
LOADI 6
STORE 30
LOADI 0
STORE 31    # Initialisierung der benötigten Speicherzellen
STORE 32    # |
STORE 33    # |
LOADI 2     # |
STORE 34    # |
LOAD 34     # ACC = i - n
SUB 30      # Überspringe die Schleife falls i > n
JUMPC <= 2  # |
JUMP 13
LOAD 31     # ACC = s(i-2) + s(i-1) + 1
ADD 32      # |
ADDI 1      # |
STORE 33    # Speichere s(i)
LOAD 32     # s(i-2) = s(i-1)
STORE 31    # |
LOAD 33     # s(i-1) = s(i)
STORE 32    # |
LOAD 34     # i++
ADDI 1      # |
STORE 34    # |
JUMP -15    # Wiederhole die Schleife
PRINT 33    # Ergebnis printen
JUMP 0

Page 4

Aufgabe 3

Unser Programm:

# Speicherbelegung
# M(40) = x
# M(41) = y
# M(42) = Ergebnis
1: LOADI 4
2: STORE 40
3: LOADI 2
4: STORE 41
5: LOADI 0
6: STORE 42
# Prüfe ob x == y bzw. x-y == 0
7: LOAD 40
8: SUB 41
9: JUMPC < 6   # y > x
# Wenn ACC == 0: fertig
10: LOADI 0
11: SUB 40
12: ADD 41      # ACC = y - x
13: JUMPC < 6   # x > y
# Fertig / x == y
14: JUMP 9
# Fall: y > x
15: LOAD 41
16: SUB 40
17: STORE 41    # y = y - x
18: JUMP -11
# Fall: x > y
19: LOAD 40
20: SUB 41
21: STORE 40    # x = x - y
22: JUMP -14
# Fertig: M(42) = ggT
23: LOAD 40
24: STORE 42
25: PRINT 42
26: JUMP 0

Page 5

Aufgabe 3 Fortsetzung

Wir haben in unserem Beispiel den folgenden Algorithmus verwendet, um das RETI Programm zu schreiben.

while x != y:
  if x > y:
    x = x - y
  else:
    y = y - x
  result = x

Beispieldurchführung an , :

PC Befehl ACC Erklärung
7 LOAD 40 4 ACC =
8 SUB 41 2 ACC =
9 JUMPC < 6 2 ACC > 0 kein Sprung
10 LOADI 0 0 0 in ACC laden
11 SUB 40 -4 ACC =
12 ADD 41 -2 ACC =
13 JUMPC < 6 -2 | Fall:
19 LOAD 40 4 ACC =
20 SUB 41 2 ACC =
21 STORE 40 2
22 JUMP -14 2 PC -= 14
8 SUB 41 0 ACC =
9 JUMPC < 6 0
10 LOADI 0 0 ACC = 0
11 SUB 40 -2 ACC =
12 ADD 41 0 ACC =
13 JUMPC < 6 0
14 JUMP 9 0 PC += 9
23 LOAD 40 2 ACC =
24 STORE 42 2
25 PRINT 42 2 Ergebnis ausgeben
26 JUMP 0 2 Programm beenden

Page 6

Aufgabe 4

Es kompiliert!