Bundeswettbewerb Informatik: Endrunde

Einleitung

Auf dieser Seite möchte ich in meinen eigenen Worten den typischen Ablauf einer Endrunde des Bundeswettbewerbs Informatik schildern. Ziel der Seite ist es, zukünftigen Endrundenteilnehmern ein ungefähres Bild vom Ablauf und von den Anforderungen zu vermitteln, die dort an die Teilnehmer gestellt werden. Das Wissen um den Ablauf der Endrunde ist nämlich meiner Meinung nach die halbe Miete und ein ungeheurer Vorteil bei der gezielten Vorbereitung. Ich selbst war bei der Endrunde des 15. Bundeswettbewerbs Informatik (15.-18. Oktober 1997) dabei und hatte das große Glück, als einer von 6 Bundessiegern ausgezeichnet zu werden und die Sonderpreise für die beste Einzelleistung und für die beste Gruppenleistung zu erhalten (letzterer Preis wurde für die gesamte Gruppe vergeben). Außerdem wirkte ich bei der Endrunde des 18. und 19. Bundeswettbewerbs Informatik (12.-15.9.2000 und 2.-5.10.2001) mit, wo ich aber nur kleine Hilfstätigkeiten durchführte. Natürlich kann die folgende Schilderung nur meine subjektive Sicht der Dinge darstellen. Einige wichtige Punkte werden im folgenden von mir vielleicht vernachlässigt, andere zu sehr betont. Darum freue ich mich auch immer über Kritik, Fragen und Anregungen, schreibt mir dazu einfach eine Mail.

Kurzer Überblick

Jedes Jahr qualifizieren sich je nach Zahl und Güte der Zweitrundeneinsendungen ungefähr 30 Zweitrundenteilnehmer des Bundeswettbewerbs Informatik für die Teilnahme an der Endrunde. Gesponsort wird die Endrunde normalerweise von großen Unternehmen, in den letzten Jahren (15. - 18. BWINF) von Lufthansa Systems, sd&m, der Deutschen Bank und der Stadt Nürnberg zusammen mit DATEV e.G.. Eine Endrunde dauert normalerweise 4 Tage, nämlich Anreise, zwei Wettkampftage und Siegerehrung / Abreise. An den beiden Wettkampftagen werden im Rahmen von je zwei halbstündigen Einzelgesprächen und zwei fünfstündigen Gruppenarbeiten die Teilnehmer beurteilt. Bei der Siegerehrung am Abreisetage werden ca. 6 Bundessieger und ca. 6 Preisträger gekürt und einige Sonderpreise (beste Einzelleistung, beste Gruppenleistung, bestes Mädchen (ggf. aus der 2. Runde), beste Leistung unter den jüngeren Teilnehmern, ...) vergeben. Die Bundessieger werden in der Regel auch in die Studienstiftung des deutschen Volkes aufgenommen, auch wenn dies offiziell kein Automatismus ist. Etwa 12 Teilnehmer der Endrunde und 3 von Jugend forscht qualifizieren sich außerdem für die Auswahlseminare zur internationalen Informatikolympiade. Aus diesen wird im Laufe von 3-4 Lehrgängen das vierköpfige deutsche Team gebildet, das zur CEOI und IOI reisen darf. Wichtig anzumerken ist wohl, dass es bei der Endrunde nicht um Programmieren geht. Tatsächlich gibt es bei der Endrunde normalerweise keinen einzigen Computer (bis auf einen für das Drucken der Urkunden), die fachliche und persönliche Qualifikation der Teilnehmer wird statt dessen anhand der Einzelgespräche und Gruppenarbeiten beurteilt.

nach oben

Einzelgespräch

