Algorithmen in der Informatik

Was sind Algorithmen und was können sie?

Moderne Computer können sehr komplexe Aufgaben ausführen. Jede Aufgabe besteht aus wohldefinierten Prozeduren, die als Algorithmen bezeichnet werden. Computer verwenden Algorithmen um die Aufgaben ausführen, die wir von ihnen erwarten.

Um zu verstehen was ein Algorithmus ist können wir uns zunächst vorstellen wie wir an einem typischen Tag einen Computer verwenden. Beispielsweise beginnen wir, an einem Bericht/Word-Dokument zu arbeiten, und wenn wir einen Absatz abgeschlossen haben, führen wir eine Rechtschreibprüfung durch. Wir öffnen eine Tabellenkalkulationsanwendung, um einige finanzielle Projektionen zu erstellen, um besser beurteilen zu können, ob uns einen neuen Autokredit leisten können. Wir verwenden einen Webbrowser, um online nach einer bestimmt Art von Auto zu suchen, das wir kaufen möchten.

In den meisten Fällen machen wir uns das zwar nicht bewusst, aber all diese Operationen, die von unserem Computer ausgeführt werden, bauen auf Algorithmen auf.

Was ist ein Algorithmus?

Eine gängige Definition von Algorithmus in der Informatik beschreibt diesen als eine definierte Prozedur, die es einem Computer ermöglicht, ein Problem zu lösen. Eine andere Definition ist, dass es sich um eine Folge eindeutiger Anweisungen handelt. Die Verwendung des Begriffs “eindeutig” weist darauf hin, dass kein Raum für subjektive Interpretation besteht. Jedes Mal, wenn wir unseren Computer bitten, den gleichen Algorithmus auszuführen, wird er dies auf genau die gleiche Weise tun, mit hoffentlich genau dem gleichen Ergebnis.

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.

Betrachten wir die genannten Beispiele noch einmal: Die Rechtschreibprüfung verwendet Algorithmen. Programme zur Tabellenkalkulation und Suchmaschinen verwenden ebenfalls Algorithmen. Tatsächlich ist es in der Informatik schwer vorstellbar, dass es Aufgaben gibt, die von einem Computer ausgeführt werden und dabei keine solche Definition von Abläufen zum Einsatz kommt.

Was ist ein Computeralgorithmus in der Informatik?

Um einen Computer dazu zu bringen etwas zu tun, muss jemand ein Computerprogramm (als genau genommen eine Abfolge von Befehlen an den Computer) schreiben. Um ein Computerprogramm zu schreiben, müssen wir dem Computer Schritt für Schritt genau sagen, was er tun soll. Der Computer führt dann das Programm aus und folgt “stumpf” jedem vorgegebenen Schritt, um das Endziel zu erreichen.

Wenn wir dem Computer sagen, was zu tun ist, können wir auch wählen, wie genau er dabei vorgehen soll. Hier kommen Computeralgorithmen ins Spiel. Der Algorithmus ist die grundlegende Technik, um die Arbeit zu erledigen. Folgen wir einem Beispiel, um das Algorithmuskonzept zu verstehen. Nehmen wir an, wir haben einen Freund, der am Flughafen ankommt, und unser Freund muss nun irgendwie vom Flughafen zu unserem Haus kommen. Hier sind vier verschiedene Algorithmen, die wir unserem Freund geben können, damit er zu uns nach Hause kommt:

Die Taxi-Variante:

• Geh zum Taxistand.
• Steige in ein Taxi.
• Gib dem Fahrer meine Adresse.

Die Anruf-Variante:

• Wenn Dein Flugzeug ankommt, rufe mein Handy an.
• Triff mich außerhalb der Gepäckausgabe.

Die Mietwagen-Variante:

• Nimm den Shuttle zum Autoverleih.
• Miete ein Auto.
• Folge der Wegbeschreibung, um zu meinem Haus zu gelangen.

Die Bus-Variante:

• Außerhalb der Gepäckausgabe in einen Bus der Linie F steigen.
• An der Haltstelle Hauptstraße in einen Bus der Linie E umsteigen.
• Steige in der Schillerstraße aus.
• Gehe zwei Blocks Richtung Norden bis zu meinem Haus.

Leistung und Kosten von Algorithmen

