Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 30

Unserer ersten Begriffsbestimmung für Algorithmen zufolge beschreibt ein Algorithmus ein Verfahren, das einen Bearbeitungsvorgang aus elementaren Schritten zusammensetzt. Bevor wir uns konkreten Sprachen für die Formulierung von Algorithmen zuwenden, listen wir einige gängige Bausteine für derartige Algorithmenbeschreibungen auf, die auch aus Handlungsvorschriften des täglichen Lebens bekannt sein dürften. Wir werden diese Bausteine anhand einfacher Vorschriften aus Kochrezepten verdeutlichen.

Elementare Operationen

 Die Basiselemente sind die elementaren Operationen, die ausgeführt werden, ohne näher aufgeschlüsselt zu werden:»Schneide Fleisch in kleine Würfel.«

Sequenzielle Ausführung

 Das Hintereinanderausführen von Schritten bezeichnet man als sequenzielle Ausführung:»Bringe das Wasser zum Kochen, dann gib das Paket Nudeln hinein, schneide das Fleisch, dann das Gemüse.«

Parallele Ausführung

 Die parallele Ausführung hingegen bedeutet das gleichzeitige Ausführen von Schritten:»Ich schneide das Fleisch, du das Gemüse.«Im Gegensatz zur sequenziellen Ausführung verbindet man mit der parallelen Ausführung in der Regel mehrere Prozessoren, also ausführende Subjekte bzw. Maschinen.

Bedingte Ausführung

 Unter einer bedingten Ausführung verstehen wir einen Schritt, der nur ausgeführt wird, wenn eine bestimmte Bedingung erfüllt wird.»Wenn die Soße zu dünn ist, füge Mehl hinzu.«Eine bedingte Ausführung erfordert also einen Test einer Bedingung. Eine Variante der bedingten Ausführung erhält man, indem auch für den negativen Ausgang des Tests ein auszuführender Schritt angegeben wird.

Schleife

 Unter einer Schleife versteht man die Wiederholung einer Tätigkeit, bis eine vorgegebene Endbedingung erfüllt wird:»Rühre, bis die Soße braun ist.«Man bewegt sich also »im Kreise«, bis man etwas fertiggestellt hat – man kann sich den Begriff gut mit der Assoziation einer »Warteschleife« eines Flugzeuges merken.

Unterprogramm

 Bereits aus dem Sprachgebrauch der Informatik stammt das Konzept des Unter»programms«:»Bereite Soße nach Rezept Seite 42.«Ein Unterprogramm beschreibt durch einen Namen (oder hier durch eine Seitennummer) eine Bearbeitungsvorschrift, die »aufgerufen« wird, um dann ausgeführt zu werden. Nach Ausführung des Unterprogramms fährt man im eigentlichen Algorithmus an der Stelle fort, an der man zum Unterprogramm gewechselt war.

Rekursion

 Eines der Kernkonzepte der Informatik ist die Rekursion. Die Rekursion bedeutet die Anwendung desselben Prinzips auf in gewisser Weise »kleinere« oder »einfachere« Teilprobleme, bis diese Teilprobleme so klein sind, dass sie direkt gelöst werden können. Hier gibt es leider offenbar keine direkten Beispiele aus Kochbüchern, so dass wir uns mit dem folgenden eher künstlichen Beispiel behelfen:»Viertele das Fleischstück in vier gleich große Teile. Falls die Stücke länger als 2 cm sind, verfahre mit den einzelnen Stücken wieder genauso (bis die gewünschte Größe erreicht ist).«Rekursion wird uns durch das ganze Buch begleiten – sollte das Prinzip bei diesem eher künstlichen Beispiel nicht klar geworden sein, verweisen wir auf die folgenden Abschnitte, in denen Rekursion intensiv behandelt wird.

Ausdrucksfähigkeit von Algorithmensprachen

Bei einer derart langen Auflistung stellt man sich schnell die Frage, ob denn alle diese Konstrukte auch notwendig sind. Diese Frage betrifft das Problem der Ausdrucksfähigkeit von Algorithmensprachen und wird uns noch näher beschäftigen. Hier sei nur bemerkt, dass die Konstrukte

 elementare Operationen + Sequenz + Bedingung + Schleifen

ausreichen, um eine genügend ausdrucksstarke Algorithmensprache festzulegen – allerdings genügen hierfür auch andere Kombinationen, wie wir später sehen werden.