Algorithmus

Ein Abakus besteht im Wesentlichen aus vertikal angeordneten Sprossen, auf denen verschiebbare Perlen befestigt sind. Beim chinesischen suan pan sitzen auf je einer Sprosse im oberen Bereich zwei Perlen; im unteren Bereich befinden sich auf jeder der Sprossen fünf Perlen. Ordnet man nun diese Perlen auf bestimmte Weise an, so lassen sich in eindeutiger Weise Zahlen darstellen. Die folgenden Beispiele zeigen, wie das geht:

Zu jeder zulässigen Perlenanordnung gehört ein bestimmter Zahlenwert, wobei das dritte und das vierte Beispiel zeigen, dass die Umkehrung dieser Aussage nicht richtig ist. Wenn man alle Sprossenspalten von rechts nach links mit 0 bis 6 durchnummeriert, dann kann man mit einem solchen 7-sprossigen Abakus alle natürlichen Zahlen zwischen 0 und 16666665 darstellen und innerhalb dieses Zahlenraums addieren und subtrahieren, wenn folgende Regeln beachtet werden:

Normalerweise werden die Perlen eines Abakus mit Daumen und Zeigefinger verschoben. Bei dem hier mithilfe von JavaScript implementierten Abakus (-> Quelltext) muss man mit dem Mauszeiger die Perlen anklicken:

Wahrscheinlich wurde der Abakus in dieser Form ein paar Jahrhunderte v. Chr. erfunden, nachdem zuvor beispielsweise mit Steinchen im Sand oder mit Stäbchen auf Rechenbrettern gerechnet wurde. Noch heute wird der Abakus als Rechenhilfsmittel vor allem in Asien verwendet. Selbst für das Multiplizieren und das Dividieren kann ein Abakus (mit genügend vielen Sprossen) gute Dienste leisten.

Man rechnet immer dann mit dem Abakus richtig, wenn zunächst durch entsprechendes Verschieben der Perlen die Eingangsdaten korrekt dargestellt werden, zweitens beim Bearbeiten der gestellten Rechenaufgabe die Regeln für das Verschieben der Perlen beachtet werden und drittens das Rechenergebnis vom Abakus fehlerfrei abgelesen wird.

Eine Folge von Anweisungen, nach denen man unter Vorgabe von Eingangsdaten eine bestimmte Ausgabe erhält, nennt man Algorithmus. Genauer:

Eine zur Lösung einer Klasse gleichartiger Probleme präzis formulierte Handlungsanweisung, die bei vorgegebenen Eingangsdaten eines festgelegten Typs mit Hilfe bekannter Regeln und unter Benutzung genau beschriebener Hilfsmittel unter Beachtung von Randbedingungen zu einem bestimmten Ergebnis führt, heißt Algorithmus.

Ein solcher Algorithmus, der zumeist aus einer Folge einzelner Anweisungen besteht, muss in einer Sprache verfasst sein, die der ausführende Mensch oder die ausführende Maschine verstehen und interpretieren kann.

Ein Algorithmus, der nach endlich vielen Schritten beendet ist, heißt terminierend. Wenn die Schrittfolge eines Algorithmus eindeutig festgelegt ist, so handelt es sich um einen deterministischen Algorithmus.

Ist das Ergebnis eines Algorithmus eindeutig bestimmt, so heißt dieser Algorithmus determiniert.

In der Grundschule lernt man, zwei Dezimalzahlen a und b miteinander schriftlich zu multiplizieren, und das geht so:

Dieses Multiplikationsverfahren funktioniert wegen der Rechenregeln bezüglich der Addition und der Multiplikation auf ℕ, der Menge der natürlichen Zahlen. Die erste vorgegebene Zahl asei m-stellig, die zweite Zahl bsei n-stellig, das heißt a = a₀·10⁰ + a₁·10¹ + ... + a_m-1·10^m-1und b = b₀·10⁰ + b₁·10¹ + ... + b_n-1·10^n-1. Dann gilt

Im Rechenbeispiel gilt a₀ = 2; a₁ = 8; a₂ = 1; a₃ = 4 bzw. b₀ = 7; b₁ = 3; b₂ = 6 und es ist a·b₀·10⁰ = 29274; a·b₁·10¹ = 12546 und a·b₂·10² = 25092.

