Bereits zum vierten Mal seit 2018 stellt unsere Schule einen Endrunden-Teilnehmer beim Bundeswettbewerb Informatik. In diesem Jahr werden wir durch Fynn Luhr aus der Klassenstufe 11 in der Endrunde vertreten sein, die Mitte September 2023 vom Fachbereich Informatik des KIT Karlsruhe ausgerichtet wird.
In der ersten Runde des diesjährigen Wettbewerbs im Herbst 2022 ging es um fünf kleinere Programmieraufgaben, die für einen guten Schüler eines Informatik-Oberstufenkurses mit genügend Anstrengungsbereitschaft und Durchhaltevermögen durchaus zu bewältigen waren. Deutschlandweit beteiligten sich rund 1.700 Schüler an der Einstiegsrunde und etwa 1.000 von ihnen wurden Anfang des Jahres zur zweiten Runde zugelassen, darunter auch Fynn sowie Niclas und Julian Gawor (Klassenstufe 10 bzw. 12).
In der zweiten Runde mussten nun bis zu den Osterferien 2023 zwei von drei Aufgaben bearbeitet werden, die weit über das schulische Niveau hinausführten. Es gelang nur mit vielen Überlegungen und äußerst raffinierten Algorithmen, überhaupt eine Lösungsstrategie für die Probleme zu finden, die sich dann bei einer Aufgabe aber noch um viele Größenordnungen als zu langsam in der Ausführung auf dem Rechner zeigte. Deshalb war es anschließend erforderlich, in zahlreichen Testläufen den gefundenen Algorithmus immer weiter zu optimieren, so dass er schließlich in sehr guter Zeit seine Ergebnisse lieferte.
In der ersten Aufgabe ging es darum, auf einer fiktiven Landkarte zahlreiche Orte mit einem Kleinflugzeug auf einem Rundflug in beliebiger Reihenfolge zu überfliegen, wobei die Gesamtflugstrecke möglichst klein werden soll. Dieses in der Informatik wohlbekannte, extrem schwierige und ausführlich untersuchte Problem (sog. Problem des Handlungsreisenden) wurde von den Aufgabenstellern nun so modifiziert, dass die vorhandenen Lösungs- und Näherungsverfahren nicht mehr verwendet werden können: An jedem Ort darf von der An- zur Abflugrichtung nur noch um maximal 90 Grad gedreht werden. Dadurch mussten die Teilnehmer völlig neuartige eigene Strategien und Verfahren entwickeln und eine möglichst gute und schnelle Lösungsidee zur Anwendung bringen.
Auch bei der zweiten Aufgabe wurde ein bekanntes Problem der Informatik (das Pfannkuchen-Sortierproblem, mit dem sich auch bereits Bill Gates beschäftigt hatte) so abgeändert, dass wieder eigenständige neue Lösungsstategien benötigt werden. Ein Stapel aus kreisrunden Pfannkuchen, die alle einen unterschiedlichen Durchmesser besitzen, soll so sortiert werden, dass der größte unten und der kleinste oben liegt. Dazu kann ein Pfannkuchen-Wender verwendet werden, den man zwischen zwei Pfannkuchen in den Stapel schiebt und mit ihm den oberen Teil des Stapels genau auf den Kopf stellt. Zusätzlich wird der Pfannkuchen, der sich nach dem Wenden oben befindet, gegessen. Für eine vorgegebene Höhe des Pfannkuchenstapels soll nun eine Pfannkuchen-Anordnung bestimmt werden, die unter allen möglichen Anordnungen am meisten Wendevorgänge (die jeweils optimal durchgeführt werden, um möglichst wenig Wendevorgänge zu benötigen) für das Sortieren erfordert.
Der Rechenaufwand für dieses sog. Min-Max-Problem wächst mit der Stapelhöhe astronomisch schnell an, da prinzipiell alle möglichen Stapelanordungen und alle möglichen Abfolgen von Wendeoperationen untersucht werden müssen. Versucht man durch den Einsatz von Arbeitsspeicher Rechenzeit zu sparen, indem Zwischenergebnisse abgespeichert werden, gerät man sehr schnell an die Arbeitsspeicher-Grenze eines typischen PCs. Folglich muss einerseits sehr effizient gerechnet werden, andererseits müssen genau die besonders häufig gebrauchten Zwischenergebnisse gespeichert werden.
In dieser zweiten Wettbewerbsrunde wurde auch eine ausführliche schriftliche Dokumentation verlangt, deren Umfang und inhaltliche Tiefe problemlos mit jeder Studienarbeit mithalten konnte. Diese extremen Hürden sorgten dafür, dass nur noch rund 200 Einsendungen für die zweite Runde eingingen, von denen sich dann nur die knapp 30 besten Teilnehmer für die Endrunde qualifizierten. Fynn konnte nicht nur beide Aufgaben vollständig korrekt lösen, sondern erhielt auch noch zahlreiche Zusatzpunkte (insgesamt 49 von eigentlich nur 40 Punkten) für seinen besonders klar strukturierten und gut lesbaren Programmcode und seine Dokumentation, die sehr ausführlich und fundiert auf die Laufzeiteigenschaften der beiden Programme einging.
Letztlich waren es diese Zusatzpunkte, die Fynn für die Endrunde qualifizierten, denn die Programme von Niclas und Julian waren genauso korrekt und lieferten ähnlich gute Ergebnisse, so dass beide einen hervorragenden zweiten Preis erhielten.
