Probleme

Erzählt man jeman­dem, man hätte ein Prob­lem, lässt sich häu­fig an dessen Reak­tion bereits erken­nen, um welchen Typ Mensch es sich handelt. Für die meisten Men­schen sind Prob­leme etwas lästiges. Sie stehen im Weg bei prak­tischen Tätig­keiten und quälen uns mit unnötigen Fragen nach rein theoretischen Eventualitäten. Es gibt sogar Probleme, für die bewiesen ist, dass sie deterministisch unlösbar sind, sogenannte formal unentscheidbare Probleme. Andere Probleme führen uns in komplexe Paradoxa und lösen in weiten Teilen der Gesellschaft ungewollte Faszination aus. Spricht man dagegen einen Physiker, Mathematiker oder Informatiker auf eine Problemstellung an, so ist die Reaktion eine komplett andere. In diesen Disziplinen ist das Problem existenziell, Ausgangspunkt für neues Wissen. Wo eine Frage nicht beantwortet ist, lohnt es sich erst recht genauer hinzuschauen. Diese Herangehensweise kann in manchen Situationen für einen Fremden schon recht irritierend sein.

In der Informatik sind viele Probleme im Speziellen interessant, da sie sich aktuell leicht wirtschaftlich nutzen lassen. Dem reinen Konsument elektronischer Medien mag es ja nicht bewusst sein, doch in jeder App, jedem Busfahrplan, jedem modernen Auto stecken unzählige hoch komplexe Algorithmen, logische Anleitungen zur Erzeugung eines bestimmten Ergebnisses. Von der Güte dieser Algorithmen hängt ab, wie hoch die Ladegeschwindigkeit von Videos online wie offline ist, wie lange der Handy-Akku hält, wie teuer der Kaffee beim Bäcker ist. Und kein Algorithmus ist perfekt. Obwohl der Trend immer mehr zu so genannten Künstlichen Intelligenzen geht, bleibt es wichtig, dass auch der Mensch sich weiterhin Gedanken macht. Denn, man ahnt es schon, so intelligent ist die KI gar nicht, da es sich auch hier „nur“ um Algorithmen aus Menschenhand handelt. Im Folgenden möchte ich ein Standardverfahren aus der Uni zeigen, mit welchem Probleme und Lösungsalgorithmen notiert werden können.

Einführung. Eines der bekanntesten Probleme der Informatik ist das Sortieren. Während wenige Elemente aus einer bekannten endlichen Menge noch von Hand zu sortieren sind, verliert man bei minimal größerem Umfang schnell den Überblick. Tipp: Versuchen Sie mal, beim Einkaufen die Produkte aufsteigend nach dem Preis auf das Kassenband zu legen! Wie schafft es dann Ihr Smartphone, sämtliche gespeicherten Dateien innerhalb weniger Sekunden nach dem verbrauchten Speicherplatz sortiert aufzulisten?

Um dieser Frage nachzugehen benötigen wir zu aller erst eine detaillierte Problembeschreibung. Hier wird festgehalten, was der Algorithmus leisten soll, also der Weg von der Ausgangssituation zum gewünschten Ergebnis. Bei unserem Beispiel wäre das folgendes: Eine endliche Menge Elemente soll anhand einer sortierbaren Eigenschaft, zum Beispiel einer eingetragenen Zahl, geordnet dargestellt werden, sodass die eingetragenen Zahlen am Schluss in aufsteigender Reihenfolge in der Liste stehen. Hierfür legen wir fest, dass die Reihenfolge von Elementen gleichen Wertes egal ist. Wir erhalten die Menge bereits als darstellbare Liste, müssen uns also nur noch um die Reihenfolge kümmern.

Um der Lösung einen Schritt näher zu kommen, greifen wir den populären Ansatz von Bubblesort auf. Im Ansatz werden die allgemeinen Gedanken geschildert, die sich der Programmierer zu Beginn der Lösung macht. Auch stehen hier erste Herangehensweisen, um dem Leser eine geeignete problemorientierte Sichtweise zu vermitteln. Bubblesort erhielt seinen Namen, weil die Elemente der Liste wie Luftblasen aufsteigen, bis sie sich an ihrer endgültigen Position verfangen. Als Grundlage dient hier das Prinzip, zwei benachbarte Elemente genau dann zu vertauschen, wenn ihre Reihenfolge gemäß der herzustellenden Ordnung falsch herum ist. Elemente gleichen Wertes werden nicht getauscht. Die Sortierung ist dann abgeschlossen, wenn keine Elemente mehr zu vertauschen sind.