Jeder Summand a·b_i·10ⁱ lässt sich für 0 ≤ i ≤ n-1 in die folgende Form bringen:

a·b_i·10ⁱ = (b_i·a₀·10⁰ + b_i·a₁·10¹ + ... + b_i·a_m-1·10^m-1)·10ⁱ

Die Aufgabe, eine m-stellige Dezimalzahl a mit einer n-stelligen Dezimalzahl b zu multiplizieren, erledigt man nach dem vorgestellten Verfahren durch n Multiplikationen der Zahl a mit 1-stelligen Dezimalzahlen, die den jeweiligen Ziffern der Zahl b entsprechen. Jede dieser n Multiplikationen führt dann zum richtigen Ergebnis, wenn man das kleine Einmaleins und das Addieren von 1-stelligen Dezimalzahlen unter Beachtung von Überträgen beherrscht. Der Wert von a·b ergibt sich schließlich durch Addition aller n Einzelergebnisse.

Für eine (mxn)Multiplikation einer m-stelligen Dezimalzahl a mit einer n-stelligen Dezimalzahl b benötigt man n (mx1)Multiplikationen mit jeweils höchstens 2m+1 elementaren Schritten (Multiplizieren bzw. Addieren zweier einstelliger Zahlen) und ungefähr m·n elementare Rechenschritte für das Addieren der n Einzelergebnisse, das sind insgesamt n·(2m+1) + m·n Schritte, also n·(3m+1) Schritte. Eine Verdoppelung der Ziffernanzahl beider Zahlen a und b ergibt demnach ungefähr eine Vervierfachung des Rechenaufwands bei der schriftlichen Multiplikation von a und b.

Der schottische Mathematiker Lord John Napier (1550 - 1617) hat ein Verfahren entwickelt, mit dem man unter anderem die Multiplikation einer m-stelligen Dezimalzahl mit einer 1-stelligen Dezimalzahl auf mechanische Art bewerkstelligen kann.

Auf den Napier'schen Rechenstäben sind untereinander Quadrate angeordnet, auf denen insgesamt alle Zahlen der Einmaleins-Reihen notiert sind, und zwar nach folgendem System:

Die Funktionsweise des Napier'schen Multiplikationsverfahrens erschließt man sich am besten anhand eines Beispiels:

Die Idee, Multiplikationen mithilfe diagonal strukturierter Gittermuster durchzuführen, stammt nicht von Napier selbst, sondern ist wesentlich älter. Zur Zeit Napiers war es üblich, zwei mehrstellige Dezimalzahlen nach der vermutlich aus Indien stammenden Gelosia-Methode auf schriftlichem Wege zu multiplizieren.
Ein Beispiel: 3716·297 = ?

Die Ziffern des Produktwertes ergeben sich durch Addieren der entsprechenden Diagonalzahlen:

Unter Benutzung des Prinzips der Napier'schen Rechenstäbe hat Wilhelm Schickard (1592 - 1635), Professor an der Universität Tübingen, 1623 die erste mechanische Rechenmaschine konstruiert. Wesentlicher Bestandteil dieser Maschine war das Addierwerk, in das die Teilergebnisse der (mx1)Multiplikationen vom Benutzer der Maschine übertragen werden mussten.

Die von Schickard erdachte und vom Mechaniker Johann Pfister hergestellte Maschine kann wegen ihres Aufbaus und ihrer Funktionsweise als erster Computer der Welt bezeichnet werden. In einem Brief an Kepler schreibt Schickard:

"aaa sind die Köpfchen senkrechter Zylinder, denen die Multiplikationen der Stellen einbeschrieben sind, die, soweit sie benötigt werden, durch die beweglichen Fenster bbb herausschauen. [Die Drehknöpfe] ddd haben innen befestigte zehnzähnige Rädchen, die so zusammengefügt sind, dass wenn irgendein rechtes sich zehnmal bewegt, das nächste linke einmal, oder wenn jenes 100 Umdrehungen macht, das dritte einmal usw. bewegt wird und zwar in derselben Richtung... Die jeweilige Zahl schaut durch die Öffnungen ccc in der mittleren Bank heraus. Auf der unteren Ebene schließlich bedeutet e Wirbel und f in ähnlicher Weise Öffnungen zur Darstellung von Zahlen, die während der Rechnung gebraucht werden."

