1.2 Algorithmen

Als Algorithmus  bezeichnet man eine Arbeitsanleitung  für einen Computer. Der Begriff des Algorithmus ist ein zentraler Begriff der Programmierung. In diesem Abschnitt wird der Begriff zunächst motiviert und dann genauer definiert. Anschließend werden verschiedene Möglichkeiten der Formulierung von Algorithmen vorgestellt, und es wird auf die Ausführung von Algorithmen eingegangen. Algorithmen besitzen einige charakteristische Eigenschaften, die zum Abschluß dieses Abschnitts erläutert werden.

  
1.2.1 Arbeitsanleitungen

Wenn Sie etwas Leckeres kochen wollen, gehen Sie nach einem Rezept vor. Der Zusammenbau eines Modellflugzeugs erfordert eine Bastelanleitung. Beim Klavierspielen haben Sie ein Notenheft vor sich. Zum Skatspielen sind Spielregeln notwendig. Mit derlei Anleitungen wie Kochrezepten, Bastelanleitungen, Partituren und Spielregeln kommen Sie tagtäglich in Berührung. Wenn Sie sich den Aufbau solcher Anleitungen genauer anschauen, können Sie feststellen, daß sie alle etwas gemeinsam haben. Sie bestehen aus einzelnen Angaben (Anweisungen) , die in einer angegebenen Reihenfolge ausgeführt zu dem gewünschten Ergebnis führen:

Kochrezept:

Zwiebel feinhacken;
Brötchen einweichen;
aus Mett, gemischtem Hack, Eiern, feingehackter Zwiebel
und eingeweichtem und gut ausgedrücktem Brötchen
einen Fleischteig bereiten;
mit Salz und Pfeffer herzhaft würzen;
Trauben waschen, halbieren und entkernen;
...

Teilweise sind gewisse Anweisungen in den Arbeitsanleitungen nur unter bestimmten Bedingungen auszuführen (bedingte Anweisungen) . Ausgedrückt wird dieser Sachverhalt durch ein: Wenn eine Bedingung erfüllt ist, dann tue dies, ansonsten tue das

Anleitung für einen Fußballschiedsrichter:

ein Spieler von Mannschaft A wird von einem Spieler
von Mannschaft B gefoult;
wenn das Foul im Strafraum von Mannschaft B erfolgt
dann pfeife Strafstoß,
ansonsten pfeife Freistoß

Darüberhinaus kommt es auch vor, daß gewisse Anweisungen in einer sogenannten Schleife  oder Wiederholungsanweisung  mehrmals hintereinander ausgeführt werden sollen: Solange eine Bedingung erfüllt ist, tue folgendes

Anleitung beim Mensch-Ärgere-Dich-Nicht-Spiel:

Solange ein Spieler eine 6 würfelt,
darf er nochmal würfeln.

Weiterhin fällt auf, daß zum Ausführen der Anleitungen gewisse Voraussetzungen erfüllt sein müssen: Zum Kochen werden Zutaten benötigt, Basteln ist nicht ohne Materialien möglich und zum Spielen sind Spielkarten oder Spielfiguren unabdingbar.

Zutaten beim Kochen:

250g Mett
250g gemischtes Hack
2 Eier
1 Zwiebel
1 Brötchen
Pfeffer
Salz

Im allgemeinen bestehen also Arbeitsanleitungen aus der Auflistung bestimmter Voraussetzungen bzw. Zubehör und der eigentlichen Anleitung:

Jenga-Spiel:

Zubehör:
1 Spielanleitung
45 Holzklötzchen
Spielanleitung:
solange die Spieler noch Lust haben zu spielen:
Turm aufbauen, dabei jeweils die Klötzchen
rechtwinklig zueinander versetzen;
solange der Turm noch nicht eingestürzt ist, müssen
die Spieler der Reihe nach folgendes tun:
ein Klötzchen aus dem Turm entnehmen;
das Klötzchen oben auf den Turm legen

Ein weiteres Merkmal dieser alltäglichen Arbeitsanleitungen ist, daß sie selten exakt formuliert sind, sondern oft Teile enthalten, die unterschiedlich interpretiert werden können. Im allgemeinen sagt uns unser gesunder Menschenverstand dann, was in der speziellen Situation zu tun ist. Beim obigen Kochrezept ist bspw. die Anleitung ,,mit Salz und Pfeffer herzhaft würzen`` wenig präzise für jemanden, der noch nie gekocht hat.

  
1.2.2 Definition des Begriffs Algorithmus

