© whiteMocca/Shutterstock.com
Teil 1: Algorithmen als Kernelemente des Programms - Definition und Klassen

Algorithmen in der Java-Praxis


Am Anfang der Ausbildung oder des Studiums hat man sich intensiv mit Algorithmen beschäftigt. Man hat etwas über formale Anforderungen gehört und die Verfahren in Lösungsklassen eingeteilt. Danach rücken die Fragen rund um Algorithmen meist in den Hintergrund, obwohl deren Anwendung und Entwicklung der Kern einer jeden Software sind. Zeit, die Grundlagen und neuere Entwicklungen auf den aktuellen Stand zu bringen.

Ein Algorithmus beschreibt ein Verfahren, um ein bestimmtes Problem zu lösen. Bekannte Algorithmen aus der alltäglichen Programmierpraxis sind zum Beispiel Such- und Sortieralgorithmen. Neben bekannten und seit Langem etablierten Verfahren aus dieser Klasse gibt es hier auch einige neue Entwicklungen, die zum Beispiel paralleles Rechnen, d. h. die Verteilung der Arbeitslast auf mehrere Prozessoren bzw. Rechenkerne, einbeziehen. In einer vierteiligen Artikelserie wollen wir uns dem spannenden Thema Algorithmen in Theorie und Praxis nähern und neben der Auffrischung von bekanntem Wissen auch neue Entwicklungen untersuchen. Das Thema des ersten Teils ist es, Grundlagen zu Algorithmen ins Gedächtnis zurückzurufen. Wir beginnen mit den formalen Anforderungen an einen Algorithmus, sehen uns die Einteilung in Klassen an und besprechen das Vorgehen für ein eigenes Lösungsverfahren. Spezifische Algorithmen wie Such- und Sortierverfahren stehen im zweiten Teil auf der Agenda. Im dritten Teil wird es um die Fragen gehen, wie übergeordnete Algorithmen, sogenannte Metaheuristiken, dazu eingesetzt werden, sehr komplexe Probleme zu lösen. Sie kommen zum Einsatz, wenn der Lösungsraum so groß ist, dass das komplette Durchsuchen im Lösungsraum eine zu große Zeitspanne beanspruchen würde. Hier lenkt man den Algorithmus nach bestimmten Kriterien in ein passendes Suchfeld, um eine möglichst gute Lösung zu finden.

Die Algorithmen werden wir in Pseudocode und/oder Java darstellen. Der abschließende Teil der Serie wird sich mit ausgewählten Java-Bibliotheken beschäftigen, die in der Praxis einige schwierige Probleme schnell lösen können.

Das Thema Algorithmen ist nicht nur interessant, sondern auch hochaktuell. Big Data, künstliche Intelligenz und erweiterte Verfahren der Datenanalyse verwenden ausgewählte Algorithmen. Möchte man umfassende Datenstrukturen sortieren, muss man sich über die Effizienz des eingesetzten Verfahrens Gedanken machen (Stichwort: parallele Verarbeitung).

Definition

„Ein Algorithmus ist ein präzises festgelegtes Verfahren zur Lösung von Problemen bzw. einer Klasse von Problemen, das aus endlich vielen, effektiv ausführbaren, elementaren Lösungsschritten besteht und in endlicher Zeit aus den Eingabedaten die gewünschten Ausgabedaten produziert.“ [1]

Es muss möglich sein, einen Algorithmus wiederholt anzuwenden. Jeder Algorithmus soll folgende Bedingungen erfüllen:

  • Spezifikation: Es muss genau angegeben sein, welche Eingabedaten erforderlich sind und welche Ausgabedaten der Algorithmus generieren soll.

  • Durchführbarkeit: Das Verfahren muss vollständig beschrieben, es muss tatsächlich ausführbar sein. Die Schrittfolge des Algorithmus muss durchgängig sein und darf keine Lücken aufweisen.

  • Terminiertheit: Es muss i. d. R. feststehen, wann der Algorithmus beendet ist. Auch die längste und komplizierteste Berechnung muss ein Ende finden. Findet ein Suchalgorithmus kein Ergebnis, endet die Suche dennoch. Terminierend heißt also ausdrücklich nur, dass der Algorithmus zu einem Ende kommt, nicht, dass er erfolgreich sein muss. Hier ist zu ergänzen, dass es Algorithmen geben kann, die kein definiertes Ende haben, d. h. in einer Art Endlosschleife laufen.

  • Determiniertheit: Der Algorithmus kann wiederholt angewendet werden.

  • Korrektheit: Sind die Eingabedaten korrekt, muss der Algorithmus ein korrektes Ergebnis produzieren.

  • Jeder Softwarealgorithmus muss diese Bedingungen erfüllen, damit er als zulässig gilt. In der Regel erreicht man diese Kriterien, wenn man ein Lösungsverfahren erarbeitet, man muss sich darüber keine Gedanken machen. Wichtige Klassen von Algorithmen lösen wiederkehrende Probleme. Wir wollen uns jetzt damit beschäftigen.

Klassen von Algorithmen

Bestimmte Probleme kommen immer wieder vor und man kann erprobte Algorithmen zur Lösung einsetzen. Such- und Sortieralgorithmen sind ein solches Beispiel. Wird ein verbessertes Verfahren entwickelt, das zum Beispiel performanter arbeitet, kann man es über Bibliotheken generisch zur Verfügung stellen. Typische Klassen von Algorithmen sind beispielsweise:

  • Suchverfahren wie sequenzielle Suche, Binärsuche oder paralleles Suchen

  • Sortierverfahren wie Bubble-Sort, Insert-Sort, Quick-Sort oder Merge-Sort

  • Mathematische und numerische Algorithmen sind Verfahren, die die Schrittfolge zur Berechnung bestimmter Sachverhalte darlegen

  • Algorithmen zur Verarbeitung von Zeichenketten, z. B. Mustererkennung (Pattern Matching) und Syntaxanalyse (Parsing)

  • Algorithmen für Optimierungsverfahren optimieren eine Größe in Hinblick auf eine bestimmte Zielstellung, z. B wird der kürzeste Weg zum Gegner in einem Computerspiel oft mit Hilfe des sogenannten A*-Algorithmus gesucht

  • Geometrische Algorithmen helfen, geometrische Grundformen wie Linien oder Splines anhand bestimmter Punkte im zwei- oder dreidimensionalen Raum zu zeichnen

  • Metaheuristiken...

headline from sands settings