Algorithmen und Computer

Es werden die grundlegenden Eigenschaften eines Algorithmus erläutert und der Computer als Maschine vorgestellt, die in der Lage ist, jeden beliebigen Algorithmus abzuarbeiten.

walter
ALU Berechenbarkeit Maschinensprache höhere Programmiersprache Algorithmus Computer
Inhaltsverzeichnis

Einordnung des Artikels

Was ist ein Computer?

Aufgabe:

Computer werden heute für unzählige Aufgaben eingesetzt. Versuchen Sie dennoch prägnant zu formulieren:

Was ist die primäre Aufgabe eines Computers?

Vorläufige Definition von Algorithmus und einfache Beispiele

Beispiele:

  1. Kochbuch
  2. Anweisungen auf Bildern in einer Telephonzelle zum Benützen des Telephons
  3. Verfahren zum schriftlichen Multiplizieren zweier Zahlen (siehe Abbildung 1)
  4. Primzahltest für eine natürliche Zahl.

Charakteristische Merkmale von Algorithmen:

Erste saloppe Definition:

Algorithmus = Regeln, Vorschriften oder Verfahrensanweisungen zur Lösung eines schwierigen Problems durch einfachere Lösungsschritte.

Aufgaben

1. Verzinsung:

Das Kapital K soll n Jahre bei einem Zinssatz p (in Prozent) verzinst werden und zwar

  1. Wie groß ist in beiden Fällen das Kapital nach i = 1, ... , n Jahren? (im ersten Fall werden die ausgeschütteten Zinsen zum Kapital gezählt.) Wie groß ist die Differenz?
  2. Formulieren Sie einen Algorithmus (mit Eingaben, Berechnungen, Ausgaben), der sämtliche Ergebnisse berechnet!

2. Schriftliches Multiplizieren zweier Zahlen:

  1. Formulieren Sie den Algorithmus, der dem schriftlichen Multiplizieren zugrunde liegt. Achten Sie dabei darauf, den Algorithmus so zu formulieren, dass zwei beliebige ganze Zahlen multipliziert werden können (also auch Zahlen beliebiger Stellen-Anzahl).
  2. Wie muss man den Algorithmus abändern, um auch Zahlen mit Nachkommastellen zu multiplizieren?
  3. Geben Sie eine Begründung an, warum der Algorithmus das richtige Ergebnis liefert.

3. Umrechnen von Dualzahlen ins Zehnersystem:

  1. Rechnen Sie die Dualzahl (1001 1101)2 in eine Zahl im Zehnersystem um.
  2. Formulieren Sie Ihre Vorgehensweise als Algorithmus, und zwar so, dass man mit dem Algorithmus eine beliebige Dualzahl ins Zehnersystem umrechnen kann.

4. Umrechnen einer Zahl aus dem Zehnersystem ins Hexadezimalsystem:

Die folgenden Anweisungen ergeben einen Algorithmus, mit dem man eine Zahl aus dem Zehnersystem in eine Hexadezimalzahl (Zahl im 16-System) umrechnen kann. Im Hexadezimalsystem laufen die Ziffern nicht mehr von 0 bis 9, sondern von 0 bis 15; um eindeutig zu erkennen, ob etwa mit 15 eine zweistellige Zahl oder eine Ziffer gemeint ist, werden die zweistelligen Ziffern durch Buchstaben ersetzt, einstellige Ziffern bleiben unverändert.

Algorithmus zum Umrechnen einer Zahl Z (im Zehnersystem) in das Hexadezimalsystem:

Berechnen Sie die zu 16, 159, 160, 255, 256, 4003 gehörigen Hexadezimalzahlen nach diesem Algorithmus.

5. Umrechnen vom Hexadezimalsystem ins Dualsystem und umgekehrt:

  1. Schreiben Sie die Potenzen von 16 und von 2 auf. Welche Auffälligkeiten erkennen Sie an den Listen? Warum treten diese Auffälligkeiten bei der Liste der Potenzen von 10 und 2 nicht auf?
  2. Formulieren Sie, wie die Gleichung 24 zu einer Verwandtschaft der Zahlensysteme zur Basis 2 und 16 führt!
  3. Geben Sie einen Algorithmus an, mit man eine beliebige Dualzahl in eine Hexadezimalzahl umrechnen kann (und der sich diese Verwandtschaft zunutze macht)!
  4. Geben Sie einen Algorithmus für die umgekehrte Umrechnung an (vom Hexadezimalsystem in Dualsystem)!