Anleitungen, wie sie im letzten Abschnitt erörtert worden sind, werden von Menschen ausgeführt, um unter bestimmten Voraussetzungen zu einem bestimmten Ergebnis zu gelangen. Genauso wie Menschen benötigen auch Computer Arbeitsanleitungen, um Probleme zu lösen. Arbeitsanleitungen für einen Computer bezeichnet man als Algorithmen . Algorithmen weisen dabei viele Merkmale auf, die wir im letzten Abschnitt für Anleitungen für Menschen kennengelernt haben. Sie bestehen aus Anweisungen, können bedingte Anweisungen und Schleifen enthalten und operieren auf vorgegebenen Materialien, den Daten. Sie unterscheiden sich jedoch darin, daß sie wesentlich exakter formuliert sein müssen, da Computer keine Intelligenz besitzen, um mehrdeutige Formulierungen selbständig interpretieren zu können.

Damit kann der Begriff Algorithmus folgendermaßen definiert werden: Ein Algorithmus ist eine Arbeitsanleitung  zum Lösen eines Problems bzw. einer Aufgabe, die so präzise formuliert ist, daß sie von einem Computer ausgeführt werden kann.

  
1.2.3 Formulierung von Algorithmen

Zur Beschreibung von Algorithmen existieren mehrere Möglichkeiten bzw. Notationen, von denen die gängigsten anhand eines kleinen Beispiels im folgenden kurz vorgestellt werden. Bei dem Beispiel geht es um die Lösung des Problems, die Summe aller Natürlichen Zahlen bis zu einer vorgegebenen Natürlichen Zahl n zu berechnen. Mathematisch definiert ist also die folgende Funktion f zu berechnen:

$$f : \N \rightarrow \N \hspace{0.1cm} mit \hspace{0.1cm} f(n)... ...um_{i=1}^n i \hspace{0.1cm} f\uml {u}r \hspace{0.1cm} n \in \N$$

1.2.3.1 Umgangssprachliche Formulierung

Arbeitsanleitungen für Menschen werden im allgemeinen umgangssprachlich formuliert. Es gibt häufig keine vorgegebenen Schemata oder Regeln. Der Mensch interpretiert die Anweisungen gemäß seines Wissens oder bereits vorliegender Erfahrungen. Auch Algorithmen lassen sich prinzipiell umgangssprachlich beschreiben. Die Beschreibung sollte jedoch so exakt sein, daß sie ohne weitergehende intellektuelle Anstrengungen in ein Programm oder eine andere Notation übertragen werden kann. Eine umgangssprachliche Beschreibung des Algorithmus zum Lösen des Beispielproblems lautet bspw.:

Gegeben sei eine Natürliche Zahl n.
Addiere die Natürlichen Zahlen von 1 bis n.
Die Summe ist das Resultat.

1.2.3.2 Programmablaufpläne

Eine normierte Methode zur graphischen Darstellung von Algorithmen stellen die Programmablaufpläne  (PAP) - auch Flußdiagramme  genannt - dar. In Abbildung (a) werden die wichtigsten Elemente der graphischen Notation skizziert. Daneben findet sich in Abbildung (b) ein Programmablaufplan zur Lösung des Beispielproblems.

  

Abbildung: Programmablaufpläne

1.2.3.3 Struktogramme

Struktogramme  (Nassi-Shneiderman-Diagramme ) bieten eine weitere graphische Notation zur Darstellung von Algorithmen. Gegenüber Programmablaufplänen sind sie im allgemeinen übersichtlicher und verständlicher. Die wichtigsten Elemente, aus denen sich Struktogramme zusammensetzen, sind Abbildung (a) zu entnehmen. In Abbildung (b) wird eine Lösung des Beispielproblems mit Hilfe von Struktogrammen formuliert.

  

Abbildung: Struktogramme

1.2.3.4 Programmiersprache

Algorithmen lassen sich auch in der Notation einer bestimmten Programmiersprache formulieren. Folgendes an die Syntax der Programmiersprache Java  angelehntes Programm löst das Beispielproblem:

       int n = readInt();
       int erg = 0;
       int i = 0;
       while (i <= n) {
         erg = erg + i;
         i = i + 1;
       }
       printInt(erg);

1.2.4 Ausführung von Algorithmen

Algorithmen stellen eine Arbeitsanleitung dar, d.h. werden sie ausgeführt, sollten sie nach Abarbeitung der einzelnen Anweisungen das erwartete Ergebnis liefern. Bei der Ausführung eines Algorithmus läuft ein sogenannter Prozeß  ab. Dieser Prozeß wird durch einen Prozessor  gesteuert. Bei den Arbeitsanleitungen  für Menschen (siehe Abschnitt ) ist der Mensch der Prozessor, bei Algorithmen ist dies der Computer, der die Notation, in der der Algorithmus formuliert ist, kennen und verstehen muß.