An den Wettkampftagen führt morgens jeder Teilnehmer ein etwa halbstündiges Gespräch mit einem Informatik-Experten aus Schule, Hochschule, Wirtschaft oder Forschung. Dabei werden oft Fragen aus den unterschiedlichsten Gebieten der Informatik gestellt. Beispiele könnten z.B. sein: Computergrafik, Theoretische Informatik (Turingmaschinen, Berechenbarkeit, Churchsche These und Satz von Cook, Halteproblem, Busy Beaver, NP vs. P, ...), Sortieren & Suchen, Graphenalgorithmen (kürzester Pfad, alle kürzesten Pfade, maximaler Fluss, minimaler Spannbaum, Artikulationspunkte, ...), geometrische Algorithmen (closest pair, konvexe Hülle, ...), Datenkompression (Huffman, LZW, RLE, Quadtrees, ...). Sehr beliebt sind auch immer wieder Neuronale Netze und genetische Algorithmen. Vielleicht bekommt man auch den Quelltext eines kleinen Programms vorgelegt, dessen Funktionsweise und etwaige Fehler man herausfinden soll. Natürlich muss man sich nicht in jedem Gebiet hervorragend auskennen, wichtiger ist ein breiter Überblick.

Doch machen derartige Fragen nach expliziten Algorithmen und Beweisen nur gut die Hälfte aller Fragen aus. Oft werden auch Fragen gestellt, mit denen weniger die fachliche, sondern eher die persönliche Kompetenz angesprochen werden soll. So könnte man z.B. nach seiner Einstellung zu ethischen Fragen gefragt werden, z.B.: "Wenn der Kommandant eines Kriegsschiffes aufgrund fehlerhafter Angaben seines Computers ein vermeintliches feindliches Flugzeug (in Wirklichkeit eine Passagiermaschine) abschießt, inwieweit ist dann der Programmierer für die Katastrophe verantwortlich?". Oder: "Angenommen, man könnte das komplette Gehirn eines Menschen ohne Veränderung der Persönlichkeit in ein Computersystem transformieren, fänden Sie solch ein Vorgehen moralisch bedenklich, akzeptabel oder würden Sie es begrüßen?". Oder eine ganz andere Frage: "Was würden Sie Bill Gates fragen, wenn Sie ein Gespräch mit ihm führen könnten?". Auf all diese Fragen kann man sich eigentlich fast gar nicht vorbereiten, doch wer sich einigermaßen über das rein fachliche Wissen hinaus Gedanken macht, sollte bei ethischen Fragen seine eigene Meinung problemlos vertreten und fundiert begründen können. Es kann auch sein, dass einem ein ganz normales mathematisches oder logisches Problem gestellt wird, um zu sehen, wie man herangeht und welche Lösungsideen man hat. Hier ist dann eben einfach die Intuition, Kreativität und auch die Redesicherheit gefragt.

Die Teilnehmer müssen rechtzeitig vor der Endrunde auch einen Lebenslauf an den Bundeswettbewerb Informatik einschicken. Oft knüpft man zumindest beim Einstieg in das Einzelgespräch an einen im Lebenslauf erwähnten Punkt an oder fragt nach dem letzten größeren Programmierprojekt. Dies bietet den Teilnehmern auch die Chance, den Ablauf des Einzelgesprächs in gewissem Rahmen selbst zu steuern. Natürlich lassen sich die Professoren nicht die ganze Zeit auf die Lieblingsgebiete des Teilnehmers ein, aber oft kann man schon die Richtung, in die das Gespräch verläuft, stark beeinflussen. Auf jeden Fall sollte man die ganze Zeit in der Lage sein, flüssig zu reden und nicht etwa zu stocken, Pausen zu machen und das Ende des Einzelgesprächs herbeizusehnen :-)

nach oben

Gruppenarbeit

Anschliessend findet jeweils eine fünfstündige Gruppenarbeit statt, die vom Mittagessen unterbrochen wird. Dabei bearbeitet man in einer Gruppe von 4-5 Personen eine informatische Aufgabe und stellt anschließend die Ergebnisse in einem engen und streng einzuhaltenden Zeitrahmen (20 min pro Gruppe) im Plenum vor. Während der Gruppenarbeit wird die Gruppe von zwei Beisitzern beobachtet, die aber (wenn auch nicht gleichzeitig) zeitweise den Raum verlassen und bei anderen Gruppen vorbeischauen können. Die Zuhörer mischen sich aber natürlich (außer in wenigen Ausnahmefällen) nicht in die Diskussion ein und verhalten sich völlig passiv. Die Aufgabenstellungen sind ca. 2-4 Seiten lang und in zahlreiche Teilaufgaben gegliedert, die am Ende auch in dieser Reihenfolge beantwortet werden sollten.