Kulturamt der Universitätsstadt Tübingen (Hrsg.): Wilhelm Schickards Tübinger Rechenmaschine von 1623, Kleine Tübinger Schriften Heft 4, 2002, Redaktion: Wilfried Setzler, Bearbeitung: Friedrich Seck.

Nachbau der Schickard'schen Rechenmaschine, initiiert von B. Baron v. Freytag Löringhoff (1957)		Schickard's Federzeichnung seiner Maschine, entdeckt von Franz Hammer (vermutlich 1935)
Die Abbildungen sind der oben genannten Broschüre entnommen. (mit freundlicher Genehmigung von Herrn Prof.Setzler)

Die Fensterchen bbb werden durch Bewegen der horizontal beweglichen Holzschieber (mit "2" bis "9" beschriftet) sichtbar.

Die folgende Simulation der Schickard'schen Maschine funktioniert mithilfe von JavaScript.

0 / 0

Die Multiplikation zweier Dezimalzahlen funktioniert - sofern der Produktwert kleiner als 1000000 bleibt - folgendermaßen:

Eingabe einer m-stelligen Zahl x	durch Drehen der Zylinderköpfchen aaa, hier: Mausklicks auf a
Eingabe einer n-stelligen Zahl y	durch Drehen der Wirbel eee, hier: Mausklicks auf e
Herausziehen des Schiebers, der der Einerziffer von y entspricht	hier: Mausklick auf den entsprechenden Schieber
Übertragen der "Napier'schen Zahlen" ins Addierwerk von rechts nach links ab dem Einerdrehknopf	durch Drehen der entsprechenden Knöpfe ddd, hier: Mausklicks auf d
Schließen aller geöffneten Fensterchen bbb	hier: Mausklick auf den entsprechenden Schieber
Herausziehen des Schiebers, der der Zehnerziffer von y entspricht	hier: Mausklick auf den entsprechenden Schieber
Übertragen der "Napier'schen Zahlen" ins Addierwerk von rechts nach links ab dem Zehnerdrehknopf	durch Drehen der entsprechenden Knöpfe ddd, hier: Mausklicks auf d
u.s.w.
Ablesen des Endergebnisses in den Fenstern ccc

Der Schickard'sche Algorithmus zur Multiplikation zweier Dezimalzahlen ist aufgrund der nicht trivialen Bedienung der Drehknöpfe ddd zumindest für einen ungeübten Benutzer fehleranfällig. Die vollständig mechanische Bearbeitung von Grundrechenaufgaben war erst mit den sogenannten Vier-Spezies-Maschinen möglich. Die erste Rechenmaschine dieser Art wurde 1672 von Gottfried Wilhelm Leibniz (1646 - 1716) entwickelt. Wesentliche Bauteile waren die von Leibniz erfundenen Staffelwalzen. Erst ein Jahrhundert später gelang es dem schwäbischen Pfarrer Philipp Matthäus Hahn (1739 - 1790), die erste funktionstüchtige Staffelwalzenmaschine zu konstruieren.

Es gab im Laufe der Zeit noch Rechenmaschinen mit anderen Konstruktionsprinzipien bis hin zur legendären Curta des Wiener Rechenmaschinen-Fabrikanten Samuel Jacob Herzstark (1902 - 1988). Informationen hierzu gibt es zum Beispiel bei Jan Meyer: Geschichte der Rechenhilfsmittel

, Reinhard Atzbach: Rechenwerkzeuge

, W.G. Blümich: Mechanische Rechenhilfsmittel

und Harald Schmid: Facit-Rechenmaschinen

Die Funktion aller mechanischen Rechenmaschinen beruht auf mathematisch begründbaren Rechenalgorithmen, die durch das planmäßige Ineinandergreifen mechanischer Bauteile realisiert wurden. Die Ziffern von Dezimalzahlen wurden dabei durch genau definierte Stellungen von Zahnrädern dargestellt.