Prinzipiell kann jeder Algorithmus auch durch einen Menschen ausgeführt werden. Computer haben gegenüber uns Menschen jedoch gewisse Vorteile:

• Ihre hohe Rechengeschwindigkeit : Computer können heutzutage einige Millionen Rechenoperationen pro Sekunde ausführen.
• Ihre große Zuverlässigkeit : Computer ermüden nicht und führen fehlerlos genau die Anweisungen durch, die ihnen der Mensch vorschreibt.
• Ihre gewaltige Speicherfähigkeit : Computer können Milliarden Daten dauerhaft abspeichern und sie auch sehr schnell wiederfinden.

  
1.2.5 Eigenschaften von Algorithmen

Algorithmen weisen folgende Eigenschaften auf:

• Eindeutigkeit : Algorithmen liefern eine eindeutige Beschreibung zur Lösung eines gegebenen Problems. Sie dürfen keine widersprüchlichen Aussagen enthalten.
• Parametrisierbarkeit : Algorithmen lösen nicht nur genau ein spezielles Problem sondern eine Klasse von Problemen mit dem gleichen Schema. So löst der Algorithmus in Abschnitt das Problem der Summenbildung von Natürlichen Zahlen nicht nur für eine fest vorgegebene Zahl sondern für beliebige Zahlen n. n wird auch Parameter  des Algorithmus genannt.
• Finitheit : Die Beschreibung eines Algorithmus besitzt eine endliche Länge.
• Ausführbarkeit : Algorithmen dürfen keine Anweisungen enthalten, die prinzipiell nicht ausführbar sind wie bspw. widersprüchliche Anweisungen.
• Terminierung : Algorithmen müssen nach endlich vielen Schritten terminieren, d.h. sie müssen ein Ergebnis liefern und dann anhalten.
• Determiniertheit : Algorithmen heißen determiniert, wenn sie mit gleichen Startbedingungen mehrfach ausgeführt immer die gleichen Ergebnisse liefern.
• Determinismus : Algorithmen heißen deterministisch, wenn zu jedem Zeitpunkt ihrer Ausführung höchstens eine Möglichkeit zur Fortsetzung besteht.

Die ersten drei Eigenschaften sind dabei Eigenschaften der Formulierung eines Algorithmus an sich (statische Eigenschaften), die letzten vier sind Eigenschaften der Ausführung eines Algorithmus (dynamische Eigenschaften).

Nicht alle Algorithmen erfüllen die letzten drei Eigenschaften. Steuerungsprogramme in Betriebssystemen  sind häufig nicht-terminierend, und aus dem Bereich der Stochastik  sind bspw. nicht-determinierte und nicht-deterministische Algorithmen bekannt.

  
1.2.6 Praxisrelevante Eigenschaften von Algorithmen

Algorithmen  sind Beschreibungen zur Lösung eines Problems bzw. einer Aufgabe. Dabei ist jedoch festzustellen, daß es zur Lösung eines Problems nicht nur immer genau einen korrekten Algorithmus gibt. Vielmehr kann sogar mathematisch bewiesen werden, daß es zu jedem Algorithmus unendlich viele verschiedene äquivalente Algorithmen gibt, also Algorithmen, die dasselbe Problem mit identischen Ergebnissen lösen.

In der Praxis ist es aber im allgemeinen nicht gleichgültig, welchen von zwei äquivalenten Algorithmen man zur Lösung eines Problems einsetzt. Kriterien, die in der Praxis bei der Findung bzw. Auswahl eines Algorithmus eine wichtige Rolle spielen, sind insbesondere:

• Effizienz : Algorithmen sollten so schnell wie möglich und mit möglichst wenig Ressourcen zu einem korrekten Ergebnis kommen.
• Speicherbedarf : Die Beschreibung eines Algorithmus sollte möglichst knapp sein, worunter die Verständlichkeit aber nicht leiden darf.
• Erweiterbarkeit : Algorithmen sollten ohne großen Aufwand an geänderte Anforderungen anpaßbar sein.
• Wiederverwendbarkeit : Algorithmen sollten so formuliert werden, daß sie nicht nur einmalig, sondern auch zur Lösung von Teilproblemen in anderen Zusammenhängen genutzt werden können.
• Portabilität : Algorithmen sollten nicht auf einen bestimmten Computertyp zugeschnitten sein, sondern prinzipiell auf beliebigen Computern ausgeführt werden können.
• Zuverlässigkeit : Algorithmen sollten das Problem korrekt und vollständig lösen. Zu beachten sind dabei insbesondere sogenannte Grenzfälle.