Hinweis: Ausführliche Erklärungen zu den letzten Aufgaben finden sich in Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem.

Berechenbarkeit

In der ersten Hälfte des 20. Jahrhunderts gab es zahlreiche — sehr abstrakte — Untersuchungen, welche Probleme der Mathematik mit Hilfe eines Algorithmus gelöst werden können. Dazu muss natürlich genauer als bisher gesagt werden, was unter einem Algorithmus zu verstehen ist. All die Überlegungen aus dieser Zeit können hier unmöglich aufgegriffen und nachvollzogen werden.

Aber die wichtigsten Ergebnisse können mitgeteilt werden:

Es gibt tatsächlich Funktionen oder mathematische Probleme, die nicht mit Hilfe eines Algorithmus in den Griff zu kriegen sind. Einige Beispiele folgen unten; wie man sehen wird, handelt es sich großteils um akademische Probleme, an denen ein Praktiker kaum interessiert ist. Sie haben eine ähnliche Struktur wie der Barbier, der behauptet:

Ich bin der einzige Barbier hier im Dorf und rasiere alle Männer im Dorf, die sich nicht selbst rasieren.

Das Beispiel stammt von Bertrand Russell. Es hört sich einfach und klar an. Aber: Wer rasiert den Barbier?

Die Paradoxie hat nichts mit unendlichen Mengen zu tun, mit denen sich viele Paradoxien bilden lassen, wie etwa die Frage von Galilei:

Gibt es mehr natürliche Zahlen oder Quadratzahlen von natürlichen Zahlen?

Einerseits ist die Menge der Quadratzahlen eine echte Teilmenge der natürlichen Zahlen — es gibt also weniger Quadratzahlen als natürliche Zahlen. Andererseits gibt es zu jeder natürlichen Zahl auch eine Quadratzahl — also gibt es gleich viele Quadratzahlen und natürliche Zahlen.

Die Paradoxie des Barbiers bleibt bestehen, auch wenn sein Dorf nur endlich viele Bewohner hat.

Einige Probleme, die sich algorithmisch nicht lösen lassen:

1. Halteproblem:

Zu einem gegebenen Algorithmus A kann man einen weiteren Algorithmus H(A) entwerfen, der entscheidet, ob der Algorithmus A nach endlich vielen Rechenschritten zu einem Ende kommt oder unendlich lange rechnet.

Als Beispiel denke man an das Multiplizieren von ganzen Zahlen. Aus der Länge der gegebenen Zahlen kann man schließen, wie viele Rechenschritte nötig sind, um zum Ergebnis zu kommen — der Algorithmus ist endlich.

Der folgende kleine Algorithmus, der die Menge der geraden Zahlen erzeugt, kommt dagegen zu keinem Ende:

Setze n = 0
Bilde n = n + 2 bis eine Zahl n entsteht mit n < 0.

Da durch die wiederholte Addition von 2 (ausgehend von n = 0) immer positive Zahlen gebildet werden, bricht die Berechnung niemals ab.

Das sogenannte Halteproblem entsteht dann, wenn man den Algorithmus H nicht nur auf einen gegebenen Algorithmus anwenden möchte, sondern für jeden beliebigen Algorithmus A entscheiden möchte, ob er nach endlich vielen Rechenschritten zu einem Ende kommt oder nicht.

Hat man diesen allgemeinen Algorithmus H gefunden, kann man ihn auch auf den Algorithmus H, also sich selbst anwenden: H(H) — aber jetzt läuft man wieder in die Paradoxie des Barbiers; den allgemeinen Algorithmus H kann es nicht geben.

2. Programmverifikation:

Wünschenswert in vielen Fällen wäre folgender Algorithmus PV, der als Programmverifikation bezeichnet wird:

Gegeben ist

Der Algorithmus PV soll prüfen, ob der Algorithmus A die Spezifikation S tatsächlich erfüllt oder nicht. Warum es wünschenswert ist den Algorithmus PV zu verwenden ist klar: jeder Programmierer könnte damit sofort und automatisch überprüfen lassen, ob sein Programm fehlerfrei ist.

Im Beispiel der Multiplikation zweier Zahlen würde die Spezifikation vorgeben:

