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.