Und damit kommen wir zur Lösung des Problems. Nicht immer muss die Lösung einen perfekten Programmcode enthalten, in der Regel genügt ein auskommentierter Pseudocode oder eine ausgeschriebene Formulierung der Anweisungen. Gerade bei mathematischen Problemen lässt sich der Algorithmus auch als rekursive Funktionsgleichung beschreiben. Wer sich für eine genaue Implementierung von Bubblesort oder anderen Sortieralgorithmen interessiert, dem empfehle ich die Suche bei Wikipedia, die in diesem Bereich sehr gut aufgestellt ist. Ausgeschrieben könnte der Algorithmus folgendermaßen aussehen:

1. Setze die Positionsmarke p auf 1. Vergleiche das erste (Position p) mit dem zweiten (Position p+1) Element und setze die boolsche Variable b auf false.
2. Ist der Wert des ersten Elements größer als der Wert des zweiten Elements, vertausche die beiden Elemente, indem dem ersten Element die Position des zweiten Elements zugeordnet wird und dem zweiten Element die Position des ersten Elements. Setze in diesem Fall b auf true.
3. Gehe zum nächsten Element weiter, indem die Positionmarke um eins erhöht wird.
4. Ist das betreffende Element nicht das letzte der Liste, gilt also, dass die Länge der Liste größer als die Positionsmarke ist (vorausgesetzt, man beginnt bei 1 zu zählen, was für Informatiker eher unüblich ist), vergleiche das betreffende Element mit dem nachfolgenden (Element an der Position p+1) und springe zu Punkt 2.
5. An dieser Stelle gilt, dass das betreffende Element das letzte der Liste ist. Ist b gleich true, springe zu Punkt 1. Andernfalls ist die Liste sortiert und kann ausgegeben werden.

Als nächstes muss die Korrektheit gezeigt werden, also der Beweis, dass dieser Algorithmus tatsächlich das Problem für jede beliebige Eingabe löst. Das Mittel der Wahl ist hier die Vollständige Induktion, doch auf dieser Seite soll auch eine informelle Begründung ausreichen. Für unser Beispiel definieren wir uns hierfür die Fehlstandszahl als die Summe der Entfernungen der Elemente von ihren endgültigen Positionen. Auf einer sortierten Liste der Länge 10, bei welcher das erste und das letzte Element vertauscht sind, beträgt die Fehlstandszahl also 18. Betrachtet man nun den Algorithmus fällt auf, dass die Fehlstandszahl bei jeder Vertauschung erniedrigt wird. Da jedes Element mit bei jedem Durchlauf mit beiden direkten Nachbarn verglichen und bei Bedarf vertauscht wird und kein Element „vergessen“ wird, da die Positionsmarke von 1 bis Länge der Liste läuft, wird die Fehlstandszahl also bei jedem sogenannten Schleifendurchlauf (einmaliges Ausführen der Schritte 1 bis 5) erniedrigt. Terminiert also der Algorithmus, ist die Ausgabe korrekt (Fehlstandszahl gleich 0). Der Algorithmus terminiert (endet in endlicher Zeit), da die Liste eine endliche Anzahl von Elementen enthält und die Fehlstandszahl bei jedem Schleifendurchlauf erniedrigt wird, es sei denn, es ist der letzte Durchlauf.

Zum Schluss soll in der Laufzeitanalyse noch untersucht werden, wie lange ein Computer abhängig von der Eingabegröße bräuchte, um das Ergebnis zu ermitteln. Bei Bubblesort hängt die Laufzeit maßgeblich von der Anzahl der Schleifendurchläufe ab. Im Best Case (Liste bereits aufsteigend sortiert) ist dies eins, im Worst Case (Liste absteigend sortiert) gleich der Anzahl der Elemente minus eins, da das letzte Element genau so oft vertauscht werden muss. Man sagt auch, im Best Case ist die Laufzeit linear zur Eingabegröße, im Worst Case quadratisch.

Alle hier präsentierten Algorithmen einschließlich Programmcode sind meine persönlichen Entwürfe und somit nicht zur Implementierung für professionelle Anwendungen geeignet. Weiter möchte ich darauf hinweisen, dass ich nicht für die Korrektheit der dargestellten Lösungen garantiere. Ich möchte lediglich vermitteln, wie derartige Probleme strukturiert sind und wie man sich konstruktiv an deren Lösung beteiligen kann.