Von-Neumann-Architektur und Grenzen der Automatisierung
Ihr Smartphone kann in Sekundenbruchteilen Millionen Pixel berechnen, und doch gibt es Aufgaben, an denen jeder Rechner scheitert, egal wie schnell er ist. Warum? Dazu müssen Sie zwei Dinge verstehen: wie ein Rechner im Kern arbeitet (Von-Neumann-Architektur) und wo die Grenzen dessen liegen, was Algorithmen leisten können. Am Ende der Seite beantworten Sie die Frage: Kann eine Software „jeden Fehler in jedem Programm“ finden?
Aufbau eines Von-Neumann-Rechners
Fast jeder Rechner, vom Schulserver bis zum Smartphone, folgt demselben Grundplan, den John von Neumann 1945 beschrieben hat. Er besteht aus wenigen Komponenten, die über Leitungen (den Bus) verbunden sind.
-
Steuerwerk: holt Befehle, entschlüsselt sie und steuert den Ablauf. Es enthält den Befehlszähler (Adresse des nächsten Befehls).
-
Rechenwerk (ALU): führt Rechen- und Vergleichsoperationen aus. Zwischenergebnisse liegen im Akkumulator (Register).
-
Speicher: nummerierte Zellen, jede mit einer Adresse.
-
Ein-/Ausgabe: Tastatur, Bildschirm, Netzwerk, Datenträger.
Der Vorteil: Ein Programm ist selbst nur Datenmaterial, man kann es laden, austauschen oder von einem anderen Programm erzeugen lassen (Compiler, Betriebssystem). Der Nachteil: Ein Fehler kann Daten so verändern, dass sie als Befehle ausgeführt werden (mehr dazu im nächsten Abschnitt).
a) Nennen Sie die Hauptkomponenten der Von-Neumann-Architektur. b) Erklären Sie, was „gemeinsamer Speicher für Programme und Daten“ bedeutet.
- a) Nennen Sie die Hauptkomponenten der Von-Neumann-Architektur.
- b) Erklären Sie, was „gemeinsamer Speicher für Programme und Daten“ bedeutet.
Fetch-Decode-Execute und Registermaschine
Wie führt der Rechner ein Programm aus? Immer im gleichen Takt, dem Fetch-Decode-Execute-Zyklus:
-
Fetch (Holen): Das Steuerwerk liest den Befehl aus der Speicherzelle, auf die der Befehlszähler zeigt, und erhöht den Befehlszähler um 1.
-
Decode (Entschlüsseln): Das Steuerwerk ermittelt, welche Operation gemeint ist und welche Adresse sie verwendet.
-
Execute (Ausführen): Das Rechenwerk bzw. der Speicher führt den Befehl aus. Bei einem Sprungbefehl wird der Befehlszähler überschrieben.
Der Befehlszähler bestimmt also die Reihenfolge der Befehle. Ohne Sprung läuft das Programm der Reihe nach, ein Sprung ändert den Ablauf.
Um das zu üben, nutzt man ein vereinfachtes Modell, die Registermaschine mit einem Akkumulator ACC:
| Befehl | Wirkung |
|---|---|
LOAD a |
ACC := Inhalt von Zelle a |
ADD a |
ACC := ACC + Inhalt von Zelle a |
SUB a |
ACC := ACC − Inhalt von Zelle a |
STORE a |
Zelle a := ACC |
JMP z |
Befehlszähler := z |
JMPZ z |
Befehlszähler := z, falls ACC = 0, sonst weiter |
HALT |
Programm endet |
Für Schleifen kombiniert man JMPZ (bedingter Sprung) mit JMP (unbedingter Sprung). Am besten führen Sie bei jeder Aufgabe eine Tabelle mit den Spalten Befehlszähler, Befehl, ACC und den betroffenen Zellen. Das ist auch im Abitur die sicherste Methode.
Erklären Sie den Fetch-Decode-Execute-Zyklus in drei Schritten und nennen Sie die Rolle des Befehlszählers.
Erklären Sie den Fetch-Decode-Execute-Zyklus in drei Schritten und nennen Sie die Rolle des Befehlszählers.
Ein Registermaschinenprogramm hat die Befehle LOAD a, ADD b, STORE c, JMPZ z, HALT. Die Speicherzellen: a = 5, b = 7, c = 0. a) Schreiben Sie ein Programm, das a + b in…
Ein Registermaschinenprogramm hat die Befehle LOAD a, ADD b, STORE c, JMPZ z, HALT. Die Speicherzellen: a = 5, b = 7, c = 0.
- a) Schreiben Sie ein Programm, das a + b in c speichert.
- b) Verfolgen Sie Akkumulator und Speicher Schritt für Schritt.
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…
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.
- a) Verfolgen Sie Befehlszähler, Akkumulator und Zelle 10 bis zum Halt.
- b) Beschreiben Sie, was das Programm berechnet.
- c) Erläutern Sie, welches Risiko entsteht, weil Programm und Daten im selben Speicher liegen (z. B. Pufferüberlauf).
Praktische Grenzen: Laufzeit wächst zu schnell
Ein Algorithmus kann korrekt sein und trotzdem nutzlos, wenn er zu lange läuft. Entscheidend ist, wie die Anzahl der Schritte mit der Eingabegröße $n$ wächst. Ein Rechner schaffe $10^9$ Schritte pro Sekunde.
| $n$ | $n^2$ Schritte | $2^n$ Schritte | Laufzeit bei $2^n$ |
|---|---|---|---|
| 20 | 400 | $\approx 10^6$ | $\approx 1\,\text{ms}$ |
| 30 | 900 | $\approx 1{,}07 \cdot 10^9$ | $\approx 1\,\text{s}$ |
| 40 | 1.600 | $\approx 1{,}1 \cdot 10^{12}$ | $\approx 18\,\text{min}$ |
| 50 | 2.500 | $\approx 1{,}1 \cdot 10^{15}$ | $\approx 13\,\text{Tage}$ |
| 60 | 3.600 | $\approx 1{,}2 \cdot 10^{18}$ | $\approx 36\,\text{Jahre}$ |
Jedes zusätzliche $n$ verdoppelt die Laufzeit bei $2^n$. Das nennt man exponentielles Wachstum. Ein tausendfach schnellerer Rechner spart nur den Faktor 1000, das entspricht etwa 10 zusätzlichen Eingaben ($2^{10} = 1024$). Gegen exponentielles Wachstum hilft Hardware kaum.
Ein klassisches Beispiel: das Problem des Handlungsreisenden
Ein Lieferdienst aus Köln will $n$ Städte genau einmal besuchen und zum Start zurückkehren. Startet man in einer festen Stadt, gibt es $(n-1)!$ Reihenfolgen. Bei $n = 10$ sind das $9! = 362.880$. Bei symmetrischen Entfernungen zählt jede Tour doppelt (Hin- und Rückrichtung), also $181.440$ verschiedene Rundreisen. Die Fakultät wächst noch schneller als $2^n$: Schon $19!$ liegt bei etwa $1{,}2 \cdot 10^{17}$, während $2^{19}$ nur etwa $5 \cdot 10^5$ beträgt.
In der Praxis nutzt man Heuristiken (z. B. „fahre immer zum nächsten unbesuchten Ort“). Sie liefern schnell eine gute Tour, aber ohne Garantie, dass sie die kürzeste ist. Man tauscht also Optimalität gegen Rechenzeit.
Ein Algorithmus benötigt für $n$ Eingaben $2^n$ Schritte, ein Rechner schafft $10^9$ Schritte pro Sekunde. a) Bestimmen Sie die Laufzeit für $n = 30$ und $n = 60$…
Ein Algorithmus benötigt für $n$ Eingaben $2^n$ Schritte, ein Rechner schafft $10^9$ Schritte pro Sekunde.
- a) Bestimmen Sie die Laufzeit für $n = 30$ und $n = 60$ (Größenordnung in Sekunden bzw. Jahren).
- 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). a) Bestimmen Sie die Anzahl möglicher…
Eine Handelskette will 20 Filialen in Niedersachsen auf einer kürzesten Rundreise anfahren (Problem des Handlungsreisenden).
- 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.
- b) Erklären Sie, warum man in der Praxis Heuristiken einsetzt und was dabei aufgegeben wird.
Prinzipielle Grenzen: das Halteproblem
Es gibt zwei Arten von Grenzen. Praktisch nicht berechenbar heißt: Es gibt einen Algorithmus, aber er braucht unvertretbar lange (Abschnitt davor). Nicht berechenbar heißt: Es gibt gar keinen Algorithmus, auch nicht bei unbegrenzter Zeit und Speicher.
Das berühmteste Beispiel ist das Halteproblem (Alan Turing, 1936). Die Frage: Gibt es ein Programm haelt(P, x), das für jedes Programm $P$ und jede Eingabe $x$ entscheidet, ob $P$ bei Eingabe $x$ irgendwann hält oder endlos läuft? Man könnte damit Endlosschleifen automatisch aufspüren. Die Antwort ist nein.
Folgerung: Es gibt kein Verfahren, das für beliebige Programme automatisch prüft, ob sie terminieren. Ähnliches gilt für viele weitere Fragen über das Verhalten von Programmen („Gibt das Programm je den Wert 0 aus?“, „Enthält es einen Fehler?“).
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…
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.
Trotzdem prüft man in der Praxis vieles:
-
Testen: Man führt das Programm mit ausgewählten Eingaben aus. Testen kann Fehler finden, aber nie deren Abwesenheit beweisen, weil man nicht alle Eingaben ausprobieren kann.
-
Verifikation für Spezialfälle: Für eingeschränkte Programmklassen oder einzelne Eigenschaften (z. B. „diese Schleife terminiert, weil der Zähler bei jedem Durchlauf sinkt und nie negativ wird“) lassen sich Beweise führen, auch automatisch.
-
Zeitlimits: Man bricht Programme nach einer Frist ab. Das ist keine Entscheidung über Halten, sondern eine Behandlung des Problems.
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,…
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.
- a) Beschreiben Sie, was
s(s)tut, und leiten Sie den Widerspruch her.
- b) Formulieren Sie die Schlussfolgerung für die Automatisierung der Programmprüfung.
- 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“. a) Beurteilen Sie die Aussage mithilfe des Halteproblems. b) Erläutern…
Ein Unternehmen wirbt mit einer Software, die „jeden Fehler in jedem Programm automatisch findet“.
- a) Beurteilen Sie die Aussage mithilfe des Halteproblems.
- b) Erläutern Sie den Unterschied zwischen nicht berechenbar und praktisch nicht berechenbar (Laufzeit).
- c) Beschreiben Sie, was Testen leisten kann und was nicht.
Zurück zum Anfang: Software kann nicht „jeden Fehler in jedem Programm“ finden, weil die dafür nötigen Entscheidungen (etwa das Halteproblem) nachweislich von keinem Algorithmus gelöst werden. Und selbst lösbare Probleme scheitern oft an exponentieller Laufzeit.
Auf einen Blick
-
Von-Neumann-Architektur: Prozessor (Steuerwerk, Rechenwerk), gemeinsamer Speicher für Programme und Daten, Ein-/Ausgabe, verbunden durch einen Bus.
-
Fetch-Decode-Execute: Befehl holen (Befehlszähler +1), entschlüsseln, ausführen. Sprünge überschreiben den Befehlszähler.
JMPZspringt nur bei ACC = 0. -
Gemeinsamer Speicher: ermöglicht flexible Programme, birgt aber Risiken wie den Pufferüberlauf.
-
Praktische Grenzen: exponentielles Wachstum ($2^n$) und Fakultät ($n!$) machen Probleme schon für mittlere $n$ unlösbar, schnellere Hardware hilft kaum. Heuristiken tauschen Optimalität gegen Zeit.
-
Prinzipielle Grenzen: Das Halteproblem ist nicht berechenbar. Testen findet Fehler, beweist aber nicht deren Abwesenheit.
-
Operatoren: nennen (Komponenten), erläutern (Zyklus, Risiken), verfolgen (Registermaschine), bestimmen (Laufzeit), beurteilen (Aussagen über Software).