Auch den Algorithmus PV kann es nur für spezielle Algorithmen (und ihrer Spezifikation), aber nicht für beliebige Algorithmen (und ihrer Spezifikation) geben; man kann zeigen, dass das Problem der Programmverifikation dann zugleich das Halteproblem lösen würde (man muss nur die Spezifikation entsprechend formulieren).

---

Alan Turing hat 1936 eine Definition vorgeschlagen, welche Funktionen als berechenbar gelten sollen, nach seiner Definition waren es alle Funktionen, die sich mit Hilfe einer Turing-Maschine berechnen lassen. Später wurden mehrere Alternative für die Turing-Maschine vorgeschlagen, es hat sich aber herausgestellt, dass sie alle gleich mächtig sind — also alle dieselben Funktionen berechnen können.

Durch diese Untersuchungen lassen sich inzwischen sehr gut die berechenbaren Funktionen charakterisieren und man geht davon aus, dass

die Klasse der von Turing-Maschinen berechenbaren Funktionen mit der Klasse der intuitiv berechenbaren Funktionen übereinstimmt.

Diese Aussage wird als die Church-Turing-These bezeichnet und ist deshalb eine These, weil nicht klar definiert werden kann, was die Klasse der intuitiv berechenbaren Funktionen sein soll — salopp gesagt sind es die Funktionen, mit denen man sich üblicherweise in der Mathematik beschäftigt und nicht die oben besprochenen akademischen Ausnahmen.

Die Komplexität von Algorithmen

Aber auch für die oben als intuitiv berechenbar bezeichneten Funktionen gibt es ein prinzipielles Problem: oft ist die Zeitdauer, die die Ausführung des Algorithmus benötigt — selbst mit den besten aktuell verfügbaren Rechnern — in der Größenordnung von Jahren oder Jahrhunderten.

Die meisten heute verwendeten Verschlüsselungsverfahren beruhen darauf, dass ein Angreifer eigentlich jede Nachricht entschlüsseln kann, die erforderliche Zeit aber in keinem Verhältnis zum Nutzen steht.

Aufgaben:

1. Multiplikation

Betrachten Sie die Abbildung 1, in der zwei vierstellige Zahlen multipliziert werden. Bezeichnet man die Multiplikation oder Addition zweier einstelliger Zahlen als elementare Operation. Wie viele solche elementare Operationen sind zur Multiplikation zweier n-stelliger Zahlen nötig? Geben Sie das Ergebnis in Abhängigkeit von n an!

2. Schachspiel

In einer typischen Stellung auf dem Schachbrett sind etwa 30 mit den Regeln vereinbare Züge möglich. Wie viele mögliche Zugfolgen gibt es, wenn jede Seite (also Weiß und Schwarz) n-mal zieht? Geben Sie die Zahlen für n = 5, 10, 20, 30 an.

Wie lange dauern diese Berechnungen, wenn man annimmt, dass für eine Zugfolge 1 ns (eine Nanosekunde) benötigt wird?

Da Weiß eine Schachpartie beginnt, hat er einen kleinen Vorteil. Warum gilt das Problem

Kann Weiß eine Schachpartie selbst bei bester Verteidigung von Schwarz zwingend gewinnen?

als unlösbar?

Die primäre Aufgabe des Computers

Nachdem geklärt, dass bis auf einige akademische Probleme alle praktisch relevanten Funktionen berechenbar sind, und eine zentrale Eigenschaft eines Algorithmus ist, dass ein komplexes Problem auf elementare Rechenschritte zurückgeführt wird, ist es naheliegend, eine Maschine zu bauen, die diese elementaren Rechenschritte ausführen kann. Möchte man eine Funktion berechnen, benötigt man nur noch jemanden, der das zu lösende Problem auf diese Rechenschritte herunterbricht — das zu lösende Problem also in einen Algorithmus übersetzt.

In diesem Sinne ist der Computer eine universelle Maschine, die in der Lage ist einen beliebigen Algorithmus auszuführen — man muss den Algorithmus nur so aufbereiten, dass ihn der Computer abarbeiten kann.

Die Arithmetic and Logic Unit (ALU)

