Nachdem ich im letzten Beitrag zur Informatik-Olympiade beschrieben habe, was man überhaupt an der SOI macht, werde ich heute ein Beispiele für Aufgaben geben.

Die Aufgabe, die ich vorstellen werde, trägt den Namen „Two Tables“ und ist hier abrufbar.

In der Aufgabe geht es darum, dass eine grosse Festgemeinschaft auf zwei Tische verteilt werde muss, jedoch gewisse Personen sich nicht verstehen und daher nicht am selben Tisch sitzen wollen. Um das Beispiel aus der Aufgabenstellung zu verwenden: Richard mag Bob nicht und Steve mag Richard nicht. Also muss Richard am einen Tisch sitzen und Bob und Steve am zweiten Tisch. Gefragt ist nun die Anzahl Möglichkeiten, die Gäste auf die beiden Tische zu verteilen.

Aus diesem Beispiel sieht man bereits, dass diese drei Personen als eine betrachtet werden können, da wenn eine davon an einen Tisch platziert wird, ist für alle anderen klar, wo sie sitzen müssen. Was man auch leicht erkennt, ist die Tatsache, dass es für jede Person zwei Möglichkeiten gibt, sie zu platzieren, an den linken oder den rechten Tisch. Für die Lösung muss also die Anzahl solcher Gruppen bestimmt werden. Die Lösung ist anschliessend 2^Gruppenzahl.

Wie kann nun die Anzahl Gruppen bestimmt werden und weiter Gruppen erkannt werden, welche nicht platziert werden können (z.B. wenn im obigen Beispiel Bob und Steve sich nicht vertragen würden). Dies kann leicht mit einem bestehenden Algorithmus namens Breitensuche herausfinden. Dazu starten wir bei einer beliebigen Person und geben ihr die Nummer 1. Alle Personen, mit der sie sich nicht verträgt geben wir die Nummer 2 und besuchen diese der Reihe nach. So verfahren wir solange, bis eine Gruppe vollständig besucht ist. Wird während dem Durchgehen eine Person entdeckt, die bereits eine Nummer hat, überprüfen wir einfach, ob beide gerade bzw. ungerade sind oder ob die eine ungerade und die Andere geraden ist. Ist das Zweite der Fall, ist es kein Problem, da alle mit einer geraden Nummer am einen Tisch sitzen und die mit einer ungeraden Nummer am anderen. Ist das Erste der Fall haben wir eine Gruppe entdeckt, die nicht platziert werden kann und somit ist die Lösung der gesamten Aufgabe, dass es keine Möglichkeit gibt.

Um die Anzahl der Gruppen zu bestimmen, zählen wir, wie oft wir eine solche Suche starten müssen, um alle Personen zu besuchen.

Wie aus dieser Beispielaufgabe ersichtlich wird, geht es an der Informatik-Olympiade weniger ums Programmieren selbst, sondern vielmehr um logisches Überlegen und etwas Fantasie, um ein Problem etwas anders zu sehen und zu sehen, worauf es ankommt.

Was macht man an einem Informatikwettbewerb? Das werde ich oft gefragt. Wenn ich dann antworte, dass man programmieren müsse, denken viele, man reiche einfach ein Programm oder ein Spiel ein, das dann bewertet werde. Klar gibt es auch solche Wettbewerbe, doch die SOI gehört nicht dazu. Bei dieser geht es um das Programmieren von Algorithmen.

Nun, was ist ein Algorithmus? Ein Algorithmus ist nicht etwas, das ursprünglich aus der Informatik kommt – selbst die alten Griechen kannten Algorithmen. Ein Beispiel für ein solcher ist die Berechnung des ggT von Euklid. Ein Algorithmus ist eine Abfolge von Befehlen, um eine bestimmte Aufgabe zu lösen. Dieser kann man in Pseudocode (das ist wie eine Programmiersprache, jedoch kann diese nicht für echte Programme verwendet werden, da die genaue Begriffe nicht festgelegt sind. So kann man auf einfache Art und Weise einen Algorithmus – also eine Abfolge von Befehlen – aufschreiben) wie folgt beschreiben (Quelle: Wikipedia):

EUCLID(a,b)
1  wenn a = 0
2      dann return b
3  sonst solange b ≠ 0
4      wenn a > b
5          dann a a - b
6      sonst b b - a
7  return a

Die return-Anweisung bedeutet, dass die Funktion diesen Wert zurückgeben soll. Der Algorithmus ist somit beendet. Zu erklären, warum und wie dieser Algorithmus funktioniert, überlasse ich euch (Wikipedia weiss es auch).

Das Ziel an der SOI ist also, ein solcher Algorithmus für ein gegebenes Problem zu finden und umzusetzen. Im nächsten Teil der Serie werde ich dann die Aufgaben näher beschreiben.

Im Final der SOI gewann ich Gold, doch ich habe nur den 4. Platz belegt. Das führt oft zu Verwirrung, denn normalerweise bekommt nur der Erste Gold.

Im Final der SOI gilt jedoch eher „Medaillen für alle“, denn alle der zwölf Finalteilnehmer erhielten eine Medaille: Gold für die ersten vier, die an die IOI dürfen, Silber für die nächsten vier und Bronze für Platz neun bis zwölf. So haben alle Finalteilnehmer ein Andenken.

Dieses Jahr habe ich – wie letztes Jahr auch – an der Schweizerischen Informatik Olympiade (SOI) teilgenommen. Nachdem ich in der ersten Runde den 6. Rang und in der zweiten Runde den 5. Rang belegte, konnte ich im Final vom letzten Wochenende nochmals einen Platz vorrücken und landete auf dem 4. Platz. Damit kann ich zusammen mit den 1. bis 3. platzierten in der ersten Sommerferienwoche nach Australien an die Internationale Informatik Olympiade (IOI).

Da ich nun oft auf dies angesprochen werde, mache ich in diesem Blog eine kurze Serie über den Wettbewerb.