Berichte 18/19

HGG-Schüler bei der Endrunde des Bundeswettbewerbs Informatik

Auch in diesem Jahr stellt unsere Schule wieder einen Endrunden-Teilnehmer beim Bundeswettbewerb Informatik: Nachdem im letzten Jahr unser Abiturient Johannes Häring teilgenommen hat, werden wir dieses Jahr durch Florian Pallas aus der Klassenstufe 11 in der Endrunde vertreten, die Anfang Oktober eine Woche lang bei SAP in Walldorf stattfinden wird.

In der ersten Runde des diesjährigen Wettbewerbs im Herbst 2018 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.

In dieser mussten bis zu den Osterferien 2019 zwei von drei Aufgaben bearbeitet werden, die weit über das schulische Niveau hinausführten. Viele der erforderlichen mathematischen Techniken (wie Determinanten, Matrizen und ihre Inversen sowie Winkelberechnungen und ebene Abbildungen im Vektorkalkül) werden im schulischen Mathematikunterricht gar nicht oder nur im Vertiefungskurs in Klassenstufe 12 behandelt. Florian musste sich hier einarbeiten und erstellte für die Programmierung auch gleich eigene Bibliotheksfunktionen für alle anfallenden mathematischen Berechnungen. Weiter gelang es nur mit vielen Überlegungen und äußerst raffinierten Algorithmen, überhaupt eine Lösungsstrategie für die Probleme zu finden, die sich aber bei einer Aufgabe für die vorgegebenen Eingabedaten 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 ganz zu verwerfen und durch ein geeigneteres Näherungsverfahren zu ersetzen, das schnell abläuft und trotzdem sehr gute Ergebnisse liefert.

In der ersten Aufgabe ging es darum, den schnellsten Weg durch eine komplexe ebene Hindernislandschaft bis zu einer Straße zu finden, wo man von einem vorbeifahrenden Bus mitgenommen wird. Nachdem alle prinzipiell möglichen Wege durch trickreiche Schnittberechnungen mit Geraden und Strecken zusammengestellt waren, verwendete Florian einen Algorithmus, wie er auch in den Navigationsgeräten von Autos Verwendung findet, um den schnellsten unter ihnen zu bestimmen. Bei der zweiten Aufgabe sollten vorgegebene Dreiecke längs einer Geraden möglichst platzsparend ohne Überlappungen aufgereiht werden, wobei beliebige Verschiebungen, Drehungen und Spiegelungen zugelassen waren. Jede Möglichkeit für die Abfolge der Dreiecke auszuprobieren und dann die beste davon auszuwählen, war mit zehn Dreiecken noch problemlos möglich, aber bei zwanzig und mehr Dreiecken vom Rechenaufwand her völlig aussichtslos. Deshalb bildete Florian trickreich zuerst mehrere fächerförmige Gruppen von Dreiecken und schob dann die einzelnen Fächer so weit zusammen, dass sie sich gerade berührten. Dieses Verfahren garantiert zwar nicht, die absolut beste Lösung zu finden, stellt jedoch bei geschickter Zusammenstellung und Abfolge der Teilgruppen in kürzester Zeit eine Lösung bereit, die nur wenig schlechter als die bestmögliche ist.

Die Lösungsschritte und die gefundene Lösung von beiden Aufgaben stellte Florian mit seinen Programmen graphisch am Bildschirm dar, so dass er während der Entwicklungsphase Programmierfehler schnell auffinden und beheben konnte und zum Schluss die Korrektheit der Lösung in der Zeichnung am Monitor überprüfen konnte.

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 die 30 besten Teilnehmer für die Endrunde qualifizierten. Florian 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.

Das Finale wird dieses Jahr von der Firma SAP ausgerichtet, die die Endrundenteilnehmer und ihre betreuenden Lehrer für eine Woche nach Walldorf einlädt. Die Finalisten werden in drei halbstündigen Einzelgesprächen von Informatik-Professoren bewusst zu Themen befragt, in denen sie sich nicht hervorragend auskennen, und bearbeiteten außerdem wie in einem Assessment-Center unter Zeitdruck zwei Informatik-Probleme im Team. Florian hat schon Kontakt mit Johannes aufgenommen, um aus erster Hand Informationen zum genauen Ablauf und zur sinnvollen Vorbereitung für die Endrunde zu erhalten. In den Sommerferien wird er sich bestimmt auch noch das eine oder andere Informatikbuch durchlesen.