· 

Was ist ein Algorithmus?

1. Einführung

Sie begegnen uns tagtäglich. Zu Hause, in der Schule, auf der Arbeit und beim Einkaufen. Einfach überall. Ohne, dass wir es merken. Algorithmen. Sie sind der Grundpfeiler für so ziemlich alles, was uns in einer zunehmend digitalisierten Welt umgibt. Sie analysieren unser Kaufverhalten, empfehlen uns Musik, helfen uns bei der Partnersuche und bestimmen mit, was wir in unserer Freizeit auf YouTube und anderen Streaming-Plattformen ansehen. Auch unser Lernverhalten wird durch sie analysiert und sie helfen uns, die für uns optimalen Bildungsangebote zu finden und zur richtigen Zeit am richtigen Ort zu konsumieren.

2. Was ist ein Algorithmus?

Doch was genau ist denn nun ein Algorithmus? Ein Algorithmus ist (vereinfacht ausgedrückt) eine fest definierte und endliche Vorgehensweise, mit der ein Problem gelöst werden kann. Jetzt siehst du auch, weshalb sie so wichtig sind: Probleme sind quasi omnipräsent und es ist unsere Aufgabe als Menschen, diese Probleme anzugehen und zu lösen. Seien es die Behandlung von Krankheiten, fehlerhafte Software oder das Backen leckerer Muffins. Für all diese Probleme gibt es Lösungen, die man aufschreiben und deren Schritte man nacheinander abarbeiten kann, um am Ende das Problem zu lösen. Die einzelnen Schritte sind in Form von Anweisungen klar definiert, werden in einer bestimmten Reihenfolge abgearbeitet und führen bei gleicher Eingabe immer zu den gleichen Ergebnissen. 

Was viele nicht Wissen: der Erzfeind vieler Schüler und Studenten - die Mathematik - steckt voller Algorithmen, die der ein oder andere Lehrer gerne als "Rezept" bezeichnet. Nehmen wir als Beispiel die Mitternachtsformel.Diese Formel   $$x_{1,2}=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$ ist die allgemeine Antwort auf die Frage, wie die Lösungen der quadratischen Gleichung \(ax^2+bx+c=0\) lautet. Der Algorithmus zum Lösen quadratischer Gleichungen ist hierbei die Mitternachtsformel gepaart mit der Anweisung "setze die gegebenen Werte für \(a,b\) und \(c\) in die Formel ein und berechne damit das Ergebnis".

Ich habe dieses Verfahren in ein Computerprogramm gegossen, mit dem du alle quadratischen Gleichungen lösen kannst. Das Programm liefert dir sogar eine ausführliche Antwort darauf, wie es auf die Lösung gekommen ist. Und woher kann das Programm das? Durch den Entwickler, der den Algorithmus mit einer Programmiersprache in eine für den Computer lesbare Form übersetzt hat! Und genau das ist die Aufgabe eines Informatikers!

Ein anderes Beispiel: wenn du eine Kurvendiskussion durchführst, klapperst du im Prinzip eine Reihe von Anweisungen ab, die der Computer allerdings weitaus besser kann als du es jemals wirst. Gehe mal auf WolframAlpha, gib in das Fragenfeld x^2 ein und drücke ENTER. Du wirst erstaunt sein, was dir der Computer alles für Aufgaben abnimmt und mit welcher Geschwindigkeit und Präzision er die Antworten präsentiert. Deshalb hört man so häufig von Studenten, dass die Schulmathematik nichts anderes als "Rechnen" sei, da man nichts anderes macht als Algorithmen abzuarbeiten (ohne wirklich darüber nachdenken zu müssen, was man gerade eigentlich warum macht). Es ist natürlich eine gute Nachricht für dich, der du jetzt weißt, dass du in der Schule eigentlich wie beim LEGO-Bauen oder Backen nur Anleitungen befolgen musst, doch wirklich vorbereiten wird dich das auf dein Arbeitsleben nur bedingt, denn im "New Work" Zeitalter ist es umso wichtiger, dass du für die Herausforderungen der Zukunft gewappnet bist - und das wird nicht durch Auswendiglernen und Anwenden des Gauß-Algorithmus erreicht, sondern vielmehr durch die Fähigkeit, den Gauß-Algorithmus selbst herzuleiten bzw. dem Computer beizubringen, wie er den Gauß-Algorithmus anwenden kann.

