Informatik - Skript zum Unterricht

(II) Software

1. Algorithmusbegriff

1.1 Geschichte

Die Bezeichnung Algorithmus geht auf den Namen des persisch-arabischen Mathematikers Abu Jafar Muhammad Ibn Mûsâ Al-Chwârismî zurück, der etwa 780 bis 850 in Bagdad lebte. Als Bibliothekar des Kalifen Al Mamun schrieb er eine Aufgabensammlung als Rechenbuch über das indische Zahlensystem für Kaufleute und Testamentvollstrecker: "Regeln der Wiedereinsetzung und Reduktion", welche im Jahre 829 veröffentlicht wurde.
Die lateinische Übersetzung des arabischen Buches mit dem Titel "Algorithmie de numero Indiorum" gibt den Verfassernamen mit 'Al Gorithmus' wieder, um so eine Assoziation zum griechischen Wort 'arithmos' (Zahl) zu erzielen.
Der aus der Auvergne (Frankreich) stammende Mönch Gerbert von Aurillac machte sich mit den "arabischen Zahlen" während einer Reise nach Cordoue (Spanien) vertraut. Nachdem er im April des Jahres 999 zum Papst Silvester 11. geweiht worden war, konnte er allmählich diese Symbole verbreiten. In Europa kam die arabische Wissenschaft erst 1202 durch das Werk "Liber Abaci" von Leonardo Fibonacci, genannt Leonardo von Pisa, an die Öffentlichkeit.
Mit der Erfindung des Buchdruckes wurde das Rechnen mit den zehn Ziffern endgültig festgelegt.

1.2 Definition

Algorithmus

Unter einem Algorithmus versteht man eine Folge von eindeutig formulierten Handlungsanweisungen oder Vorschriften, die in einer vorgeschriebene Reihenfolge ausgeführt, zur Lösung einer bestimmten Unterklasse von Aufgaben, einem Aufgabentyp, führen.Er hat endlich viele Schritte und liefert immer ein Ergebnis. Dabei handelt es sich entweder um die Lösung des Problems oder um die Erkenntnis der Unlösbarkeit des Problems

Anweisung

Eine Anweisung ist ein Befehl oder Kommando (in einer Programmiersprache), der sich im Allgemeinen aus zwei Teilen zusammensetzt:
(1) WAS (der Rechner) machen soll (Operationsteil der Anweisung) z.B. lesen, ausgeben, zuweisen
(2) WOMIT (der Rechner) etwas machen soll (Operandenteil der Anweisung)

Ein Algorithmus ist also -grob gesprochen- eine Abfolge von Handlungsanweisungen zur Lösung eines Problems.

Diese Folge von Anweisungen bzw. Vorschriften muss folgende fünf Bedingungen erfüllen:

Allgemeingültigkeit: Die Anweisungen besitzen Gültigkeit für die Lösung einer ganzen Problemklasse, nicht nur für ein Einzelproblem
Ausführbarkeit: Die Anweisungen müssen verständlich formuliert sein für den Befehlsempfänger (Mensch oder Maschine) und für diesen ausführbar sein.
Eindeutigkeit: An jeder Stelle muss der Ablauf der Anweisungen eindeutig sein, d.h. die Reihenfolge der Anweisungen eindeutig sein.
Endlichkeit: Die Beschreibung der Anweisungsfolge muss in einem endlichen Text möglich sein, d.h. die Anzahl der Anweisungen muss endlich sein (Endlichkeit der Zahl der Anweisungen).
Terminiertheit: Nach endlich vielen Schritten liefert die Anweisungsfolge eine Lösung des gestellten Problems (Endlichkeit der Schritte zur Lösung).

Mit einem Computer sind nur solche Probleme lösbar, zu denen ein Algorithmus vorhanden ist.
Ein Algorithmus, der in einer für den Computer verständlichen Sprache formuliert ist, heißt Programm.
Quelle: http://schulen.freiepresse.de/gymnasiumolbernhau/informatik/algorithmen.htm

1.3 Beispiel

Beispiel für einen umgangssprachlichen Algorithmus:
Problemstellung: Durchführen eines Telefongesprächs

Hörer abnehmen;
Freizeichen abwarten;
WIEDERHOLE  wähle nächste Ziffer;
   BIS      keine Ziffer der Telefonnummer mehr vorhanden;
FALLS       der Gesprächspartner sich meldet
   DANN     führe das Gespräch
   SONST    ärgere dich;
Hörer auflegen.

Wenn wir annehmen, dass die Telefonnummer des Gesprächspartners bekannt und die Telefonanschlüsse intakt sind, erfüllt die Anweisungsfolge wegen der Sterblichkeit der Telefonteilnehmer (endliche Durchführbarkeit) alle Bedingungen für einen Algorithmus.