Normalerweise ist die Aufgabe für den einen Wettkampftag relativ komplex und umfangreich, so dass für sie keine wirklich optimale Lösung existiert und oftmals die Aufgabenstellung gar nicht im mathematischen Sinne exakt formulierbar ist. Hier müssen die Teilnehmer dann recht abstrake Probleme lösen und häufig Heuristiken verwenden. Gerade bei diesem Typ von Aufgaben kann man auch mit besonderer Kreativität punkten und dadurch vielleicht den Sonderpreis für die kreativste Einzelidee bekommen. Beim 15. BWINF bestand die erste Aufgabe z.B. darin, einen möglichst guten Flugplan (d.h. angebotene Flüge und Verteilung der Flotte und des Personals auf dieselben) für die Lufthansa zu erstellen. Hierbei handelt es sich um ein extrem komplexes Optimierungsproblem mit zahlreichen Nebenbedingungen bzw. Beschränkungen (Zahl und Typ der verfügbaren Flugzeuge samt bauartbedingten Einschränkungen; Wartungspläne, Wünsche des Personals, Kompensationsmöglichkeit für Ausfälle und Verspätungen, ...). Man sollte sich Modellierungen für das Kundenverhalten (z.B. hat die Kundschaft, die in den Schulferien von Frankfurt nach Mallorca fliegen will, andere Ansprüche an den Reisepreis und an die Reisedauer als Personen, die am Werktag morgens oder abends per Linienflug Business Class von Berlin nach Stuttgart fliegen) und darauf und auf andere Kriterien aufbauend Bewertungsmöglichkeiten für Flugpläne überlegen. Ferner sollten Algorithmen skizziert werden, die entscheiden, ob ein Flugplan überhaupt möglich (also mit der verfügbaren Flotte und dem Personal fliegbar) ist usw.

Die zweite Aufgabe ist oft eher algorithmischer Natur oder stammt aus der theoretischen Informatik. Beim 15. BWINF z.B. war ein großes OR-Gatter mit n Eingangsdrähten gegeben, das am Ausgang genau dann eine 1 lieferte, wenn mindestestens ein Eingang auf 1 lag. Allerdings waren nur k der Eingangsdrähte überhaupt funktionstüchtig, bei den restlichen Drähten kam eine anliegende 1 nicht durch. Man sollte nun einen Algorithmus entwickeln, um bei bekanntem k und n mit möglichst wenigen Tests die defekten Drähte zu identifizieren. Natürlich war die Aufgabe noch etwas verklausuliert: in der Aufgabenstellung war die Rede von einer Menge von n Attributen, von denen k essentiell hießen. Man konnte nun jeweils anfragen, ob in einer bestimmten Teilmenge der Attribute mindestens c essentielle Attribute enthalten sind oder nicht und sollte mit möglichst wenigen Anfragen die essentiellen Attribute herausfinden. Am Anfang war c = 1, in späteren Teilaufgaben wurde dann c und natürlich auch n und k variiert oder eine Beziehung zwischen denselben angegeben (z.B. k << n oder k*k = n oder n = 2*k).

Selbstverständlich ist in der Gruppenarbeit wichtig, dass die Gruppe gute Ergebnisse erzielt und die Aufgaben sinnvoll bearbeitet und löst. Viel wichtiger aber ist die richtige Gruppendynamik und das richtige Maß an kooperativem Verhalten. Man sollte stets bemüht sein, die Gruppe zusammenzuhalten, die Ideen der anderen zu respektieren (aber auch durchaus auf Ideen beharren, wenn man überzeugt ist dass und vernünftig darlegen kann warum diese besser sind). Es schadet bestimmt nicht, in regelmäßigen Abständen zu rekapitulieren, was die Gruppe bisher erreicht hat, wie sie im Zeitplan liegt und welche Ziele in welcher Reihenfolge erreicht werden sollen. Sitzt ein Gruppenmitglied nur still und teilnahmslos dabei, so kann man denjenigen ruhig mal gezielt nach seiner Meinung fragen oder auch jemanden bremsen, der sich zu sehr in den Vordergrund drängen will. Wenn man sich sicher genug fühlt und den nötigen Überblick hat, kann man durchaus versuchen, die Gruppe ein wenig zu leiten und zu koordinieren, aber ohne sich besserwisserisch oder egozentrisch in den Vordergrund zu drängen und andere Gruppenmitglieder unterzubuttern. Wichtige erarbeitete Punkte und Ideen sollten unbedingt aufgeschrieben werden, damit man sie hinterher beim Erstellen der Folien noch in Erinnerung hat.

