Aufgaben: Von-Neumann-Architektur und Grenzen der Automatisierung

1. a) Nennen Sie die Hauptkomponenten der Von-Neumann-Architektur.

1. b) Erklären Sie, was „gemeinsamer Speicher für Programme und Daten“ bedeutet.

Erklären Sie den Fetch-Decode-Execute-Zyklus in drei Schritten und nennen Sie die Rolle des Befehlszählers.

Nennen Sie zwei Aufgaben, die ein Computer prinzipiell nicht oder nur eingeschränkt lösen kann (z. B. Halteproblem, unvertretbar lange Laufzeit), und erklären Sie kurz je eine Ursache.

Ein Registermaschinenprogramm hat die Befehle LOAD a, ADD b, STORE c, JMPZ z, HALT. Die Speicherzellen: a = 5, b = 7, c = 0.

1. a) Schreiben Sie ein Programm, das a + b in c speichert.

1. b) Verfolgen Sie Akkumulator und Speicher Schritt für Schritt.

Ein Algorithmus benötigt für $n$ Eingaben $2^n$ Schritte, ein Rechner schafft $10^9$ Schritte pro Sekunde.

1. a) Bestimmen Sie die Laufzeit für $n = 30$ und $n = 60$ (Größenordnung in Sekunden bzw. Jahren).

1. b) Beurteilen Sie, ob ein 1000-mal schnellerer Rechner das Problem für $n = 60$ praktisch lösbar macht.

Eine Handelskette will 20 Filialen in Niedersachsen auf einer kürzesten Rundreise anfahren (Problem des Handlungsreisenden).

1. a) Bestimmen Sie die Anzahl möglicher Rundreisen als Fakultät und schätzen Sie die Größenordnung. Begründen Sie dabei, ob die Startfiliale und die Fahrtrichtung für die Zählung eine Rolle spielen.

1. b) Erklären Sie, warum man in der Praxis Heuristiken einsetzt und was dabei aufgegeben wird.

Angenommen, es gäbe ein Programm haelt(P, x), das entscheidet, ob Programm $P$ bei Eingabe $x$ hält. Man konstruiert s(P): Wenn haelt(P, P) wahr ist, läuft s endlos, sonst hält s.

1. a) Beschreiben Sie, was s(s) tut, und leiten Sie den Widerspruch her.

1. b) Formulieren Sie die Schlussfolgerung für die Automatisierung der Programmprüfung.

1. c) Nennen Sie ein praktisches Beispiel, in dem man trotzdem Teilaussagen prüfen kann (Testen, Verifikation für Spezialfälle).

Ein Unternehmen wirbt mit einer Software, die „jeden Fehler in jedem Programm automatisch findet“.

1. a) Beurteilen Sie die Aussage mithilfe des Halteproblems.

1. b) Erläutern Sie den Unterschied zwischen nicht berechenbar und praktisch nicht berechenbar (Laufzeit).

1. c) Beschreiben Sie, was Testen leisten kann und was nicht.

Ein Von-Neumann-Rechner führt ein Programm im Speicher ab Adresse 0 aus. Befehle: 0: LOAD 10, 1: SUB 11, 2: JMPZ 5, 3: STORE 10, 4: JMP 0, 5: HALT. Anfangs gilt Zelle 10 = 3 und Zelle 11 = 1.

1. a) Verfolgen Sie Befehlszähler, Akkumulator und Zelle 10 bis zum Halt.

1. b) Beschreiben Sie, was das Programm berechnet.

1. c) Erläutern Sie, welches Risiko entsteht, weil Programm und Daten im selben Speicher liegen (z. B. Pufferüberlauf).