Alle vier dieser Algorithmen erreichen genau das gleiche Ziel, aber jeder Algorithmus verfährt auf völlig unterschiedliche Weise. Jede Variante ist auch mit spezifischen Kosten und einer anderen Reisezeit verbunden. Ein Taxi zum Beispiel ist wahrscheinlich der schnellste Weg, aber auch der teuerste. Den Bus zu nehmen ist definitiv weniger teuer, aber viel langsamer. Wir wählen unseren Weg basierend auf den Umständen die in unserem Fall zu erwarten sind.

Sortieralgorithmen

In der Computerprogrammierung gibt es oft viele verschiedene Möglichkeiten um eine gegebene Aufgabe zu erfüllen. Jeder mögliche Weg hat Vor- und Nachteile in verschiedenen Situationen. Das Sortieren beispielsweise ist ein Themengebiet, an dem viel geforscht wurde, weil Computer viel Zeit damit verbringen, Listen zu sortieren. Hier sind fünf verschiedene Algorithmen, die beim Sortieren verwendet werden:

Bin sort / Bucket sort
Merge sort
Bubble sort
Shell sort
Quicksort

Wenn man eine Million ganzzahlige Werte zwischen 1 und 10 hat und diese sortieren muss, ist Bin Sort der richtige Sortieralgorithmus. Wenn man eine Million Buchtitel hat, ist Quicksort möglicherweise der beste Weg. Wenn wir die Stärken und Schwächen der verschiedenen Vorgehnsweisen kennen, können wir die für die jeweilige Aufgabe den am besten geeigneten auswählen. Wenn wir die Informatik als eine Pyramide betrachten, stehen Algorithmen per Definition ganz unten. Sie sind die Grundlage von allem, und die grundlegende Sache, über die jeder ehrgeizige und kompetente Informatiker zwangsläufig ein vertieftes Wissen haben muss.

Computerprogramme basieren auf einer Ablauf-Definition. Eine einfache Definition von Algorithmus lautet in der Informatik wie folgt:

Es handelt sich dabei um eine Reihe von Schritten, die definieren, wie ein Problem zu lösen ist. Auf Computern laufen Software-Programme deren Aufgabe es ist, Probleme zu lösen.

Zusammenfassung

Jetzt können wir sagen, dass eine Software eine konkrete Definition eines solchen Ablaufs für Computer ist. Es kann einen Algorithmus geben, der die effiziente Sortierung und Neuordnung von Millionenzahlen beschreibt, einen, der angibt, wie eine Website in ein Suchergebnis einzuordnen ist, einen , der angibt, wie ein Filter auf ein Bild angewendet wird, viele Algorithmen, die die KI eines Spiels definieren usw. All dies sind per Definition Algorithmen, sobald wir diese erstellt haben, ist der nächste Schritt, diese in einer bestimmte Programmiersprache zu formulieren. Sobald dies geschehen ist haben wir eine Software erstellt.

Hinweis: Der Algorithmus kann aus englischen Anweisungen und mathematischen Ausdrücken oder aus beiden bestehen. Wenn ein Algorithmus in einer solchen Form vorliegt (die drei, die ich gerade beschrieben habe), dann liegt er noch in abstrakter Form vor und muss mittels einer Programmiersprache in Software verwandelt werden. Wenn wir den Algorithmus dagegen direkt in einer Programmiersprache geschrieben haben, haben wir quasi eine Software bzw. ein Programm erstellt. Jetzt müssen wir nur noch optimieren und testen.

Beispiele von Algorithmen

Einige der Vorgehensweisen, die wir in der Informatik bei einfachen Programmen verwenden, sind intuitiv und von Natur aus in unser logisches Denken eingebettet, während andere, die komplexen, untersucht und verstanden werden müssen. Algorithmen sind in allen Bereichen der Informatik weit verbreitet. Ein Suchmaschinenalgorithmus beispielsweise nimmt Suchstrings aus Schlüsselwörtern und Operatoren als Eingabe auf, durchsucht entsprechend seiner Definition die zugehörige Datenbank nach relevanten Webseiten und gibt Ergebnisse zurück.

Ein Verschlüsselungsalgorithmus wandelt Daten gemäß bestimmter Aktionen um, um sie zu schützen. Ein geheimer Schlüsselalgorithmus wie beispielsweise der Datenverschlüsselungsstandard (DES) des US-Verteidigungsministeriums verwendet denselben Schlüssel zum Verschlüsseln und Entschlüsseln von Daten. Solange der Algorithmus ausreichend ausgefeilt ist, kann niemand, dem der Schlüssel fehlt, die Daten entschlüsseln.