Die erste Runde des 31. Bundeswettbewerb Informatik (kurz: BwInf) begann heute. Das bedeutet, bis zum 03.12.2012 haben Schler mal wieder die Chance zu zeigen, was sie in der Informatik drauf haben. Es gibt keine verpflichtende Anmeldung, nur die Einsendung. Wenn ihr diesen Beitrag also vor dem 03.12.2012 lest, knnt ihr noch teilnehmen.
Die offiziellen Informationen zum Wettbewerb, dessen Ablauf, die Teilnahmebedingungen und die Aufgaben gibt es auf bundeswettbewerb-informatik.de. Das Folgende ist inoffiziell; es sind meine persönlichen Erfahrungen.
Ich habe selbst ein paar mal am Bundeswettbewerb teilgenommen und bin bei meiner letzten Teilnahme Bundessieger geworden. Später habe ich Musterlösungen erstellt und an der Korrektur der Erstrunden- und Zweitrundenaufgaben teilgenommen. Ich weiß also wovon ich rede.
üö
Aufbau des Wettbewerbs
Der BwInf besteht aus drei Runden, in denen algorithmische Probleme gelöst werden müssen. Die ersten beiden Runden werden von zu Hause erledigt. Dafür habt ihr mehr als genug Zeit - jeweils über einen Monat. Die dritte Runde müsst ihr vor Ort bestehen. Diese läuft vollkommen anders ab, aber darüber will ich mal noch nichts berichten. (Falls ihr unbedingt einen Bericht wollt, hier ist der von Tobias).
Nur wer in der ersten Runde mindestens drei von fünf (+ 3 Junioraufgaben) Aufgaben weitgehend richtig gelöst hat, wird zur Zweiten zugelassen. Die Aufgaben der zweiten Runde sind prinzipiell ähnlich aufgebaut, jedoch deutlich schwerer zu lösen. Immer wieder sind \(\mathcal{NP}\)-vollständige Probleme dabei.
Warum sollte man teilnehmen?
Programmiert ihr gerne? Habt ihr Spaß daran, an Aufgaben zu knobeln? Denkt ihr darüber nach, wie man bereits gelöste Probleme noch effizienter lösen kann?
Dann ist der Bundeswettbewerb auf jeden Fall etwas für euch!
Selbst wenn ihr nicht alle Fragen überzeugt mit einem „Ja“ beantworten könnt, könnte der Bundeswettbewerb euch gefallen. Probier es einfach mal aus.
Einen weiteren Anreitz bieten Preise: Die Bundessieger werden soweit ich weiß immer in die Studienstiftung aufgenommen und es gibt Geldpreise.
Und noch ein Schlusswort zur Motivation: Eine gute Dokumentation zu schreiben ist anstrengend. Ich hatte häufig bei der Dokumentation keine Lust mehr, sie noch ein weiteres mal anzusehen. Sie nochmals zu verbessern. Aber die Arbeit lohnt sich. Wenn ihr sie fertig geschrieben habt, könnt ihr stolz darauf sein. Wie ein Sprichwort so schön sagt: „Ohne Fleiß kein Preis.“
Tipps zur Aufgabenbearbeitung
Zur Lösungsfindung
Wenn ihr ein Skript habt, dass eventuell nicht sofort, aber nach ein paar Stunden die Lösung ausgeben sollte, dann vergesst nicht, auch eine Ausgabe mit Zwischenergebnissen dafür einzubauen! Kaum etwas ist ärgerlicher, als ein Programm, das lange läuft und am Ende keine Ausgabe macht oder sich aufhängt.
Doku ist wichtig
Bei der Korrektur wird zuerst die Dokumentation angesehen. Natürlich ist die Lösungsidee wichtig, aber eine negativ bewertete Dokumentation ist ärgerlich. Also lest euch bitte die Dokumentation nochmals durch und überprüft, ob die wichtigen Lösungsideen verständlich erklärt wurden.
Ich denke das ist wohl der einzige Aspekt, wo euch andere helfen können. Gerade Leute ohne Programmierkenntnis sollten eure Lösungsidee verstehen können. Mein Vater (der nicht programmieren kann) hat häufig meine Einseundungen nochmals auf Rechtschreib- und Grammatikfehler sowie auf fehlende Zusammenhänge überprüft. Er konnte zwar nicht sagen, was dort nicht stimmt, hat aber häufig ... naja, sagen wir mal Stellen gefunden, bei denen meine Deutschlehrer wohl Zahnschmerzen hätten (trifft wohl auch auf diesen Blog zu 😉)
Also: Schreibt die Doku früh. Ich habe sie geschrieben, während ich programmiert habe. Dann setzt irgendwann eine Version auf, von der ihr denkt, dass sie fertig ist. Wartet so ein, zwei Tage und lest sie euch nochmals durch (es ist wirklich erstaunlich, was man dann sieht). Dann sucht euch jemanden, der die Aufgabenstellung nicht kennt und nicht programmieren kann. Der Korrekturleser sollte das Deutsche natürlich gut beherrschen. So ein Korrekturleser streicht nur mangelhafte Stellen in eurer endgültigen Version an, macht aber keine Verbesserungsvorschläge. Die müsst ihr euch selbst überlegen. Und dann ist man wirklich froh, wenn man das blöde Ding los ist.
Eine Randbemerkung dazu noch: Ich habe mal einen kurzen Job als Programmierer für ein größeres Projekt übernommen. Dabei gab es über 2GB, die größtenteils C++-Code und ein paar Testdaten waren (rechnet es aus, das ist VERDAMMT viel Code!). Die hatten keine Dokumentation! Ich habe bestimmt eine Woche nur damit verbracht, mich mehr oder weniger wahllos durch wirre Quelltexte zu klicken, weil ich noch nicht einmal wusse, wo ich genau anfangen soll. Ich glaube den Zweck einer Dokumentation versteht man erst nach einem solchem Erlebnis.
Beispiele
Die Beispiele werden leider hin und wieder vergessen und sind oft nicht aussagekräftig. Überlegt euch: Welche Eingaben sind Standard-Fälle? Welche Eingaben sind Sonderfälle? Diese sollten unbedingt als Beispiele gezeigt werden, da es oft nicht klar ist, ob jemand in einer Einsendung daran gedacht hat. Mit Sonderfällen sind nicht falsche Eingaben gemeint - das ist für den Bundeswettbewerb unwichtig - sondern korrekt formatierte Eingaben, die etwas ungewöhnliches / schweres aufweisen.
Die Beispiele sollen euch helfen, Probleme zu entdecken. Eventuell funktioniert eure Implementierung nicht so, wie ihr es euch vorstellt. Das könnt ihr damit feststellen. In diesem Zusammenhang solltet ihr euch das Konzept der testgetriebenen Entwicklung ansehen. Dabei schreibt man zuerst alle wichtigen Testfälle, bevor man überhaupt eine Zeile produktiven Codes schreibt. Beispielsweise für die Aufgabe „Verben“ würde ich heute so eine Herangehensweise wählen.
Ach ja: Es kann sein, dass ihr ein Problem feststellt, dieses aber nicht beheben könnt. Dann solltet ihr es beschreiben. Es wird sowieso entdeckt. Man kann eurer Lösungsidee erkennen, welche schwächen die Implementierung hat.
Versionskontrolle
Ich habe leider erst nach dem Bundeswettbewerb meine ersten Erfahrungen mit Versionskontrollsystemen gesammelt. Immer wenn ich eine Idee hatte, wie man das Problem anders angehen könnte, habe ich eine Kopie der aktuellen Version erstellt und auf der Kopie weiter gearbeitet. Diese Lösung ist jedoch in vielerlei Hinsicht einem Versionskontrollsystem - SVN und Git sind die bekanntesten - unterlegen. Man kann nicht so leicht eine Sicherung durchführen. Es ist unübersichtlich, die wiederherstellung bei vielen Dateien ist schwer und man kann sich nicht so leicht die Unterschiede von verschiedenen Versionen anzeigen lassen. Zum vergleich: Hier kann man sich den Unterschied zweier Versionen auf code.google.com ansehen. Mit meld bekommt man ähnlich gute Ergebnisse auch auf dem eigenem Rechner.
LaTeX
LaTeX ist toll - aber keine Pflicht. Es werden leider relativ wenige Dokumentationen mit LaTeX erstellt. Dabei bietet LaTeX für den BwInf ein paar Vorteile:
- Das Ergebnis kann sich sehen lassen, LaTeX sieht einfach schön aus.
- Man kann die Doku in die Versionskontrolle stecken.
- Man kann Quelltext automatisch einbinden lassen (siehe dazu ein Blogpost von mir).
- Und so bekommt man LaTeX: How to install the latest LaTeX Version.
Außerdem ist die Kombination LaTeX+Versionskontrolle toll ☺
Die CD
Ich weiß leider nicht, warum keine Online-Abgabe möglich ist. Vielleicht, weil es einfacher ist. Eventuell aus Sicherheitsgründen. Wenn man Papier und eine CD in der Hand hat, kann es nicht passieren, dass eine Runde im schlimmsten Szenario komplett ausfallen muss, weil der Server abgeraucht ist. Egal wie, ihr müsst die CD erstellen. Dazu hätte ich - aus Sicht eines Korrektors - ein paar Bitten:
Die CD hat über 600 MB. Das ist deutlich mehr, als ihr braucht. Also schreibt doch bitte auch die Beispiele des BwInf darauf, sowie eine PDF-Datei eurer Doku. Das erleichtert die Korrektur ungemein, da man so die Doku durchsuchen kann. Überprüft, ob die CD auch wirklich gebrannt wurde, abgeschlossen wurde und sie lesbar ist. Wenn eure Dokumentation schlecht ist und die CD nicht lesbar ist, kann eventuell eine gute Lösungsidee schlecht bewertet werden.
edit: Hier habe ich eine Rückmeldung von Herrn Dr. Pohl erhalten. Es geht nicht um CD vs. Online-Abgabe sondern um CD und „gedruckte Dokumentation und CD“ vs. „Online-Abgabe“. Die Korrektur von Lösungsideen auf einem Blatt Papier ist immer noch die einfachste und für den Leser die angenehmste. Ich schreibe als Korrektor häufig Anmerkungen in eure Dokumentation, damit der Zweitkorrektor leichter nachvollziehen kann, was ich mangelhaft oder auch sehr gut gefunden habe. Außerdem schreibe ich manchmal rein, was der Einsender gemeint hat (falls die Doku nicht so toll war und es nicht direkt ersichtlich ist). Außerdem ist es mit CDs einfacher, die Infrastruktur für die Korrektur aufzubauen. An den Bewertungswochenenden werden so ca. 30 frisch aufgesetzte, unvernetzte PCs benutzt (es lohnt sich also nicht, Viren zu schreiben). Bei einer Online-Abgabe müssten diese PCs Internet haben, was leider nicht immer zur Verfügung steht. Oder sie müssten lokal, z.B. auf einem NAS, sein. Das ist alles etwas umständlicher als einfach eine CD zu brennen. Ihr dürft übrigens auch SD-Karten einschicken ☺
Vielen Dank an Herrn Dr. Pohl für die Hinweise!
Die Programmiersprache
Also eine Brainfuck-Einsendung muss jetzt nicht gerade sein (obwohl ich wirklich beeindruckt wäre). Aber eine Shakespeare-Einsendung würde ich mal toll finden ☺ Nein, im ernst: Ihr dürft fast alles benutzen. Ich selbst kann Python, PHP, Java, C++ und C gut genug um jede Einsendung verstehen zu können. Ich weiß, dass wir immer Leute haben die Haskel/Objective CAML und vielleicht noch ein paar weitere funktionale Sprachen können. Auch Pascal, Delphi (Object Pascal), BASIC stellen kein Problem dar. Das ist jetzt keine vollständige Liste; unter den Korrektoren gibt es einige, die auch exotische Sprachen können. Aber wenn euch klar ist, dass eure Sprache exotisch ist, dann solltet ihr besondere Sprachfeatures kommentieren.
Ich habe damals meine Einsendung in PHP geschrieben, später in Python. Warum PHP? Naja, es gibt ein super Tutorial für PHP.
Welche Programmiersprache würde ich heute nehmen? Nun, es gibt keine Programmiersprache die für jeden Zweck gut ist. Für kleine Probleme - und Bundeswettbewerbsaufgaben sind zwar schwer, aber doch recht übersichtlich - eignet sich häufig Python gut. Falls es in der zweiten Runde auf Geschwindigkeit ankommt, ist wohl C++ eine Sprache der Wahl. Für später empfiehlt es sich, Java zu lernen. Aber ihr müsst keine dieser Sprachen nehmen. Das ist ja das tolle am BwInf. Es steht euch frei, das zu wählen, was für euch das beste ist.
Quelltext-Kommentare
Trotz Doku sind Quelltextkommentare erwünscht. Allerdings müssen Standard-Strukturen (if/else,for,while, Variablendeklarationen) nicht kommentiert werden! Übertreibt es nicht, aber verwendet Kommentare, wenn einem Außenstehendem nicht direkt klar sein kann, was ihr macht. Java-Programmierer sollten definitiv die standard Sun Checkstyle und JavaDoc verwenden, Python-Programmierer sollten DocStrings kennen und verwenden. Für alle anderen Sprachen muss man halt ein Gefühl entwickeln. Wer in C wild mit Pointern um sich wirft sollte tendenziell wohl mehr Kommentare machen als jemand, der Pythons Standardbefehle nutzt.
Style-Guides
Es ist nicht zwingend erforderlich, dass ihr euch an sogenannte Styel-Guides haltet. Allerdings ist es bei der Bewertung - und insbesondere später, wenn ihr an echten Projekten mit anderen zusammen arbeitet - sehr hilfreich, wenn ihr euch an Konventionen haltet. Hier sind ein paar:
Was sollte man lernen?
Falls ihr Informatik studieren wollt oder später programmieren wollt, sind SVN und GIT unverzichtbar. Außerdem werdet ihr wohl mit Java und C++ in Kontakt kommen. Am KIT wird euch beigebracht, wie ihr mit Eclipse und checkstyle umgeht. Aber es wird auch erwartet, dass ihr es nutzt. Ich vermute, dass für viele wissenschaftliche Veröffentlichungen im Natur- und Ingenieurswissenschaftlichen Bereich LaTeX kaum wegzudenken ist. (Ach ja: Ihr könnt auch Briefe mit LaTeX schreiben und komplexe Grafiken mit LaTeX erstellen!)
Website-Empfehlungen
Das meiste, was ihr wissen müsst, könnt ihr über Wikipedia lernen. Ich habe mich z.B. mal durch die Kategorie:Algorithmus geklickt. Das ist nicht sonderlich zielführend und sicher nicht jedermanns Sache, aber so habe ich mir einiges beigebracht. Ob es mir viel genutzt hat, kann ich nur schwer beurteilen.
Wenn ihr Interessantes rund um die praktische Informatik in kleinen Portionen lernen wollt, ist der Newsletter von StackOverflow.com empfehlenswert. Der ist zwar auf englisch, aber ich glaube das Englisch ist einfach genug. Außerdem werdet ihr im Informatik-Bereich häufig auf englische Literatur, Websites, Manuals oder Spezifikationen treffen. Man muss sich vielleicht mal daran gewöhnen, mit leo einiges Übersetzen, aber das gibt sich schnell.
Es gibt übrigens von einigen Universitäten Online-Vorlesungen. Ich habe mir damals eine Vorlesung vom MIT komplett angesehen (das waren damals zwei Dozenten, von denen einer Prof. John Guttag war). Dieses Semester habe ich vom Stanford Algorithms: Design and Analysis durchgearbeitet. Die stellen sogar eine PDF-Urkunde mit deinen Ergebnissen aus. Udacity bietet in der Hinsicht auch interessante Kurse.
Wenn ihr generell am Knobeln Spaß habt, kann ich sogenannte „Challenge Websites“ empfehlen. Die Probleme sind (größtenteils) schneller zu lösen als beim Bundeswettbewerb und man muss keine Doku schreiben.
Buchempfehlungen
Für die zweite Runde kann ich „Computers and Intractability: A Guide to the Theory of NP-Completeness“ (Link) empfehlen. Es wird in der zweiten Runde häufig (immer?) erwartet, dass man auf die Komplexität des Problems bzw. das Laufzeitverhalten der eigenen Lösung eingeht. Wenn man das besonders gut macht, gibt es hin und wieder Bonuspunkte. Wenn ihr dieses Buch - das ganz eindeutig dem Bereich der Theoretischen Informatik zuzuordnen ist und für einen Schüler bestimmt keine leichte Lektüre ist - versteht und das Wissen übertragen könnt, dann könntet ihr hier Boni erhalten. Aber wie gesagt, das zu verstehen und auf ein konkretes Problem zu übertragen ist nicht leicht.
Deutlich einfacher ist „Theoretische Informatik - kurz gefasst“. Das Buch gibt eine grundlegende Einleitung und ist auf deutsch.
Und, nur um es nochmals zu betonen: Das sind persönliche Erfahrungen und teilweise Bitten von jemanden, der es korrigiert. Wenn Teilnehmer meine Tipps nicht beachten, gibt es keinen Punktabzug und es gibt auch keine Bonuspunkte, wenn ihr sie beachtet. Aber ihr erleichtert ein paar Leuten die Korrektur, ihr lernt dabei eventuell was neues (LaTeX und GIT/SVN werdet ihr im Informatik-Studium noch benötigen) und vielleicht fallen euch Fehler oder Mängel in eurer Lösung auf.
Falls ihr Fragen habt kann ich die auch gerne beantworten. Auf Ikhaya habe ich bereits ein paar beantwortet.