Der Bundeswettbewerb Informatik ist der traditionsreichste deutsche Schülerwettbewerb in diesem Fach. Dieses Jahr nahmen bundesweit etwa 1400 Schüler/innen daran teil. Unser Schüler Adrian Dobbelstein (Jg. 10) gehört mit einem ersten Preis in der zweiten Runde des Bundewettbewerbs Informatik zu den dreißig Finalisten, welche im September am Hasso-Plattner-Institut (Potsdam) an der dritten Runde, einem Kolloquium, teilnehmen dürfen. Darin führt jeder Teilnehmende ein Gespräch mit je einem Informatiker aus Schule und Hochschule und analysiert und bearbeitet im Team zwei Informatik-Probleme. Dort winkt dann der Bundessieg, der mit der Aufnahme in die Studienstiftung des deutschen Volkes verbunden ist. Die jüngeren Finalisten können am Verfahren zur Auswahl des deutschen Teams für die Internationale Informatik-Olympiade (IOI) teilnehmen und haben damit die Chance, sich bei der IOI 2018 in Tokio/Japan mit Spitzentalenten aus der ganzen Welt zu messen.
Um einen Eindruck zu gewinnen, welche Aufgaben von Adrian in der zweiten Runde gelöst werden mussten, sei hier eine Aufgabe vorgestellt:
Rechtsrum in Rechthausen
Eine Statistik der Polizei von Rechthausen hat gezeigt, dass eine Vielzahl von Autounfällen durch inkorrektes Linksabbiegen verursacht wird. Der Bürgermeister von Rechthausen hat deshalb beschlossen, das Linksabbiegen per Dekret zu untersagen. Autofahrer sollen in Rechthausen nur noch geradeaus fahren oder rechts abbiegen dürfen. Diese Entscheidung führt zu viel Unmut der Bewohner von Rechthausen. Sie befürchten, sich dann in der Stadt nicht mehr zurechtzufinden. Du möchtest Abhilfe schaffen und ein Navigationssystem erstellen, das nur Routen vorschlägt, bei denen nicht links abgebogen werden muss. Dein System erhält als Eingabe ein Straßenverzeichnis. Dieses besteht aus einer Menge V von Kreuzungen mit ihren jeweiligen Koordinaten sowie der Menge E von denjenigen Paaren von Kreuzungen, die direkt durch Straßenabschnitte verbunden sind. Da Rechthausen eine moderne Stadt ist, haben die Straßen keinerlei Kurven. Das Straßennetz von Rechthausen könnte zum Beispiel so aussehen (alles, was in Rechthausen als Kreuzung angesehen wird, ist durch einen Buchstaben gekennzeichnet):
Die Aufgabe bestand darin, nach einer geeigneten Definition des Linksabbiegens einen kürzesten Weg zwischen zwei beliebigen Kreuzungen zu finden. Man musste also eine Art Navigationssystem entwerfen.
(Quelle: http://www.bundeswettbewerb-informatik.de/aktuell/2-runde/)
