HGG-Schüler erfolgreich beim Bundeswettbewerb Informatik

Auch in diesem Jahr waren unsere Schüler wieder erfolgreich beim Bundeswettbewerb Informatik: Niclas Gawor (Klasse 10), Fynn Luhr (Klasse 11) und Julian Gawor (Klasse 12) schnitten in der ersten Runde des Wettbewerbs, an der insgesamt rund 1.600 Schüler aus ganz Deutschland teilgenommen haben, so gut ab, dass sie sich alle drei auch für die zweite Runde qualifizieren konnten.

Im Herbst 2022 ging es in der ersten Runde des diesjährigen Wettbewerbs um fünf umfangreichere Programmieraufgaben, die auch einem sehr guten Schüler eines Informatik-Oberstufenkurses mit genügend Anstrengungsbereitschaft und Durchhaltevermögen durchaus einiges abverlangten.

Eine der Aufgaben behandelte die Symmetrie-Eigenschaften von Sudokus. Aus jedem Sudoku können durch die Vertauschung der vorkommenden Ziffern und durch geeignete Vertauschungen von Zeilen und Spalten über eine Billion anderer gleichwertiger Sodokus erzeugt werden, denen man die Verwandtschaft untereinander nur in den einfachsten Fällen direkt ansehen kann. Die Schüler sollten nun ein Programm erstellen, das für zwei vorgelegte Sodukos vollautomatisch entscheidet, ob sie nur Varianten voneinander sind oder ob sie echt verschieden sind.

Würde man dabei tatsächlich alle über eine Billion Varianten ausprobieren, würde das Programm viel zu lange für sein Ergebnis benötigen. Durch ein geschicktes Vorgehen, bei dem viele ungeeignete Varianten gar nicht erst betrachtet werden müssen, erhält man jedoch schon nach einem Bruchteil einer Sekunde das gewünschte Ergebnis.

Eine andere Aufgabe verlangte, die Auftragsbearbeitung für einen extrem überbeanspruchten Handwerksbetrieb zu optimieren: Wie können die durchschnittliche und die maximale Wartezeit der Kunden möglichst klein gehalten werden? Sollte man die eintreffenden Aufträge strikt in der Reihenfolge ihres Eintreffens abarbeiten oder sollte man kürzere Aufträge vorziehen und längere Aufträge zurückstellen?

Die Simulationen mit dem erstellten Programm zeigten, dass es am günstigsten ist, eine Mischstrategie anzuwenden, bei der sehr kurze Aufträge vorgezogen werden, aber alle anderen in der Reihenfolge des Eintreffens abgearbeitet werden.

In der zweiten Runde müssen nun bis zu den Osterferien 2023 Aufgaben bearbeitet werden, die weit über das schulische Niveau hinausführen. Hier gelingt es nur mit vielen Überlegungen und äußerst raffinierten Algorithmen, überhaupt eine Lösungsstrategie für die Probleme zu finden, die sich aber bei den vorgegebenen Eingabedaten meist noch um viele Größenordnungen als zu langsam in der Ausführung auf dem Rechner zeigen. Deshalb ist es anschließend erforderlich, in zahlreichen Testläufen den gefundenen Algorithmus immer weiter zu optimieren, bis er sehr gute Ergebnisse liefert.

Durch das erfolgreiche Abschneiden in der ersten Runde erhalten unsere Schüler auch die Möglichkeit, an interessanten mehrtägigen Informatik-Workshops teilzunehmen: Fynn besucht Ende Januar das Hasso-Plattner-Institut in Potsdam und zusammen mit Niclas nimmt er Anfang Februar am Jugendforum Informatik auf der Burg Liebenzell teil.