Eine solche analoge Darstellung von Zahlen ist in elektronischen Rechenmaschinen nicht möglich. Hier braucht man die binäre Darstellung von Zahlen unter Benutzung von genau zwei unterscheidbaren Zeichen.

Die binäre Darstellung einer natürlichen Zahl z ist zum Beispiel möglich, indem man diese nicht - wie im Dezimalsystem - zur Basis 10 aufschreibt, sondern zur Basis 2.

Mit Hilfe der Zweierpotenzen kann jede natürliche Zahl z ∈ ℕ wie folgt dargestellt werden:

Eine natürliche n-stellige Zahl z mit der Darstellung

z = z₀·b⁰ + z₁·b¹ + z₂·b² + ... + z_n-1·b^n-1

heißt Zahl zur Basis b. In abkürzender Schreibweise:

z = [z_n-1...z₂z₁z₀]_b

Eine Zahl zur Basis 10 heißt Dezimalzahl, eine Zahl zur Basis 2 Dualzahl, eine Zahl zur Basis 8 Oktalzahl, eine Zahl zur Basis 16 Hexadezimalzahl.

Die im Ausdruck [z_n-1...z₂z₁z₀]_b für die z_i einsetzbaren Zahlzeichen heißen Ziffern des jeweiligen Stellenwertsystems. Zulässige Ziffern:

Dualsystem:	0 1
Oktalsystem:	0 1 2 3 4 5 6 7
Dezimalsystem:	0 1 2 3 4 5 6 7 8 9
Hexadezimalsystem:	0 1 2 3 4 5 6 7 8 9 A B C D E F

Beispiel 1:
Darstellung zweier Zahlen unter Verwendung verschiedener Basen:
30₁₆ = 0·16⁰ + 3·16¹ = 48₁₀ = 1·2⁴ + 1·2⁵ = 110000₂.
1A7F₁₆ = F·16⁰ + 7·16¹ + A·16² + 1·16³ = 15·16⁰ + 7·16¹ + 10·16² + 1·16³ = 6783₁₀

Beispiel 3:
Darstellung von Sexagesimalzahlen in der babylonischen Mathematik:

Man erkennt an diesem Beispiel, dass die Babylonier weder Ziffern (im heutigen Verständnis) noch ein Symbol für die Zahl Null verwendet haben. (→ Die babylonische Keilschrifttafel Plimpton 322)

Die automatische Umrechnung einer natürlichen Zahl zur Basis 10 in eine natürliche Zahl zu irgendeiner Basis b lässt sich mit dem folgenden hier in JavaScript implementierten Algorithmus bewerkstelligen:

function decToAnyBase (dnum, b) {
// wandelt eine Dezimalzahl dnum in eine Zahl zur Basis b um
var z = dnum;      // Integer
var bpot = b;      // Integer
var code = 0;      // Integer
var ziffer = "";   // String
var ergebnis = ""; // String

if ((dnum > 0) && (b > 1)) {
while (bpot <= z) bpot = bpot*b;

do {
       bpot = bpot/b;
       code = Math.floor (z/bpot);
       codeplus55 = String.fromCharCode(code + 55);
       codeplus48 = String.fromCharCode(code + 48);
       ziffer = (code > 9) ? codeplus55 : codeplus48;
       ergebnis = ergebnis + ziffer;
       z = z - code*bpot;
    } while (bpot > 1);

return ergebnis;
}
else return ("nix");
}

Die einzugebende Zahl dnum darf nicht negativ und die Zahl b muss größer als 1 sein. Als Ziffern werden die in ihrer Reihenfolge eindeutig festgelegten Zeichen eines Teilbereichs der 8Bit-ASCII-Codetabelle verwendet: 0, 1, ... 9, A, B, ... Z. Insgesamt stehen also durch diese (willkürlich festgelegte) Einschränkung 36 Zeichen zur Verfügung, so dass b kleiner als 37 sein muss.

Unter der Voraussetzung, dass dnum, b ∈ ℕ mit b > 1 und dnum ≥ 0, terminiert dieser Algorithmus immer und liefert stets ein eindeutiges und korrektes Ergebnis (-> kompletter Quelltext des Programms).