Um seine Aufgabe zu erfüllen, sind im Computer elektrische Schaltungen eingebaut, mit deren Hilfe die elementaren Rechenschritte eines Algorithmus berechnet werden. Diese Schaltungen realisieren zum Beispiel logische Operationen (wie logisches UND, logisches ODER, Vergleiche zwischen Zahlen) oder Rechenoperationen (Addition, Subtraktion, Multiplikation, Komplementbildung). Die Schaltungen werden zur sogenannten Arithmetic and Logic Unit (kurz ALU) zusammengefasst.

In der Anfangszeit der Computertechnik waren die elektrischen Schaltungen durch Röhren und Relais realisiert, heute sind sie mit Transistoren realisiert. Die Größe der ALU war anfangs die eines Zimmers, heute (in einem PC) etwa die einer zusammengedrückten Streichholzschachtel.

Maschinensprache und höhere Programmiersprachen

Um die elektrischen Schaltungen in der ALU ansprechen zu können, muss der Algorithmus genau auf diejenigen logischen und arithmetischen Operationen heruntergebrochen werden, die in der ALU realisiert sind. Die Sprache, die über diesen Befehlsvorrat verfügt, nennt man die Maschinensprache. Für einfache Aufgaben mag die Maschinensprache ausreichend sein, bei komplexen Problemen werden die Algorithmen schnell unübersichtlich groß und sind vom Menschen nicht mehr beherrschbar.

Daher erfolgt die Programmierung eines Algorithmus (bis auf wenige Ausnahmefälle) nicht in der Maschinensprache, sondern in sogenannten höheren Programmiersprachen. Sprachen wie BASIC, PASCAL, C, C++, Java sind Beispiele für höhere Programmiersprachen.

Der Quelltext, der in der höheren Programmiersprache geschrieben wird, ist zunächst eine Textdatei, die dann vom Compiler in die Maschinensprache übersetzt wird. Der Compiler ist selbst ein Programm, das zuerst prüft, ob im Quelltext die Sprachregeln eingehalten wurden (die Spezifikation kann der Compiler nicht prüfen). Falls nicht, gibt er eine Fehlermeldung aus, die den Programmierer auffordert sein Programm zu korrigieren. Ist das Programm fehlerfrei, wird es in den sogenannten Maschinencode übersetzt; das ist das Programm, das vom Computer ausgeführt werden kann. Sie kennen den Maschinencode vermutlich als .exe-Datei.

Eine höhere Programmiersprache bietet (unter anderem) folgende Sprachelemente an:

  1. Definition von Variablen mit zugehörigen Datentypen
  2. Wertzuweisung an Variablen
  3. Ausführen von Rechenoperationen und logischen Operationen
  4. Weitere Kontrollstrukturen (wie Bedingungen, Schleifen)
  5. Bündeln von Operationen zu Unterprogrammen.

Zur Erläuterung — im Detail sind die folgenden Ausführungen für jede Programmiersprache ein wenig anders, in grober Betrachtung bieten aber alle Sprachen die identischen Elemente an:

1. Variable

Variablen verwendet man, um Objekte zu simulieren, deren Wert sich im Lauf der Ausführung des Programmes verändert (ein Beispiel ist das Kapital im Algorithmus oben, der die Verzinsung berechnet). Von den Eigenschaften der Variable hängt es ab, welchen Datentyp sie erhalten wird; es gibt zum Beispiel ganze Zahlen (integer), Zahlen mit Nachkommastellen (double), Zeichen (char), Zeichenketten (String).

2. Wertzuweisung

Erst die Möglichkeit, den Variablen einen Wert zuzuweisen — und dies an beliebigen Stellen im Programm -, also nicht nur mit Konstanten zu arbeiten, erlaubt dynamisches Verhalten eines Programmes. Als Beispiel diene das Kapital im Beispiel der Verzinsung.

3. Rechenoperationen und logische Operationen

Die Überlegungen zum Thema Berechenbarkeit haben gezeigt, dass eigentlich sehr elementare Rechenoperationen ausreichen, um jeden Algorithmus zu verwirklichen. Ein weit verbreitetes Vorurteil ist, dass es zu jedem Problem eine (oder sogar nur eine) geeignete Programmiersprache gibt. Das ist natürlich falsch, denn jede Programmiersprache erlaubt, jeden beliebigen Algorithmus zu schreiben; sie unterscheiden sich nur darin, wie angenehm die Arbeit für den Programmierer ist — und dies hängt zum Teil davon ab, welche Operationen und Kontrollstrukturen eine Sprache anbietet.

