Theseus kämpft mit dem Minotausrus (gr. Malerei)6.1 Alltagsalgorithmen


In den Vergangenen Kapiteln ist uns öfters der Algorithmusbegriff begegnet. Wir haben diesen Begriff naiv benutzt, d.h. wir taten so, als wäre Algorithmus ein anderes Wort für Kochrezept. In diesem Kapitel wollen wir den Begriff etwas näher beleuchten.

 
 
Übung Das nachfolgende Ablaufdiagramm veranschaulicht das Vorgehen, wenn man ein Autos zulassen möchte. Verbalisieren Sie das dargestellte Verfahren. Arbeiten Sie wesentliche Sprachkonstruktionen heraus.
Ablaufdiagramm  

 

Wesentliche Sprachkon- struktionen Drei Sprachkonstrukte reichen aus, Ablaufdiagramme in einen Algorithmus überzuführen. Wie sie in Java realisiert sind, haben wir bereits gesehen. Zum ersten ist dies die Sequenz. Man spricht von einer Sequenz oder auch Reihung, wenn der Ablauf durch das Aufzählen von Anweisungen erfolgt. Die Anweisungen sollen in der Reihenfolge ausgeführt werden, wie die Reihung es vorgibt. In einer Normsprache könnte man jede Anweisung mit "tue" beginnen. Eine Sequenz ist also eine Aufreihung von "tue"s.  Nachfolgende Anweisungen werden durch Semikola getrennt. Zum zweiten haben wir die Verzweigung. Sie sorgt dafür, dass nach der Beantwortung einer Ja-Nein-Frage der weitere Ablauf in zwei Wege aufteilt wird. In der Normsprache erkennt man eine Verzweigung an der 'wenn Bedingung ... erfüllt dann..sonst' Konstruktion. In Java wird die Verzweigung durch if(<Bedingung>) .. else ... realisiert. Schließlich das dritte Sprachelement, die Iteration  (Schleife). Sie beschreibt Wiederholungen und ist erkennbar an Sprachelementen wie "tue solange Bedinung...erfüllt" oder "tue solange bis Bedingung .. erfüllt ist.." oder "tue so und sooft mal". Wie wir gesehen haben, gibt es die while- do- und for-Schleife.
Wir wollen das Ablaufdiagramm für die Zulassung eines Autos in einer Normsprache formulieren. Dabei handelt es sich bei einer Normsprache um ein Sprache, die im wesentlichen noch an der Alltagssprache sich orientiert, und die sprachlichen Konstruktionen wie Verzweigung und Iteration verwendet. Eine Sequenz zeigt sich im Untereinanderschreiben aufeinander folgenden Anwesungen.

 

Der Algorithmus
in einer Normsprache
Das obere Ablaufdiagramm könnte in einer Normsprache etwa folgende Gestalt haben.

wenn TÜV abgelaufen dann tue {
   wiederhole bis Überprüfung erfolgreich {
       Fahrzeug überprüfen lassen
       wenn Überprüfung nicht erfolgreich {
           wenn Reparatur sinnvoll {
               Auto in Werkstatt
           }
           sonst {
               Auto zum Schrottplatz
               fertig!
           }
       }
   }
}

mit KFZ-Brief,..., Prüfprotokoll zur Zulassungsstelle
fertig!

 

Die Strukturierung ist kein Element der Normsprache, erleichtert aber das Lesen. Was in eine Schleife, in einen Ja- bzw. Nein-Zweig einer Iteration gehört, wird durch das Setzen von geschweiften Klammern markiert. Man erkennt, dass die Formulierung eines Algorithmus in einer Normsprache schon deutlich die Implementierung  in einer Computersprache vorwegnimmt.
 

  Wir erkennen, dass die Beschreibung des Ablaufs für das Zulassen eines Autos gewisse Bedingungen erfüllt, die wir für die Festlegung des Algorithmusbegriffs verwenden wollen.
 
Algorithmus
Spezifikation
Implementierung
(Der Begriff)
Ein Algorithmus ist ein Problemlösungsverfahren für ein genau vorgegebenes Problem. Genauer besehen ist er aus einem Problemlösungsrezept mit den folgenden Eigenschaften:
  • Das Verfahren besteht aus einzelnen Schritten (Aktionen).
  • Jede Aktion bewirkt eine Änderung von Objekten und bestimmt, welche Aktionen als nächstes ausgeführt werden sollen.    
  • Jede Aktion muss von dem gegebenen Prozessor eindeutig interpretierbar sein (Maschine oder Lebewesen).
  • Jede Aktion muss durch den Prozessor in endlicher Zeit ausführbar sein.
  • Der Algorithmus muss mit endlich langem Text formulierbar sein.
  • Der Algorithmus kann mit Eingangsobjekten, Ausgangsobjekten und Hilfsobjekten arbeiten (muss aber nicht).

Oder in Kurzfassung:

Ein Algorithmus ist eine Beschreibung, um ein Problem zu lösen. Diese Beschreibung ist

  1. eindeutig 
  2. ausführbar und
  3. terminiert.

Achtung: Die Beschreibung selbst muss terminiert sein, nicht jedoch die Ausführung, diese kann i. P. ewig dauern,  wie das Beispiel der Ampelsteuerung zeigt.

 

Spezifikation - Algorithmus - Implementierung Neben dem Begriff des Algorithmus taucht häufig noch die Begriffe Spezifikation und Implementierung auf. Diese Begriffe, die wir bisher eher naiv benutzt haben, lassen sich jetzt etwas präzisieren. So beschreibt die Spezifikation das Problem, das gelöst werden soll, liefert also eine Antwort auf ein 'was?". Der Algorithmus beschriebt dann, wie das Problem gelöst wird. Die Implementierung schließlich ist die Realisierung des Algorithmus in einer konkreten Computersprache wie z.B. Pascal, C++, Delphi oder Java.

An einem Beispiel sollen Spezifikation und Algorithmus verdeutlicht werden
 

ein weiteres Beispiel
Reifenwechsel
Spezifikation:   Ersetze ein Rad durch ein Reserverad. Schreiben Sie einen Algorithmus, der die Spezifikation erfüllt.

Algorithmus:

Packe Werkzeug und Reserverad aus.
Entferne Radkappe.
Wiederhole solange solange noch eine Mutter fest {
    Lockere feste Mutter
}
Setze Wagenheber an.
Hebe Wagen mit Heber an.
Wiederhole solange noch eine Mutter nicht entfernt ist {
    Schraube Mutter ab
}
Nimm Rad ab.
Setze Reserverad an.
Wiederhole solange noch eine Mutter nicht befestigt ist {
    Schraube Mutter auf freien Bolzen
}
Setze Radkappe auf
Entferne Wagenheber.
fertig!
 

Weitere Beispiele...
  • Anbaggern
  • Löse Gleichungssystem
  • Vereinbare Gesprächstermin
  • Starte ein Auto
  • Koche Mittagessen

"Programmieren" ist so alt wie Unterweisung und Nachahmung.
 

zu 6.2 Der Faden der Ariadne
zur Startseite www.pohlig.de  (C) MPohlig 2005