Algorithmen und Berechenbarkeit
Begriffe vorab
- Algorithmus: Eindeutige Folge von Schritten, die ein Problem löst.
- Turing-Maschine: Abstraktes Rechenmodell von Alan Turing.
- Berechenbar: Eine Funktion, für die ein Algorithmus existiert.
- Entscheidungsproblem: Frage, ob es ein mechanisches Verfahren gibt, das jede mathematische Aussage entscheidet.
- Komplexität: Wie Zeit- und Speicherbedarf mit der Eingabegröße wachsen.
Was ein Algorithmus ist
Ein Algorithmus ist eine endliche, eindeutige Anleitung aus Einzelschritten, die für jede zulässige Eingabe zu einem Ergebnis führt. Ein Rezept ist keiner (es lässt Spielraum), das schriftliche Addieren schon. Die Informatik fragt nicht nur, wie man ein Problem löst, sondern auch, ob und wie schnell.
Turing 1936
Alan Turing veröffentlichte 1936 den Aufsatz „On Computable Numbers, with an Application to the Entscheidungsproblem“. Er beschrieb eine idealisierte Rechenmaschine, die Turing-Maschine, als Modell dafür, was ein Mensch mit einem exakt vorgegebenen Verfahren ausrechnen kann. Mit diesem Modell zeigte er, dass es keinen mechanischen Prozess geben kann, der alle mathematischen Fragen entscheidet. Die Church-Turing-These besagt, dass jede Funktion, die sich mechanisch berechnen lässt, von einer Turing-Maschine berechnet werden kann. Sie ist eine These und kein beweisbarer Satz, weil „mechanisch berechenbar“ kein formal definierter Begriff ist.
Warum das für die Praxis zählt
- Es gibt Probleme, für die kein Algorithmus existieren kann (Unentscheidbarkeit).
- Es gibt Probleme, die lösbar, aber in der Praxis zu langsam sind.
- Jede Programmiersprache kann im Prinzip dasselbe berechnen; Unterschiede liegen in Komfort und Geschwindigkeit, nicht in der Berechenbarkeit.
Ein einfaches Beispiel: Suchen
Gesucht wird ein Name in einer Liste mit n Einträgen. Die lineare Suche prüft Eintrag für Eintrag – im schlechtesten Fall n Schritte. Ist die Liste sortiert, halbiert die binäre Suche den Suchbereich in jedem Schritt: Bei 1.000.000 Einträgen genügen etwa 20 Schritte (220 ≈ 1.048.576).
def binaere_suche(liste, ziel):
unten, oben = 0, len(liste) - 1
while unten <= oben:
mitte = (unten + oben) // 2
if liste[mitte] == ziel:
return mitte
if liste[mitte] < ziel:
unten = mitte + 1
else:
oben = mitte - 1
return -1
Der Unterschied zwischen n und etwa log₂ n Schritten ist das, was man mit „Komplexität“ meint.
Frage bei jedem Problem zwei Dinge: Gibt es einen Algorithmus – und wie wächst sein Aufwand mit der Eingabe?
Zum Selbermachen
- Führe die binäre Suche von Hand für die Liste 2, 5, 8, 12, 16, 23, 38 und das Ziel 23 durch.
- Schätze, wie viele Schritte eine lineare Suche bei 1.000.000 Einträgen im schlechtesten Fall braucht.
Verwandte Themen
Rechner → „Von-Neumann-Architektur“. KI → Maschinelles Lernen erzeugt Verfahren aus Daten, bleibt aber an dieselben Grenzen der Berechenbarkeit gebunden.
Prüfstatus: Belegt (Stand 1. Oktober 2026): Turings Aufsatz von 1936, die Idee der Turing-Maschine, das Ergebnis zum Entscheidungsproblem und die Formulierung der Church-Turing-These wurden gegen Fachquellen (u. a. Stanford Encyclopedia of Philosophy) geprüft. Nicht einzeln belegt: die Rechnung zur binären Suche (nachrechenbar), das Codebeispiel (konstruiert, nicht ausgeführt) und die Aussage zur Gleichwertigkeit von Programmiersprachen (verbreitete Lehrmeinung).
Quellen
- Alan M. Turing – „On Computable Numbers, with an Application to the Entscheidungsproblem“ (Proceedings of the London Mathematical Society, 1936)
- Stanford Encyclopedia of Philosophy – „The Church-Turing Thesis“
Die Von-Neumann-Architektur
Begriffe vorab
- CPU: Zentrale Recheneinheit: führt Befehle aus.
- Arbeitsspeicher: Speicher für Programme und Daten während der Ausführung.
- Befehlszyklus: Ablauf aus Holen, Dekodieren und Ausführen eines Befehls.
- Stored-Program: Programme liegen wie Daten im Speicher.
- Ein-/Ausgabe: Schnittstellen zu Tastatur, Bildschirm, Netzwerk und Speichermedien.
Ein Papier von 1945
Am 30. Juni 1945 verbreitete John von Neumann das 107 Seiten lange „First Draft of a Report on the EDVAC“. Es beschrieb erstmals ausführlich einen Rechner, bei dem Programm und Daten im selben Speicher liegen (Stored-Program-Prinzip). Die Bezeichnung „Von-Neumann-Architektur“ ist umstritten, weil der Bericht die Beiträge von John Mauchly und J. Presper Eckert nicht nennt.
Die Bausteine
- Rechenwerk (arithmetisch-logische Einheit): führt Rechen- und Vergleichsoperationen aus.
- Steuerwerk: liest Befehle und koordiniert den Ablauf.
- Speicher: hält Befehle und Daten.
- Ein- und Ausgabe: verbindet den Rechner mit der Außenwelt.
In heutigen Prozessoren sind Rechen- und Steuerwerk in der CPU vereint.
Der Befehlszyklus
- Holen: Der nächste Befehl wird aus dem Speicher gelesen.
- Dekodieren: Die Steuerung ermittelt, was zu tun ist.
- Ausführen: Das Rechenwerk führt aus; Ergebnisse gehen in Register oder Speicher.
Dann beginnt der Zyklus von vorn. Alles, was ein Rechner tut, besteht letztlich aus diesen Schritten – nur sehr schnell und sehr oft.
Folgen des Stored-Program-Prinzips
Weil Programme Daten sind, kann man Programme laden, ändern und übersetzen (ein Compiler ist ein Programm, das Programme erzeugt). Das Prinzip hat auch eine Kehrseite: Wenn Daten als Programm ausgeführt werden können, entstehen Angriffsmöglichkeiten wie Code-Einschleusung. Das ist ein Grund für Schutzmechanismen, die Datenbereiche von ausführbaren Bereichen trennen – eine Parallele zu Injection-Angriffen im Web, wo Daten als Befehl interpretiert werden.
Beispiel: Zwei Zahlen addieren
Ein Programm liegt als Befehlsfolge im Speicher: „Lade Zahl A in ein Register, lade Zahl B, addiere, speichere das Ergebnis“. Die CPU holt Befehl für Befehl, das Rechenwerk addiert, das Ergebnis wandert zurück in den Speicher.
Denke Hardware in Schichten: Befehle sind die unterste Software-Ebene, auf der alles Weitere aufbaut.
Zum Selbermachen
- Beschreibe den Befehlszyklus für das Programm „c = a + b“ in fünf Schritten.
- Suche heraus, wie viel Arbeitsspeicher und wie viele Kerne dein Rechner hat.
Verwandte Themen
Rechner → „Das Betriebssystem als Vermittler“. Security → „Injection, XSS und CSRF“ (Daten werden als Befehl behandelt).
Prüfstatus: Belegt (Stand 1. Oktober 2026): Das Datum 30. Juni 1945, der Umfang von 107 Seiten, das Stored-Program-Prinzip und die Namenskontroverse (Mauchly, Eckert) wurden gegen Fachquellen zum EDVAC-Bericht geprüft. Nicht einzeln belegt: die Beschreibung der Bausteine und des Befehlszyklus (Standarddarstellung in Lehrbüchern, hier nicht gegen ein einzelnes Lehrbuch geprüft) und die Parallele zu Injection (eigene Einordnung).
Quellen
- John von Neumann – „First Draft of a Report on the EDVAC“ (30. Juni 1945)
Das Betriebssystem als Vermittler
Begriffe vorab
- Betriebssystem: Software, die Hardware verwaltet und Programmen Dienste anbietet.
- Kernel: Kern des Betriebssystems mit Zugriff auf die Hardware.
- Prozess: Laufendes Programm mit eigenem Speicher.
- Systemaufruf: Anforderung eines Programms an den Kernel.
- Virtueller Speicher: Abstraktion, die jedem Prozess einen eigenen Adressraum vorspiegelt.
Wozu ein Betriebssystem?
Ohne Betriebssystem müsste jedes Programm Festplatte, Netzwerkkarte und Bildschirm selbst ansprechen und sich mit allen anderen Programmen abstimmen. Das Betriebssystem übernimmt das: Es verwaltet Ressourcen (Prozessor, Speicher, Geräte) und stellt einheitliche Schnittstellen bereit. Programme sehen „Dateien“ und „Netzwerkverbindungen“ statt Plattenblöcken und Netzwerkpaketen – das ist Abstraktion.
Kernel und Benutzerprogramme
Der Kernel läuft im privilegierten Modus und hat Zugriff auf die Hardware. Normale Programme laufen im Benutzermodus mit eingeschränkten Rechten. Wollen sie etwas, das nur der Kernel darf (Datei öffnen, Daten senden), stellen sie einen Systemaufruf. So kann ein fehlerhaftes Programm nicht ohne Weiteres das ganze System lahmlegen.
Prozesse und Scheduling
Auf einem Rechner laufen viele Prozesse, aber nur wenige Prozessorkerne. Der Scheduler des Kernels teilt Rechenzeit zu und wechselt blitzschnell zwischen Prozessen. Für jedes Programm entsteht der Eindruck, es habe den Rechner für sich.
Virtueller Speicher
Jeder Prozess bekommt einen eigenen Adressraum. Der Kernel bildet ihn auf den tatsächlichen Arbeitsspeicher ab und kann Teile bei Bedarf auf Festplatte auslagern. Das schützt Prozesse voreinander und erlaubt es, mehr Speicher zu nutzen, als physisch vorhanden ist.
Das Betriebssystem als Schichtenmodell
Edsger Dijkstra beschrieb 1968 im Aufsatz „The Structure of the THE-Multiprogramming System“ (Communications of the ACM 11(5)) ein System mit Schichten, bei dem höhere Schichten nur von niedrigeren abhängen. Die unterste Schicht verwaltet den Prozessor, die nächste den Speicher; darüber muss sich niemand mehr um die Zahl der Prozessoren kümmern. In demselben Aufsatz führte Dijkstra die Semaphore als Mittel der Synchronisation ein. Das Schichtenprinzip prägt seither Betriebssysteme – und Netzwerke.
Beispiel: Eine Datei speichern
Ein Textprogramm ruft „Datei schreiben“ auf. Der Kernel prüft Rechte, übergibt die Daten an den Dateisystemtreiber, dieser an den Gerätetreiber, und der schreibt auf den Datenträger. Das Textprogramm weiß nichts von Blöcken oder Controllern.
Jede Schicht kennt nur die Schicht direkt unter sich – das macht Systeme änderbar, ohne dass alles zerbricht.
Zum Selbermachen
- Öffne den Task-Manager oder das Aktivitätsprotokoll und zähle die laufenden Prozesse.
- Nenne drei Dienste, die dein Betriebssystem für Programme anbietet, ohne dass die Programme Hardware kennen müssen.
Verwandte Themen
Rechner → „Von-Neumann-Architektur“. Schichtenmodelle → „Das Schichtenprinzip“. Security → Rechtetrennung folgt dem Prinzip der geringsten Rechte („Entwurfsprinzipien“).
Prüfstatus: Belegt (Stand 1. Oktober 2026): Dijkstras Aufsatz (Communications of the ACM, Band 11, Heft 5, 1968, S. 341–346), die Schichtstruktur mit Prozessorverwaltung unten und Speicherverwaltung darüber sowie die Einführung der Semaphoren wurden gegen Fachquellen und das Dijkstra-Archiv geprüft. Nicht einzeln belegt: die Beschreibung von Kernel, Systemaufruf, Scheduling und virtuellem Speicher (allgemeines Grundlagenwissen aus Lehr- und Fachtexten, nicht gegen ein einzelnes Lehrbuch geprüft) und das Dateibeispiel (didaktisch vereinfacht).
Quellen
- Edsger W. Dijkstra – „The Structure of the ‚THE‘-Multiprogramming System“ (Communications of the ACM 11(5), 1968, S. 341–346)