Eine Programmiersprache, die es nicht erlaubt, beliebige Algorithmen zu schreiben, sollte man auch nicht als Programmiersprache bezeichnen. Zum Beispiel werden Auszeichnungssprachen (wie HTML oder LaTeX) oder Datenbank-Abfragesprachen (wie SQL) gerne als Programmiersprachen bezeichnet — mit diesen Sprachen kann man aber nicht frei programmieren. Ihr Befehlsvorrat ist gegenüber einer Programmiersprache so weit eingeschränkt, dass man nicht mehr jeden Algorithmus verwirklichen kann.

4. Kontrollstrukturen Kontrollstrukturen werden in der Einführung zur Programmierung noch ausführlich behandelt (siehe Strukturelemente von Algorithmen). Zunächst sollte man dabei an Konstrukte wie Bedingungsprüfung, Alternative oder Schleifen denken.

Bedingungsprüfung hat die Bedeutung, dass eine Anweisung A nur dann ausgeführt wird, wenn eine gewisse Bedingung erfüllt ist:

IF (Bedingung)
    THEN (Anweisung A)
Anweisung B

Die folgende Anweisung B wird immer ausgeführt — egal, ob die Bedingung eingetreten war oder nicht.

Alternative: Sie hat meist die Gestalt

IF (Bedingung)
    THEN (Anweisung A)
    ELSE (Anweisung B)

Falls eine gewisse Bedingung erfüllt ist, wird die Anweisung A ausgeführt, ist die Bedingung nicht erfüllt, wird B ausgeführt.

Schleifen: Dabei denke man an folgendes Beispiel.

Von einer Gruppe von Personen sollen die Personalien aufgenommen werden.

Man kann das Problem in zwei Teilprobleme zerlegen:

Das erste Problem führt vermutlich zu einem Unterprogramm (siehe unten); das zweite Problem erfordert eine Schleife, die dafür sorgt, dass nacheinander alle Personen abgearbeitet werden (und dabei jedes Mal das Unterprogramm aufgerufen wird) und danach die Schleife verlassen wird.

5. Unterprogramme

Diese letzte Eigenschaft wirkt unscheinbar, macht aber gerade die Mächtigkeit einer höheren Programmiersprache im Vergleich zur Maschinensprache aus. Denn in der Maschinensprache müssen bei jedem Algorithmus, den man schreibt, die Befehle, die man eigentlich einsetzen möchte, von Neuem auf die elementaren Rechenschritte heruntergebrochen werden, die der Computer versteht. In einer höheren Programmiersprache kann man komplexe Operationen zu einer neuen Funktion oder einem Unterprogramm zusammenfassen und diese können nach Belieben später — auch in anderen Programmen — wiederverwendet werden. Und diese Unterprogramme können dann thematisch geordnet zu Bibliotheken zusammengefasst werden, die dem Programmierer später zahlreiche Service-Funktionen anbieten — in der Maschinensprache wird er immer von vorne anfangen müssen.

Als Beispiel diene obiger Algorithmus zum Umrechnen einer Zahl aus dem Zehnersystem in das Hexadezimalsystem. Bietet eine Programmiersprache diese Funktion nicht als elementare Operation an, so kann der Algorithmus — einmal geschrieben — abgespeichert und immer wieder verwendet werden.

Man kann den Unterschied zwischen Maschinensprache und höherer Programmiersprache vielleicht auch so formulieren: Die Maschinensprache ist an den Computer angepasst, der umso einfacher ist, je elementarer die Operationen sind, die er ausführt. Mit den höheren Programmiersprachen versucht man die Entwicklung von Algorithmen an die menschliche Denkweise anzupassen; sie beruht darauf, dass man abstrahieren kann und größere Einheiten (Module) bilden kann, deren genauen Inhalt man nicht kennen muss, man aber weiß, wie sie einzusetzen sind.

Die obigen Sprachelemente einer höheren Programmiersprache sollten verdeutlichen, wie ein Programmierer denkt. Im Vergleich dazu ist die Maschinensprache auf sehr einfache Befehle beschränkt; es handelt sich vor allem um logische Operation und Grundrechenarten. Der folgende Abschnitt Logische Operationen und Schaltnetze soll einen Eindruck vermitteln, um welche Befehle es sich dabei handelt und wie ihre Ausführung im Computer realisiert ist.