Es ist unsere Aufgabe, zukünftig nicht nur Lösungen für bestimmte Ausprägungen eines eigentlich abstrakten Problems zu finden, sondern direkt das abstrakte Problem zu erkennen und dieses zu lösen. Mit anderen Worten: wir müssen in Zukunft für ein Problem Algorithmen entwerfen, mit deren Hilfe man das Problem lösen kann. Die konkrete Lösung ist dann Aufgabe des Computers, dem man durch ein Programm beibringt, wie er das zuvor formulierte und durch einen Algorithmus gelöste Problem lösen kann.


3. Eigenschaften eines Algorithmus

Jetzt hast du bereits eine Menge über den Algorithmus gelernt. Nun soll noch einmal klar definiert werden, welche Eigenschaften erfüllt sein müssen, damit man bei einer Anleitung bzw. einer Handlungsvorschrift tatsächlich von einem Algorithmus sprechen kann.

3.1. Eindeutigkeit

Ein Algorithmus muss eindeutig sein. Er darf keine widersprüchliche Beschreibung besitzen oder Schritte definieren, die logisch nicht miteinander vereinbar sind.

3.2 Finitheit

Der Algorithmus muss mit endlich vielen Worten und Zeichen beschrieben werden können. Finitheit bezieht sich hier also auf die Endlichkeit der Beschreibung des Algorithmus.

3.3 Terminierung

Neben der Finitheit muss ein Algorithmus in endlich vielen Schritten terminieren (d. h. irgendwann muss er zu einem Ende kommen) und ein Ergebnis liefern. Wann und ob ein Programm jemals aufhört zu rechnen, kann man paradoxerweise aber nicht mit einem Algorithmus ermitteln. Das ist das sogenannte Halteproblem, zu dem noch ein separates Video folgen wird.

3.4 Determinismus

Es muss zu jedem Zeitpunkt in der Abarbeitung klar sein, welcher Schritt als nächstes folgt. Es besteht also bei jedem Schritt höchstens ein Folgeschritt.

3.5 Determiniertheit

Auch wenn die Begriffe Determinismus und Determiniertheit ähnlich klingen, meint Determiniertheit etwas anderes, nämlich dass bei der gleichen Eingabe in den Algorithmus das gleiche Ergebnis herauskommt. Wenn du also den Algorithmus zum Addieren zweier Zahlen auf 5 und 2 anwendest, dann muss, wenn du das 100 mal machst auch 100 mal 7 als Ergebnis herauskommen!

3.6 Ausführbarkeit

Die einzelnen Schritte im Algorithmus müssen - für Mensch oder Maschine - verständlich formuliert und ausführbar sein.

Wenn du selbst einen Algorithmus für ein bestimmtes Problem formulieren willst, musst du sicherstellen, dass all die genannten Eigenschaften erfüllt sind.


4. Beispiel

Als Beispiel kannst du dir ein Rezept (z. B. zum Backen eines leckeren Käsekuchens) vorstellen. Wenn es sich dabei tatsächlich um einen Algorithmus handelt, dann müssen alle sechs Eigenschaften eines Algorithmus erfüllt sein.

  • Eindeutigkeit: Ein Rezept besitzt für gewöhnlich keine widersprüchlichen Beschreibungen und genaue Angaben über die Zutaten, sowie die Zubereitungsreihenfolge. Allerdings müsste man formal korrekt definieren, was man z. B. unter "einer Prise Salz" versteht.
  • Finitheit: Die Finitheit ist gegeben, da ein Rezept in endlich vielen Wörtern beschrieben werden kann.
  • Terminierung: Ein Rezept ist nach einer endlichen Zeit fertiggekocht und man kann sich das Ergebnis schmecken lassen. Es gibt kein Rezept, das niemals endet. Bei vielen Rezepten wird sogar angegeben, wie lange dieser Algorithmus braucht, um zu terminieren.
  • Determinismus: Bei einem Rezept ist zu jedem Zeitpunkt klar, welcher Schritt als nächstes ausgeführt werden soll. Die einzelnen Schritte sind für gewöhnlich mit Nummern versehen, sodass man als Koch/Bäcker die Reihenfolge einhalten kann. 
  • Determiniertheit: Wenn du mit den exakt gleichen Zutaten und denselben Bedingungen das Rezept nachkochen würdest, würde jedesmal das gleiche Ergebnis herauskommen. Wenn du ein Rezept für Käsekuchen nachbackst, kann es nicht passieren, dass du auf einmal eine Schwarzwälder-Kirschtorte vor dir stehen hast. Auch wenn es nach den Kriterien eines Algorithmus nicht passieren darf, kann es sein, dass sich die Ergebnisse geschmacklich unterscheiden, da der Mensch keine Maschine ist und nicht jedesmal die exakt gleichen Bedingungen herstellen kann.
  • Ausführbarkeit: Die Ausführbarkeit ist gegeben, da Rezepte in der Sprache des jeweiligen Kochs oder Bäckers geschrieben sind. Wenn die entsprechenden Zutaten und Küchenutensilien vorhanden sind, ist ein Nachkochen/Nachbacken möglich. Auch Maschinen können (nach entsprechender Programmierung) Rezepte nachkochen/nachbacken.

