Ein Algorithmus ist eine strukturierte Abfolge von Anweisungen, die beschreiben wie ich eine gegebene Aufgabe erledigen kann.
Das Wort selbst ist abgeleitet vom Namen des persischen Rechenmeisters und Astronomen Muḥammad Ibn-Mūsā al-H̱wārizm, der im 9. Jht. in Bagdad im dortigen "Haus der Weisheit" ein arabisches Lehrbuch über die indischen Ziffern verfasste. Das Buch wurde im 12. Jht. ins Lateinische übersetzt, dabei wurde auch der Name latinisiert. Aus den Anfangsworten "Dixit Algorismi" = "Algorismi hat gesagt" wurde der Algorithmus.
Beispiel 1: Wegbeschreibung
Ein einfaches Beispiel ist eine Wegbeschreibung:
- fahre mit der U-Bahn bis "Schlesisches Tor"
- verlasse den U-Bahnhof
- wende dich nach rechts
- gehe bis zur 3. Kreuzung
- wende dich nach links
- gehe bis zum Ufer
Beispiel 2: Kochrezept
Ein anderes populäres Beispiel ist ein Kochrezept - hier für ein Tiramisu1:
- Creme:
- 4 Eigelb, 100g Puderzucker, 500g Mascarpone und 2 cl Amaretto cremig rühren
- 2 Eiweiß steif schlagen
- Eiweiß vorsichtig unterheben
- Biskuit:
- 250g Löffelbiskuits mit 2 Tassen Espresso tränken
- 4 Lagen schichten:
- Biskuits,
- Mascarponecreme,
- Biskuits,
- Mascarponecreme.
- Finish:
- Dick mit Kakao bestäuben
- kühl stellen.
Hier finden wir auch eine weitere wichtige Sache: Funktionen, also ausgelagerte Beschreibungen einer einzelnen, wiederkehrenden Aufgabe. Cremig rühren, steif schlagen und unterheben mögen für Kochkundige als zu einfach für eine Funktion erscheinen, aber wir wollen ja mit dummen Computern reden.
Da diese Funktionen immer wieder in Rezepten auftauchen, könnten wir eine Art Funktionssammlung anlegen, auf die wir beim nächsten Rezept zurückgreifen (selbst wenn es nur eine der drei Funktionen benötigt). Solche Funktionssammlungen heißen beim Programmieren Bibliothek (engl. library).
Funktionen werden - Überraschung - ebenfalls durch einen Algorithmus beschrieben.
Konkret zunächst steif schlagen:
Was soll steif geschlagen werden? Ein Eiweiß - das ist ein Parameter, mit dem die Funktion aufgerufen wird, üblicherweise in Klammern hintern den Funktionsnamen gesetzt:
steif_schlagen(material)2
Die Funktion könnte z.B. auch mit Sahne anstatt Eiweiß aufgerufen werden.
Und wie geht das?
materialin eine Schüssel geben- Schüssel mit einer Hand festhalten
- mit dem Schneebesen solange schlagen, bis der Inhalt steif geworden ist
Hier gibt es ein neues wichtiges Element in der Programmierung: eine Schleife.
Konkret etwas solange ausführen bis eine Bedingung erfüllt ist - etwas formaler in Pseudo-Code SOLANGE bedingung ...3.
Mit schlagen()4 sehen wir schon eine weitere Funktion (sowas wie "Schneebesen kreisförmig anheben und fallenlassen"?), deren Asuführung wir uns hier aber ersparen.
Als nächste wenden wir uns dem Cremig rühren zu. Diese Funktion erhält als Parameter eine ganze Reihe von Dingen, die cremig gerührt werden sollen - eine Liste!
cremig_rühren(liste)5
- Jedes Element aus
listein eine Schüssel geben - Schüssel mit einer Hand festhalten
- mit dem Schneebesen solange rühren, bis der Inhalt cremig geworden ist
Hier gibt es eine weitere Form der Schleife: etwas das mehrfach ausgeführt werden soll für-jedes-Element, im weiteren Pseudo-Code FÜRJEDES6.
Bei genauerer Betrachtung fällt auf, dass steif_schlagen(material) und cremig_rühren(liste) recht ähnlich sind.
"Recht ähnlich" - da klingeln die Programmier-Glocken und das alte Mantra Niemals-etwas-doppelt-machen7 in den Ohren. Wir könnten die beiden Funktionen zu einer einzigen Funktion zusammenfassen - Abstraktion.
Die neue Funktion nennen wir erst mal cremig_rühren2().
Trotzdem unterscheiden sich die Funktionen im Detail:
steif_schlagen()erhält nur einen einzelnen Parameter, cremig_rühren() dagegen eine Liste von Parameternschlagen()vs.rühren()- Schleifenbedingung: "Inhalt steif" vs. "Inhalt cremig"
Das lösen wir durch einen weiteren Parameter der neuen Funktion, die wir zunächst cremig_rühren2() nennen, anhand dessen wir unterscheiden, ob wir steif oder cremig wollen und ob wir rühren oder schlagen. Den Paramater nennen wir steif - ist er WAHR, schlagen wir steif, andernfalls rühren wir cremig. Außerdem behandeln wir den einzelnen Parameter als eine Liste, die nur ein Element enthält.
Damit ist cremig_rühren2(steif, liste):
- Jedes Element aus
listein eine Schüssel geben - Schüssel mit einer Hand festhalten
- ist
steifWAHR?- wenn ja: mit dem Schneebesen solange schlagen, bis der Inhalt steif geworden ist
- sonst: mit dem Schneebesen solange rühren, bis der Inhalt cremig geworden ist
Damit können wir auf die beiden alten Funktionen steif_schlagen(material) und cremig_rühren(liste) verzichten und nennen die neue Funktion cremig_rühren():
cremig_rühren(steif, liste)
FÜRJEDES element AUS liste
in_schüssel_geben(element)
schüssel_festhalten()
WENN steif DANN
SOLANGE inhalt_nicht_steif()
schlagen()
SONST
SOLANGE inhalt_nicht_cremig()
rühren()
Als letztes könnte uns auffallen das SOLANGE in Kombination mit der Verneinung nicht eher unschön ist. Viele Sprachen bieten dafür eine SOLANGE ... BIS8 Schleife an.
Das ist dann eine sogenannte Stil-Frage.
cremig_rühren(steif, liste)
FÜRJEDES element AUS liste
in_schüssel_geben(element)
schüssel_festhalten()
WENN steif DANN
SOLANGE
schlagen()
BIS inhalt_steif()
SONST
SOLANGE
rühren()
BIS inhalt_cremig()
Voila (unterheben sparen wir uns mal).
Beispiel 3: Euklidscher Algorithmus - größter gemeinsamer Teiler
Als weiteres Beispiel was formaleres - ca. 300 v.u.Z entwickelte Euklid den ersten bekannten (nicht-trivialen) Algorithmus der Welt: die Bestimmung des größten gemeinsamen Teilers (ggT) zweier Zahlen a und b (die eine oder der andere erinnert sich vielleicht noch so an die 5./6. Klasse...)
In Worten: Euklid zieht wiederholt die kleinere der beiden Zahlen von der größeren ab bis 1 erreicht ist. Das funktioniert, da der ggT gleich bleibt, wenn ich die kleinere von der größeren Zahl abziehe.9
Als Pseudo-Code
WENN a == 0 DANN
Ergebnis: b
SONST
SOLANGE b != 0
WENN a > b DANN
a := a - b
SONST
b := b - a
Ergebnis: a
Hier sehen wir gleich mehrere wichtige Konzepte:
- Verzweigungen (auch bedingte Verzweigung):
- "WENN ... DANN" (und "WENN ... DANN ... SONST") ist eine Abfrage und daran hängend eine Verzweigung im Programm.
DANN und SONST umfassen eine ganzen Block an Anweisungen - hier zusammengefasst durch die Einrückung.
(engl. "IF ... THEN ... ELSE)
- "WENN ... DANN" (und "WENN ... DANN ... SONST") ist eine Abfrage und daran hängend eine Verzweigung im Programm.
- Operatoren:
- "==" (sprich: "gleichgleich") ist der Vergleichsoperator.
a == 0 ist WAHR, wenn a Null ist und andernfalls FALSCH (engl. TRUE und FALSE)
Da ein einzelnes "=" nicht eindeutig zwischen Vergleich und Zuweisung unterscheidet hat C das doppeltes Gleichheitszeichen für den Vergleich eingeführt (und nutzt das das einfache "=" für die Zuweisung). - ":=" (sprich: "doppelgleich") ist der Zuweisungsoperator
a := 3 weist a den Wert 3 zu
a := b weist a den Wert von b zu
a := b + 6 weist a den Wert von b plus 6 zu (läßt b aber unverändert!)
a := a - b weist a den Wert von a verringert um den den Wert von b (zieht im Effekt also b von a ab)
Aus demselben Grund aus dem C das "==" einführte, hat Pascal das ":=" eingeführt. Der besseren Erkennbarkeit halber verwenden wir beides (und verzichten auf das missverständliche "=") - "!=" (sprich: "ungleich") ist ein weiterer Vergleichsoperator, der auf Verschiedenheit testet
auch geschrieben als "<>" (sprich: "kleiner-größer"), also kleiner-oder-größer (aber nicht gleich)
- "==" (sprich: "gleichgleich") ist der Vergleichsoperator.
- Schleifen:
- Bereits oben eingeführt ist "SOLANGE" ist eine Schleife: Solange die Bedingung (hier: b ungleich der Zahl Null) zutrifft (also WAHR ist), wird der Block ausgeführt.
Am Ende des Blockes springt das Programm wieder zu Bedingung und prüft erneut. Wenn die Bedingung nicht mehr zurifft (also FALSCH ist), wird die Schleife beendet und die Programmausführung geht am Ende
- Bereits oben eingeführt ist "SOLANGE" ist eine Schleife: Solange die Bedingung (hier: b ungleich der Zahl Null) zutrifft (also WAHR ist), wird der Block ausgeführt.
Als Flussdiagramm
Beispiel 4: Parkplatzsuche
Weil der Begriff des Algorithmus so zentral ist: ein letztes Besipiel - die allseits beliebte Parkplatzsuche - TODO
- 1. Von chefkoch.de - https://www.chefkoch.de/rezepte/323461114392341/Tiramisu.html
- 2. Funktionsnamen (und andere Bezeichner) bestehen üblicherweise nur aus Buchstaben, Zahlen und Unterstrich ohne Leerzeichen, o.ä. Für einen Computer ist es deutlich leichter zu erkennen, dass "steif_schlagen" zusammengehört als "steif schlagen".
- 3. Englisch: while
- 4. schlagen() benötigt keine Parameter. Die leeren Klammern kennzeichnen in vielen Programmiersprachen Funktionen ohne Parameter. Zu Dokumentationszwecken werden die Parameter ebenfalls häufig weggelassen (solange die Funktion dann noch eindeutig benannt ist).
- 5. Meist dürfen Funktionsnamen o.ä. auch keine Umlaute enthalten (es kommt ja alles aus dem englischen). Das wäre hier dann also cremig_ruehren().
- 6. Englisch: foreach
- 7. Wenn ich dann etwas ändern möchte, muss ich es nur an einer Stelle machen (Faulheit!) und laufe nicht Gefahr, die andere Stelle zu vergessen.
- 8. Englisch: do ... while
- 9. Euklid wollte das "gemeinsame Maß" zweier Längen bestimmen. In seinen Worten: "Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die vorangehende misst".
Neuen Kommentar hinzufügen