Berichte 19/20

Zum dritten Mal in Folge stellt das HGG einen Endrunden-Teilnehmer beim Bundeswettbewerb Informatik

Auch in diesem Jahr stellt unsere Schule wieder einen Endrunden-Teilnehmer beim Bundeswettbewerb Informatik: Nachdem vor zwei Jahren unser Abiturient Johannes Häring teilgenommen hat und sich letztes Jahr Florian Pallas aus der jetzigen Klassenstufe 12 qualifizieren konnte, wird das HGG dieses Jahr durch Lukas Kesch aus der Klassenstufe 11 in der Endrunde vertreten, die Mitte September 2020 vom Fachbereich Informatik der Universität Erlangen-Nürnberg ausgerichtet wird. 

In der ersten Runde des diesjährigen Wettbewerbs im Herbst 2019 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 2.000 Schüler an der Einstiegsrunde und etwa 1.000 von ihnen wurden Anfang des Jahres zur zweiten Runde zugelassen.

Erstmals gab es dabei die Teilnahme eines HGG-Teams, denn Lukas und Florian hatten sich zusammen angemeldet und die Aufgaben im Team bearbeitet. Hier ging es zum Beispiel darum, das Tanken für eine 10.000 km lange Urlaubsfahrt längs einer Strecke mit 200 Tankstellen, die unterschiedliche Preise verlangten, so zu optimieren, dass man nicht unnötig häufig tanken musste, aber trotzdem insgesamt möglichst günstig tankte. Gemeinsam erreichten sie für die drei eingereichten Aufgaben jeweils die Maximalpunktzahl und wurden zur zweiten Runde zugelassen, bei der nun aber jeder einzeln die nächsten Aufgaben zu bearbeiten hatte.

Hier mussten bis zu den Osterferien 2020 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, Jahreszahlen durch Berechnungen mit nur einer Ziffer darzustellen, etwa 2020 = (6 - 6 / 6) * (6 + 6 * 66 + (6 + 6) / 6), und dabei mit möglichst wenig Ziffern auszukommen. Dabei musste man zuerst Rechenausdrücke samt den zugehörigen Regeln wie Punkt vor Strich oder Vorrang von Klammern rechnerintern korrekt darstellen und dann unter Milliarden von möglichen Ausdrücken effizient denjenigen herausfinden, der die gewünschte Jahreszahl mit möglichst wenig Ziffern darstellt.

Bei der zweiten Aufgabe sollte man in einer komplexen ebenen Straßenkarte zunächst den kürzesten Weg vom Start zum Ziel finden, was mit einem Algorithmus gelang, der auch in den Navigationsgeräten von Autos Verwendung findet, danach allerdings gegebenenfalls einen etwas längeren Weg in Kauf nehmen, wenn man längs diesem weniger oft abbiegen muss. Dieser alternative Weg sollte bezogen auf seine Anzahl von notwendigen Abbiegevorgängen aber wieder optimal, also möglichst kurz sein. Da es auch hier schnell zu Millionen von zu untersuchenden Wegen kam, war es wieder wichtig, einen effizienten Algorithmus zu finden, der unbrauchbare Wege möglichst schnell erkennt und verwirft.

Lukas und Florian stellten die Lösungsschritte und die gefundenen Lösungen der zweiten Aufgabe graphisch am Bildschirm dar, so dass sie während der Entwicklungsphase Programmierfehler schnell auffinden und beheben konnten und zum Schluss die Korrektheit der Lösung in der Zeichnung am Monitor überprüfen konnten.

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 23 besten Teilnehmer für die Endrunde qualifizierten. Lukas konnte nicht nur beide Aufgaben vollständig korrekt lösen, sondern erhielt auch noch Zusatzpunkte 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 Lukas fĂĽr die Endrunde qualifizierten, denn die Programme von Florian waren genauso korrekt und lieferten dieselben Ergebnisse mit derselben Laufzeit, Florian konnte aber durch die parallel laufende Vorbereitung auf die schriftliche AbiturprĂĽfung nicht ganz soviel Zeit in die Dokumentation investieren und hatte dann einige Punkte weniger, so dass er sich nur knapp nicht fĂĽr die Endrunde qualifizierte.

Das Finale wird dieses Jahr coronabedingt als Online-Wettbewerb ausgerichtet und nicht wie geplant vor Ort an der Universität Erlangen-Nürnberg. Wie dies genau ablaufen soll, muss allerdings noch geklärt werden. Eigentlich ist dies sehr schade, da der Endrunden-Wettbewerb auch immer viele Möglichkeiten bot, Kontakte mit anderen Informatik-Schülern und den prüfenden Professoren zu knüpfen. Hierzu bietet sich für Lukas ja dann vielleicht beim nächstjährigen Wettbewerb 2020/2021 im Herbst 2021 eine Gelegenheit.