Nach Möglichkeit sollte man etwa 30-60 (eher 60) Minuten vor Ablauf der Gruppenarbeitszeit alle Aufgaben gelöst haben, damit man noch genügend Zeit für die Vorbereitung des Vortrags im Plenum hat. Die Teilaufgaben müssen dann so auf die Gruppenmitglieder verteilt werden, dass jeder ungefähr gleich lang spricht (4-5 Minuten, je nach Gruppengröße) und möglichst auch über ein Teilgebiet vorträgt, zu dessen Lösung er/sie besonders viel beigetragen hat. Am besten ist es, wenn die Folien früh genug fertig sind, dass man noch im Gruppenraum einen Probedurchgang des Vortrags abhalten kann, um Unstimmigkeiten zu entdecken und vor allem (ganz wichtig!!) den Zeitplan genauer einschätzen zu können. Auf jeden Fall sollte man den anderen Gruppenmitgliedern ihren Teil zubilligen und nicht versuchen, sich dadurch zu profilieren, dass man den ganzen Vortrag an sich reißt. Im Gegenteil, es macht einen extrem schlechten Eindruck beim Vortrag, wenn ein Vortragender seine Zeit überzieht. Denn das Gesamtzeitlimit von 20 Minuten für die Gruppe wird knallhart eingehalten (es werden dann auch jeweils Schilder mit den Aufschriften "noch 10 Minuten", "noch 5 Minuten", "noch 1 Minute", "Ende" hochgehalten), und durch eine Überziehung der Redezeit entzieht man den nachfolgenden Gruppenmitgliedern die Zeit für ihren eigenen Vortrag. Natürlich sollte man auch darauf achten, dass die Folien übersichtlich und lesbar sind, oft können kleine handgemalte Schaubilder, Symbole oder Diagramme das Verständnis wesentlich vereinfachen. Wie überall ist wichtig, die wesentlichen Fakten kurz, aber präzise und nachvollziehbar darzustellen.

nach oben

Vorbereitung

Wie bereitet man sich nun optimal auf die Endrunde vor? Sehr wichtig ist natürlich eine umfassende und breite Kenntnis der unterschiedlichsten Informatikgebiete. In meiner Buchtipps-Seite finden sich einige Vorschläge für Literatur, besonders ans Herz legen möchte ich Euch den Sedgewick und speziell als erste Endrundenvorbereitung Dewdneys Turing Omnibus, der einen schönen (wenn auch teilweise lücken- und fehlerbehafteten) Überblick über unterschiedliche Informatikgebiete gibt und einfach und ohne Hirnverrenkungen zu lesen ist. Ansonsten kann man sich schon ein paar Gedanken über das Verhalten bei den Einzelgesprächen und Gruppenarbeiten machen und in welche Richtung man das Einzelgespräch wohl lenken möchte, falls sich die Möglichkeit dazu ergibt. Auf viele Aspekte der Endrunde kann man sich aber nur schwer oder gar nicht vorbereiten, was vielleicht auch ganz gut ist. Vor allem aber ist die Endrunde nicht nur eine großangelegte, stressige Prüfungssituation, sondern man kann auch viele nette, interessante und kompetente Menschen kennenlernen. Darum gilt: have fun, don't panic ;-)

nach oben

Druckversion Druckversion
Last change: 2015-07-04 23:06:39 GMT+1000 Valid XHTML 1.1 best viewed with any browser