Sortieren interaktiv
Ein Ausblick in die vertiefende Algorithmik – ganz ohne Computer.
MATERIALIEN
Natürlich gibt es viel mehr interessante Algorithmen als die bereits behandelten – wichtig für viele Aufgaben des Computer sind insbesondere solche, die sich mit der Verarbeitung grösserer Datenmengen beschäftigen.
Sortieralgorithmen
Um einen kleinen Ausblick zu bieten, wollen wir uns an dieser Stelle noch etwas mit dem Problem des Sortierens beschäftigen, u.a. weil
- effizientes Sortieren ein wichtiger Bestandteil vieler Algorithmen ist;
- es viele verschiedene Lösungen für dieses Problem (bzw. diese Problemklasse) gibt;
- dieses Beispiel die Frage aufwirft, wie man verschiedene Lösungsansätze für dasselbe Problem vergleicht.
Aufgabe
Einen interaktiven Einblick in die fortgeschrittenere Algorithmik bieten die Folien SortierenInteraktiv.pptx.pdf.
Witzig: Hier finden Sie die beiden besprochenen Sortier-Algorithmen als karikierte IKEA-Anleitung: KWICK SÖRT und MERGE SÖRT.
Algorithmen für verschiedene Herangehensweisen und Lösungswege für komplexere Probleme werden im Ergänzungsfach Informatik thematisiert.
Algorithmen vergleichen
Eine übliche – in den Folien angedeutete – Methode, um die Effizienz von Algorithmen abzuschätzen und zu vergleichen, hier noch als (fortgeschrittenes) Konzept:
Laufzeitkomplexität
Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe (bzw. der Grösse des Problems). Man spricht hier auch von der asymptotischen Laufzeit und meint damit – in Anlehnung an eine Asymptote – das Zeitverhalten des Algorithmus für eine potenziell unendlich grosse Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer für ein bestimmtes Problem, sondern vielmehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind. Die Frage ist also z.B., ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Weniger wichtige Faktoren (z.B. Konstanten) spielen dabei keine Rolle und werden üblicherweise ignoriert.
Bei der Abschätzung der Zeitkomplexität geht man üblicherweise vom „worst case“ aus, man berücksichtigt also die Anzahl Rechenschritte, die benötigt werden, wenn das spezielle Problem innerhalb der Problemklasse maximal ungünstig gewählt ist.
Analogie
Auf das erste Feld eines Schachbretts wird ein Reiskorn gelegt. Auf jedes weitere Feld soll jeweils die doppelte Menge Reis platziert werden: Wie viele Reiskörner werden benötigt?
Mit einer einfachen Komplexitätsabschätzung (hier Reiskörner statt Verarbeitungsschritte) wird klar, dass es vermutlich auf der ganzen Welt nicht genug Reis dafür gibt.
Besonders interessant sind solche Komplexitätsabschätzungen, wenn es nicht nur darum geht, welcher von mehreren Lösungsansätzen der bessere ist, sondern darum, ob ein gegebener Algorithmus überhaupt in nützlicher Zeit ausgerechnet werden kann. Bei vielen Problemklassen stellt sich dabei heraus, dass dies nicht der Fall ist und wir uns – selbst mit sehr schnellen Computern – mit Näherungsverfahren oder einer ziemlich guten – anstatt der besten – Lösung behelfen müssen.
Aufgabe
Mit dem Interaktive Algorithm Timer kann man sich klar machen, wie schnell die benötigten Laufzeiten ggf. wachsen.