5. Arten von Algorithmen

Man kann verschiedenen Arten von Algorithmen unterscheiden. Diese Algorithmenklassen werden maßgeblich durch ihre Funktionsweise definiert:

  • Rekursive Algorithmen: Bei einem rekursiven Algorithmus wird der Algorithmus mit einem immer einfacheren Problem vom selben Typ aufgerufen, bis man ein Ergebnis erreicht, an dem der Algorithmus terminieren soll. Solche Algorithmen werden verwendet, um Probleme zu lösen, die in einfachere oder kleinere Probleme desselben Typs umgewandelt werden können.
  • Backtracking Algorithmen: Diese Algorithmenklasse geht nach dem Trial-and-Error-Prinzip vor, d.h. es wird versucht, eine Teillösung zu einer Gesamtlösung auszubauen. Wenn bereits erkennbar ist, dass eine Teillösung nicht zu einer Gesamtlösung führen kann, werden die zuletzt ausgeführten Schritt rückgängig gemacht und ein alternativer Weg ausprobiert. Dadurch werden alle infrage kommenden Wege getestet. Nach endlich langer Zeit wird entweder eine Lösung gefunden oder es wird festgestellt, dass keine Lösung existiert. Ein Beispiel ist die Lösung des Damenproblems.
  • Greedy-Algorithmen: Greedy bedeutet übersetzt "gierig". Dieser Algorithmentyp sucht nach einer optimalen Lösung. Durch seine "Gier" begnügt er sich mit der erstbesten optimalen Lösung in einem abgesteckten Bereich, statt auf eine global optimale Lösung zu bauen. Ein Beispiel hierfür ist der Huffman-Code bzw. Huffman-Baum.
  • Divide-and-Conquer-Algorithmen: Bei dieser Algorithmenklasse wird ein großes Problem in viele kleine Teilprobleme zerlegt und diese dann schrittweise gelöst. Anschließend werden die Ergebnisse dieser Teilprobleme zur Lösung des Gesamtproblems kombiniert. Beispiele dafür sind die Sortieralgorithmen Quick Sort und Merge Sort.
  • Dynamische Optimierungsalgorithmen: Solche Algorithmen merken sich das vorangegangene Ergebnis und nutzen es, um neue Ergebnisse zu finden. Durch das Speichern dieser Teilproblemlösungen, müssen sie zu einem späteren Zeitpunkt nicht erneut berechnet werden, was die Laufzeit reduziert.
  • Randomisierte Algorithmen: Ein solcher Algorithmus verwendet mindestens einmal während der Abarbeitung eine Zufallszahl, um eine Entscheidung zu treffen. Ein Beispiel dafür ist der Sortieralgorithmus Quick-Sort, der eine Zufallszahl zur Bestimmung des Pivot-Points nutzt.
  • Brute-Force Algorithmen: Bei einem Brute-Force-Algorithmus werden systematisch alle Möglichkeiten durchprobiert. Solche Algorithmen werden auch genutzt, um eine optimale Lösung für ein Problem zu finden. Sie sind oft sehr ineffizient, da (ohne Intelligenz) einfach alles ausprobiert wird.