Algorithmen Teil 1: Was ist ein Algorithmus?
Algorithmen beherrschen die moderne Gesellschaft. Sie stellen die Grundlage eines jeden Computerprogramms dar – und damit vieler Prozesse, die die Wirtschaft, das Privatleben und sogar die Politik bestimmen. Für viele Menschen stellt der Begriff Algorithmus ein Synonym für ein Computerprogramm oder sogar für die Informatik im Allgemeinen dar. Während es sich bei einem Computerprogramm tatsächlich im Wesentlichen um sich Umsetzung von Algorithmen handelt, ist die zweite Annahme jedoch nicht ganz korrekt. Algorithmen spielen in der Informatik zwar eine sehr wichtige Rolle. Allerdings gibt es hierbei noch einige weitere Bereiche, die von Bedeutung sind.
Viele Menschen haben zwar eine gewisse Vorstellung davon, was ein Algorithmus ist. Allerdings sind diese Ideen häufig nicht ganz klar und präzise. Deshalb stellen wir hier die Frage: Was ist ein Algorithmus in der Informatik? Dieser Artikel besteht aus zwei Teilen. Im ersten Teil stellen wir Ihnen die Definition des Algorithmus, sowie dessen Entwicklungsgeschichte vor. Im zweiten Teil präsentieren wir Ihnen dann zwei wichtige Anwendungsbeispiele.
Der Algorithmus als eindeutige Handlungsanweisung
Ein Algorithmus stellt eine eindeutige Handlungsanweisung dar, die dazu dient, ein bestimmtes Problem zu lösen. Diese Handlungsanweisung besteht aus einzelnen Schritten, die jeweils eindeutig definiert sein müssen. Man kann sich dies ähnlich wie ein Kochrezept vorstellen. Wenn Sie beispielsweise einen Pfannkuchen backen wollen, kann das vereinfacht so aussehen:
✔️1. Geben Sie Mehl, Milch, Eier und etwas Salz in eine Schüssel.
✔️2. Verrühren Sie die Zutaten, bis eine einheitliche Masse entsteht.
✔️3. Geben Sie den Teig in eine heiße Bratpfanne mit etwas Öl.
✔️4. Wenden Sie den Pfannkuchen nach einiger Zeit.
✔️5. Nehmen Sie den Pfannkuchen aus der Pfanne, wenn er goldgelb gebraten ist.
Hierbei sind fünf einzelne Handlungsanweisungen vorgegeben. Damit lösen Sie das Problem der Zubereitung eines Pfannkuchens. Das bedeutet, dass hierbei die Grundvoraussetzungen dafür erfüllt sind, dass es sich um einen Algorithmus handelt. Ein Problem besteht jedoch in der genauen Definition der einzelnen Schritte. Beispielsweise fehlen eindeutige Mengenangaben und auch sonst ist die Definition der einzelnen Schritte aus mathematischer Sicht nicht sehr präzise. Davon abgesehen können wir dieses Rezept jedoch als Algorithmus bezeichnen. Hierbei ist weder vorgegeben, dass es sich dabei um ein Problem aus dem Bereich der Informatik oder der Mathematik handeln muss, noch, dass die einzelnen Schritte in Form eines Computerprogramms beschrieben sind. Es ist auch möglich, die natürliche menschliche Sprache zu verwenden. Dennoch wäre es auch bei diesem Algorithmus möglich, ihn in den Bereich der Informatik zu übertragen. Wenn Sie beispielsweise einen Roboter für die Herstellung von Pfannkuchen programmieren möchten, können Sie ihn als Grundlage verwenden.
Was ist ein Algorithmus – einfach erklärt
Wenn man den Algorithmus nun mit ganz einfachen Worten erklären will, kann man sagen, dass es sich dabei um eine präzise schrittweise Anweisung handelt, um ein Problem zu lösen.
Einfaches Beispiel für einen Algorithmus in der Mathematik
Das Beispiel des Kochrezepts hat sicherlich anschaulich dargestellt, wie ein Algorithmus aufgebaut sein kann. Meistens kommen Algorithmen jedoch zum Einsatz, um bestimmte mathematische oder informatische Probleme zu lösen. Deshalb wollen wir auch hierfür ein Beispiel angeben. Dazu erstellen wir einen Divisionsalgorithmus. Dabei wollen wir eine Zahl, die wir als Dividend bezeichnen, durch eine andere Zahl, die die Bezeichnung Divisor trägt, teilen. Dabei erhalten wir ein Ergebnis und einen Rest zurück. In der Grundschule haben Sie hierfür sicherlich bereits passende Methoden erlernt – beispielsweise das schriftliche Teilen. Dabei sind für die einzelnen Schritte jedoch ebenfalls Divisionen notwendig. Diese sind in der Informatik nicht ganz einfach durchzuführen. Deshalb erstellen wir nun einen Divisionsalgorithmus, der diese Aufgabe nur auf Basis von Additionen, Subtraktionen und Größenvergleichen löst. Als Eingabewerte sind dabei der Dividend und der Divisor vorgegeben:
✔️1. Setzen Sie den Wert für das Ergebnis auf 0
✔️2. Weisen Sie dem Rest den Wert des Dividenden zu.
✔️3. Wiederholen Sie die folgenden Anweisungen so lange, wie der Rest größer als der Divisor ist:
✔️- Ziehen Sie den Divisor vom Wert des Rests ab.
✔️- Erhöhen Sie den Wert des Ergebnisses um 1.
Wenn Sie diese drei Anweisungen konsequent befolgen, weisen sowohl das Ergebnis als auch der Rest den richtigen Wert auf, wenn der Algorithmus beendet ist. Daher haben Sie damit das Problem korrekt gelöst.
Die Implementierung der Algorithmen
Damit aus dem Algorithmus ein Computerprogramm wird, ist es notwendig, diesen zu implementieren. Der Algorithmus stellt dabei das Grundgerüst dar, dass die einzelnen Schritte genau vorgibt. Wie diese umzusetzen sind, hängt dann jedoch von der gewählten Programmiersprache ab. Diese gibt genaue Regeln vor, wie Sie diese Anweisungen in eine für den Computer verständliche Sprache übertragen können. Je nach Programmiersprache können diese Handlungsanweisungen jedoch einige Unterschiede aufweisen. Um die Implementierungsmöglichkeiten aufzuzeigen, gestalten wir nun zwei Computerprogramme in verschiedenen Sprachen. Diese implementieren jeweils den Divisionsalgorithmus aus dem vorigen Abschnitt. Dabei geben wir als Dividend den Wert 14 und als Divisor den Wert 3 vor. Für die Überprüfung des Programms geben wir am Schluss die Werte für das Ergebnis und für den Rest aus. Wie Sie leicht nachrechnen können, muss das Ergebnis dabei 4 und der Rest 2 betragen.
Wenn Sie den oben beschriebenen Algorithmus beispielsweise in einem Python-Programm implementieren möchten, könnte das so aussehen:
dividend = 14
divisor = 3
ergebnis = 0
rest = dividend
while rest > divisor:
rest -= divisor
ergebnis += 1
print("Ergebnis:", ergebnis)
print("Rest:", rest)
Nun erstellen wir hierfür ein Java-Programm:
public class Division {
public static void main(String[] args) {
int divident = 14;
int divisor = 3;
int ergebnis = 0;
int rest = divident;
while (rest > divisor){
rest -= divisor;
ergebnis ++;
}
System.out.println("Ergebnis: " + ergebnis);
System.out.println("Rest: " + rest);
}
}
Sie sehen, dass die Implementierungen je nach Sprache ganz anders aussehen können. Da der zugrundeliegende Algorithmus jedoch der gleiche ist, führen sie genau zum gleichen Ergebnis.
Die Geschichte der Algorithmik
Die Algorithmik ist ein sehr wichtiges Gebiet der Mathematik und der Informatik. Die Ursprünge reichen bereits mehrere Jahrtausende zurück. Deshalb wollen wir hier einen kurzen Überblick über die Geschichte dieses Forschungsbereichs geben.
Entwicklung der ersten Algorithmen in der Antike
Die ältesten bekannten Algorithmen entstanden bereits vor etwa 4.500 Jahren. Babylonische Mathematiker entwickelten Algorithmen für vielfältige Berechnungen – beispielsweise Divisionsalgorithmen wie denjenigen, den wir oben vorgestellt haben. Auch die alten Ägypter entwickelten zahlreiche Algorithmen. Zu dieser Zeit war jedoch weder der Begriff Algorithmus verbreitet, noch gab es eine formale Definition für die beschriebene Vorgehensweise.
Abu Dschaʿfar Muhammad ibn Musa al-Chwārizmī: Namensgeber des Algorithmus
Als Erfinder des Algorithmus wird häufig fälschlicherweise der persische Mathematiker Abu Dschaʿfar Muhammad ibn Musa al-Chwārizmī genannt. Dieser erstellte wahrscheinlich im Jahre 825 ein Werk über das arabische Zahlensystem. Als dieses mehrere Jahrhunderte später ins Lateinische übersetzt wurde, transkribierte der Übersetzer den Namen al-Chwārizmī zu „Algorizmi“ – was jedoch nur entfernt mit dem eigentlichen Namen übereinstimmt. Daraus entwickelte sich im Laufe der Zeit der Begriff Algorithmus. Allerdings hatte dieser ursprünglich eine ganz andere Bedeutung. Er bezog sich auf das dezimale Zahlensystem, das al-Chwārizmī in seinem Werk beschrieben hatte. Die heutige Bedeutung erhielt der Begriff erst im 19. Jahrhundert. Demnach ist al-Chwārizmī zwar der Namensgeber des Algorithmus, seine Forschungsarbeit hatte dazu jedoch keinerlei Bezug.
Definition des Algorithmus durch Alan Turing
Der Begriff Algorithmus war unter den Mathematikern des 19. und des frühen 20. Jahrhunderts nicht sehr beliebt. Das lag daran, dass es damals keine formale Definition für diesen Begriff gab. Diese wurde erst Mitte des 20. Jahrhunderts erstellt – durch den bedeutenden Mathematiker und Urvater der Informatik, Alan Turing. Dieser hatte zwischen 1936 und 1937 die sogenannte Turing machine entworfen. Dabei handelt es sich um einen theoretischen Entwurf für ein Gerät, das Berechnungen durchführen und Zeichen manipulieren kann. In diesem Rahmen stellte er auch eine Definition für die Berechenbarkeit eines Ausdrucks auf. Diese theoretischen Überlegungen stellen bis heute eine der wichtigsten Grundlagen der Informatik dar.
Die formale Definition des Algorithmus ist eng mit dieser Turing Machine verbunden. Sie besagt, dass eine Berechnungsvorschrift für die Lösung eines Problems dann als Algorithmus bezeichnet wird, wenn sich dafür eine Turing machine entwerfen lässt, die bei jeder Eingabe, die eine Lösung besitzt, zu einem Ergebnis kommt.
Erster Computeralgorithmus durch Ada Lovelace
Der erste Computeralgorithmus entstand jedoch lange bevor der Algorithmus überhaupt definiert war. Er geht auf die britische Mathematikerin Ada Lovelace zurück. Diese schrieb 1843 Kommentare zur sogenannten Analytical Machine des Mathematikers Charles Babbage. Dabei handelt es sich um ein theoretisches Modell für eine Rechenmaschine, die ähnliche Berechnungen wie ein Computer durchführen könnte. Zwar war es damals noch nicht möglich, diesen Entwurf in die Praxis umzusetzen. Lovelace entwarf in ihren Kommentaren jedoch eine Möglichkeit, wie man mit dieser Maschine die Bernoulli-Zahlen berechnen könnte. Bei diesen Anweisungen handelte es sich um einen Algorithmus – obwohl der Computer, für den er geschrieben war, niemals funktionierte.
Algorithmen prägen die moderne Gesellschaft
Im ersten Teil unseres Artikels zu den Algorithmen haben wir aufgezeigt, was dieser Ausdruck genau bedeutet und einige Beispiele dafür entwickelt. Im zweiten Teil werden wir dann zwei bekannte Algorithmen vorstellen, die bis heute bei vielen Berechnungen zum Einsatz kommen – den Dijkstra Algorithmus und den Luhn Algorithmus. Wenn Sie noch etwas tiefer in dieses Thema eintauchen möchten, können Sie sich dabei über einige wichtige praktische Anwendungsmöglichkeiten informieren.