Programmierwettbewerbe bei Infinite Search Space

Update August 2013/April 2014: So wie es aussieht, gibt es die Seite nicht mehr.

Vor einer Weile habe ich über die „Al Zimmermann’s Programming Contests“ geschrieben, bei denen jeder Interessierte möglichst gute Lösungen zu einer bestimmten Aufgabe eingeben konnte – es war im Prinzip völlig egal wie man auf die Lösungen kam, in der Praxis war es allerdings ohne Computer unmöglich, brauchbare Ergebnisse zu erzielen. Nachdem die Website dieses Wettbewerbs seit geraumer Zeit nur noch Fehlermeldungen liefert, bin ich neulich in einem Blog auf eine neue Website gestoßen, die einen Wettbewerb nach dem gleichen Muster durchführt: Infinite Search Space.

Prinzip

Ein Wettbewerb besteht aus einer Reihe von sehr ähnlichen Problemen (die sich zum Beispiel nur durch einen gegebenen ganzzahligen Wert unterscheiden). Für jede Teilaufgabe kann man eine Lösung eingeben (und auch jederzeit eine bessere nachreichen). Der Wettbewerb ist so konstruiert, dass sich die Lösung relativ einfach überprüfen und bewerten lässt. Für jede Teilaufgabe bekommt derjenige, der die beste Lösung gefunden hat, einen Punkt und diejenigen, die eine weniger gute Lösung haben, entsprechend Teilpunkte. Man kann jederzeit seinen eigenen Punktestand für die Teilaufgaben einsehen, außerdem wird noch die Gesamtpunktzahl ermittelt und danach ein Ranking aller Teilnehmer erstellt, das man ebenfalls einsehen kann.

Im Gegensatz zu den „Al Zimmermann’s Programming Contests“ gibt es bei diesem Wettbewerb (bisher) allerdings nicht viel zu gewinnen.

Der aktuelle Wettbewerb „Orchard Planting“

Zurzeit befasst sich der Wettbewerb mit einer Variante des „Orchard-planting problem“ (beschrieben unter anderem in der englischen Wikipedia) mit vier Bäumen pro Reihe: Es geht hierbei darum auf einer Ebene (Obstgarten, engl. „Orchard“) n Punkte (Bäume) so unterzubringen, dass es möglichst viele Geraden gibt, auf denen sich genau vier Bäume befinden, aber auf keiner Gerade mehr als vier Bäume liegen.

Auf der Website muss dabei für jedes der 50 Teilprobleme (das heißt für jede Anzahl Bäume n von 11 bis 60) eine Liste mit den (ganzzahligen) Koordinaten der Bäume im Garten abgegeben werden, und die Website ermittelt selbst, ob die Lösung gültig ist und wie viele Geraden mit vier Bäumen es darin gibt. Nach der Anzahl der Geraden mit vier Bäumen bemisst sich dann auch die Punktzahl für das Teilproblem: Wenn für das Teilproblem mit 11 Bäumen die maximal abgegebene Anzahl an Geraden mit vier Bäumen bei sechs liegt, bekommt man beispielsweise einen halben Punkt, wenn man wenn man eine Lösung mit drei Geraden auf denen vier Bäumen liegen eingegeben hat. Wenn man für alle Teilaufgaben die beste Lösung hat, kommt man demzufolge auf die Maximalpunktzahl von 50 Punkten (hat im Moment niemand).

Los geht’s!

Wer also Lust hat, in einer Programmiersprache seiner Wahl ein bisschen mit Teilnehmern aus aller Welt um die Wette zu programmieren oder schon seit längerem auf der Suche nach einer Alternative zum „Al Zimmermann’s Programming Contests“ ist, kann sich die offizielle Aufgabenstellung zum „Orchard Planting“-Wettbewerb (Update: Link entfernt, da Aufgabe nicht mehr online) anschauen und loslegen.

Formeln schön und effizient: Aufsätze und Referate mit LaTeX

Dieser Beitrag ist der erste aus der lange versprochenen Serie „Hilfsmittel für Mathe, Physik & Co“. Edit: Dort gibt es auch einen Beitrag über eine grafische Benutzeroberfläche für LaTeX.

Wer schon einmal viele Formeln in einem Textdokument verwenden wollte (oder vielleicht auch musste) hat wahrscheinlich die Erfahrung gemacht, dass die Formeleditoren von normalen Office-Programmen nicht besonders praktisch zu bedienen sind und das Ergebnis oft ausgesprochen mittelmäßig aussieht.

Eine gute Alternative zu diesen Office-Programmen ist LaTeX (Einer Erweiterung von TeX). In vielen wissenschaftlichen Bereichen, inbesondere in der Mathematik, ist LaTeX das Standardsystem zum Textsatz, sei es für Präsentationen, Hausaufgaben oder wissenschaftliche Publikationen. Eine Stärke dieses Systems ist die Erweiterbarkeit. So gibt es beispielsweise Module für Notensatz, chemische Formeln, pdf-Formulare, verschiedenste Stuktogramme, optimierte Darstellung von Quellcode und vieles mehr. Außerdem ist LaTeX dafür bekannt, dass es ohne viele Korrekturen des Nutzers Dokumente erstellt, die gut lesbar sind und alle wichtigen Regeln der Typografie einhalten.

Allerdings funktioniert LaTeX nicht nach dem WYSIWYG-Prinzip, das heißt der Nutzer schreibt zunächst von Hand LaTeX-Quellcode in eine Textdatei, die dann von LaTeX umgewandelt wird (oft in .pdf-Dateien, es sind aber auch viele andere Ausgabeformate wie zum Beispiel HTML-Seiten möglich). Das Lernen der LaTeX-Syntax kostet erst einmal etwas Zeit, wobei es im Internet viele gute Tutorials (oft auch auf den Seiten von Universitäten) gibt. Eine gute Einführung und Vorlagen für eigene Dokumente (Briefe, Diplomarbeiten …) gibt es unter anderem hier beim Mathematik-Online-Projekt der Universitäten Stuttgart und Ulm. Wenn man einmal eine Funktion nicht kennt, dann findet man über Google in der Regel sehr schnell Hilfe zu entsprechenden Funktionen. Eine gute Übersicht über wichtige Befehle für den Formelsatz gibt es auch in der Wikipedia, die selbst für die Darstellung größerer Formeln LaTeX verwendet. Und wenn man die Syntax einmal beherrscht gehen gerade Formeln sehr viel schneller, als wenn man sie in einem Formeleditor mühsam zusammen klicken muss.

Einen Überblick über verschiedene Verwendungsmöglichkeiten von LaTeX gibt es auch in der englischen Präsentation LaTeX: More Than Just Academic Papers and Theses.

LaTeX ist kostenlose Open-Source-Software und damit auch kostenlos für alle wichtigen Desktop-Betriebssysteme (und nicht nur für die) verfügbar. Für Windows empfiehlt sich beispielsweise MiKTeX, für Linux empfehle ich die Suche im jeweiligen Paketmanager oder bei der Suchmaschine des Vertrauens. Wer einfach nur ein bisschen mit den Mathe-Funktionen von LaTeX spielen möchte, findet im Internet auch diverse Seiten, auf denen man selbst LaTeX-Code eingeben kann, der dann als gerendertes Bild wieder ausgegeben wird – zum Beispiel hier.