Ein Algorithmus heißt genau dann korrekt, wenn er immer exakt das tut, was man von ihm erwartet. Die Korrektheit eines Algorithmus lässt sich in vielen Fällen sogar beweisen, zumindest dann, wenn er unter Verwendung einer passenden Programmiersprache auf imperative Weise implementiert ist ("decToAnyBase" ist zum Beispiel ein imperativ formulierter Algorithmus).

Eine imperative Programmierung ist vor allem gekennzeichnet durch die Hintereinanderausführung von Anweisungen und die Verwendung folgender elementarer Sprachstrukturen, die anhand des Beispiels "decToAnyBase" erläutert werden:

Eingabe und Ausgabe von Daten
	Die Eingabewerte werden der Funktion decToAnyBase unter Verwendung der formalen Parameter dnum und b übergeben. Als Ausgabewert liefert die Funktion decToAnyBase eine Zeichenkette zurück.

Variablen von verschiedenem Typ als "Behälter" für Werte
	Der Begriff "Variable" wird hier im Sinne der Informatik verwendet und bedeutet etwas anderes als sonst in der Mathematik. Beispielsweise ist bpot eine Variable vom Typ Integer; ziffer ist eine Variable vom Typ String.

arithmetische Ausdrücke, logische Ausdrücke und Zeichenketten
	Beispiele für arithmetische Ausdrücke: bpot/b, Math.floor (z/bpot) Beispiele für logische Ausdrücke: (bpot <= z), ((dnum > 0) && (b > 1)) Beispiele für Zeichenketten: "", "nix"

Wertzuweisungen
	Beispiele: code = 0; ziffer = ""; ziffer = String.fromCharCode(code + 55); z = z - code*bpot;

Schlüsselwörter
	Beispiele: function, var, if, else, do, while, return

Bedingte Anweisungen
	Beispiel: if ((dnum > 0) && (b > 1)) { //tue etwas } else return ("nix"); Bedeutung: Falls dnum größer als 0 ist und b größer als 1 ist, dann tue etwas, sonst liefere "nix" zurück.

Schleifenanweisungen
	Beispiel: while (bpot <= z) bpot = bpotb; Bedeutung: Solange* bpot kleiner oder gleich z ist, multipliziere den Wert der Variablen bpot mit b, ersetze den alten Wert von bpot durch den Produktwert von bpot·b und wiederhole dies alles.

Die Syntax beschreibt die Grammatik der Programmiersprache. Sie umfasst alle sprachlichen Regeln, denen ein in dieser Sprache geschriebener Programmquelltext genügen muss. Zur Formulierung dieser Regeln verwendet man üblicherweise Syntaxdiagramme oder den Backus-Naur-Formalismus.

Die Semantik betrifft den Sinn und die Bedeutung des Programmquelltextes. Ein syntaktisch korrekter Programmquelltext ist keineswegs automatisch auch semantisch korrekt. Beispielsweise ist die syntaktisch korrekte Programmierzeile

semantisch dann sinnlos, wenn die Arraykomponente feld[5] zuvor mit einer Zeichenkette belegt wurde und zahl der Bezeichner einer integer-Variablen ist (string und integer sind nicht miteinander verträgliche Datentypen!). Ein Programmquelltext ist insbesondere nur dann sinnvoll, wenn zum Beispiel bei Wertzuweisungen oder Vergleichen die dort verwendeten Datentypen zueinander passen.

Die im Allgemeinen schwierigste Aufgabe bei der Bewertung eines Algorithmus, der in Form eines Programmquelltextes vorliegt, ist es zu zeigen, dass dem syntaktisch korrekten und sinnvoll geschriebenen Algorithmus tatsächlich die Bedeutung zukommt, die vom Programmierer beabsichtigt war. Eine ganz andere Frage ist, ob ein gegebener Algorithmus unabhängig von der Wahl der (zulässigen) Eingabedaten immer terminiert. Schließlich ist noch sicherzustellen, dass die Maschine, die einen als korrekt erkannten Algorithmus schrittweise abarbeitet, auch fehlerfrei funktioniert.