Archive for the 'Informatik' Category

Bundeswettbewerb Informatik 2010/2011 gestartet

Heute startet die 1. Runde des 29. Bundeswettbewerbs Informatik (BWINF). Um einen kleinen Überblick über die Teilnahme und die Gewinnmöglichkeiten zu geben habe ich hier die wesentlichen Infos zusammen getragen:

Ablauf und Preise

Der Bundeswettbewerb Informatik läuft jedes Jahr über drei Runden, in denen man sich jeweils für die nächste Runde qualifizieren kann. Die ersten beiden Runden werden zu Hause gelöst. Hier gibt es schon Buchpreise und diverse Sonderpreise zu gewinnen.

Alle, die sich für die dritte Runde qualifiziert haben, werden dann eingeladen. In dieser Runde werden dann die Bundessieger ermittelt, denen unter anderem die Aufnahme ins Stipendienprogramm der Studienstiftung des deutschen Volkes und Geldpreise winken.

Teilnahme am Bundeswettbewerb Informatik

Bis Mitte November kann jeder die Aufgaben bearbeiten und seine Lösungen nach der Online-Anmeldung einschicken (weitere Infos gibt auf der verlinkten Anmeldeseite). Wer in der ersten Runde Erfolg hat, wird normalerweise über die weiteren Möglichkeit informiert.

Die Aufgaben der 1. Runde des 29. BWINF

Die Aufgaben und Zusatzmaterialien finden sich wie immer auf der entsprechenden Seite des Bundeswettbewerbs. Dort gibt es auch die Aufgaben als .pdf-Datei (Im Gegensatz zur recht drögen Darstellung des Bundeswettbewerbs Mathematik ist die Aufmachung des BWINF so verspielt und bunt, dass weder die Bildschirmdarstellung noch ein Schwarzweißausdruck wirklich praktisch sind. Es soll aber noch eine übersichtlichere Fassung folgen.). Zu jeder der Aufgaben wird neben dem Programm selbst (Quellcode und lauffähige Variante) auch eine Dokumentation von Idee und Programmaufbau verlangt.

Die Aufgabe 1 (die Aufgabenbeschreibung beginnt schon ganz oben in der mittleren Spalte auf Seite 4, auch wenn die Überschrift (mutwillig!) mittendrin steht ;-) ) ist dieses Jahr eine Kreativaufgabe, die in einer exotischen Spezialsprache für künstlerische Grafiken zu bearbeiten ist. Nachdem man sich hier ein bisschen eingearbeitet hat, sollte diese Aufgabe problemlos zu lösen sein.

Bei der Aufgabe 2 geht es darum, eine Simulation entsprechend der vorgegebenen Regeln zu entwickeln. Neben der Logik mit Kollisionserkennung dürfte vor allem die Steuerung der Parameter und die saubere Darstellung je nach Programmiersprache mit etwas Aufwand verbunden sein. Hier ist sicherlich Erfahrung in der Programmierung von grafischen Benutzeroberflächen hilfreich.

Aufgabe 3 erfordert im Wesentlichen das Einlesen von Daten, die dann entsprechend ausgewertet werden müssen. Beispieldaten gibt es laut BWINF ab Mitte September, der Link zu den Daten in der .pdf-Datei enthält bisher auch nur die erste Zeile der umgebrochen dargestellten URL.

Für die Aufgabe 4 dürfte ein bisschen Mathematik zur Lösungsfindung nötig sein, die man dann in einen perfekten Spieler eines einfachen Kartenspiels umsetzten muss. Nachdem das Spiel aber nur vom Würfel und einem einzigen Spieler abhängt (wenn ich es richtig verstanden habe), sollte auch diese Aufgabe machbar sein.

Die letzte Aufgabe (Aufgabe 5) ist wie die dritte Aufgabe eine Logistikaufgabe, die allerdings vermutlich etwas mehr Vorüberlegungen (und ein paar Skizzen oder ein gutes Vorstellungsvermögen) erfordert.

Insgesamt sind die Aufgaben damit wieder recht abwechlungsreich. Wer tatsächlich am 29. BWINF teilnehmen möchte sollte bald anfangen, damit er auch wirklich Zeit hat, bis Mitte November nicht nur saubere Programme sondern auch eine entsprechende Dokumentation zu schreiben.

Und damit es nicht wieder so geht, wie beim BWM: Von mir gibt es keine weiteren Hinweise, unter anderem aus den gleichen Gründen wie dort.

Viel Erfolg an alle (ehrlichen) Teilnehmer des 29. Bundeswettbewerbs Informatik!

Apfelmännchen im Browser

Darstellung der Mandelbrotmenge

Mandelbrotmenge

Nachdem ich vor kurzem ein sehr primitives Java-Applet mit Erklärung (Quellcode hier) geschrieben habe, mit dem sich das „Apfelmännchen“ (das heißt die Mandelbrotmenge) darstellen lässt, habe ich hier noch ein wesentlich komfortableres und funktionsreicheres Applet geschrieben, mit dem sich die Mandelbrotmenge untersuchen lässt. (Die ganzen Bilder der Mandelbrot-Menge hier im Blog sind auch damit berechnet.)

Continue reading ‘Apfelmännchen im Browser’

Mandelbrotmenge einfach selbst programmiert

Darstellungen der Mandelbrotmenge (auch „Apfelmännchen“ genannt) sind mit das Schönste was die Mathematik zu bieten hat. Nachdem ich vor kurzem schon die mathematischen Grundlagen (.pdf-Datei) erklärt habe, will ich mich hier der Programmierung eines einfachen Java-Applets zur Anzeige des „Apfelmännchens“ widmen. Sowohl den vollständigen Programmcode als auch das eingebettete Applet finden Sie unten.

Wer weniger an der Technik als vielmehr am Herumspielen mit der Mandelbrotmenge interessiert ist, dem kann ich mein aufwändigeres Applet u.a. mit Zoomfunktion empfehlen.

An Mathematik brauchen wir nur die beiden Formeln (1) und (2) aus der Erklärung, die wir wie in der .pdf Datei unter „Wie kann ich das programmieren“ beschrieben berechnen. Hier sind die hier wesentlichen Abschnitte noch einmal als Auszug:

Die Formeln:

xn+1 = xn2 – y n2 + a
yn+1 = 2xnyn + b

Dies lässt sich nun ohne Kenntnis von komplexen Zahlen berechnen, wenn a und b bekannt sind (x0 = y0 = 0).

Die Beschreibung:

Um die Mandelbrot-Menge darstellen zu können, berechnet man für jeden Punkt des Bildes die Folge mit seinen Koordinaten a (üblicherweise nach rechts) und b (nach oben) entsprechend den Gleichungen oben. Dazu setzt man eine maximale Anzahl an Iterationen (das heißt Anzahl an Folgengliedern die berechnet werden) und prüft nach jeder Iteration ob x2+y2>4 ist. Falls ja, ist der Punkt mit den Koordinaten a und b definitiv nicht Teil der Mandelbrot-Menge. Wenn diese Bedingung nach einer bestimmten Anzahl an Iterationen noch nicht erfüllt ist, kann man mit hoher Wahrscheinlichkeit davon ausgehen, dass er Teil der Mandelbrot-Menge ist (je höher die Anzahl der Iterationen desto sicherer das Ergebnis). Die Punkte, die zur Mandelbrot-Menge gehören, werden dann (meist schwarz) eingefärbt.

Dabei muss man aufpassen, dass man bei der Berechnung des zweiten Terms nicht schon mit dem neuen Ergebnis aus der ersten Berechnung arbeitet. Umgesetzt in Java sieht die Funktion zur Berechnung, ob ein Punkt (wahrscheinlich) zur Mandelbrotmenge gehört dann folgendermaßen aus:
Continue reading ‘Mandelbrotmenge einfach selbst programmiert’

Apfelmännchen für die Schule

Die als „Apfelmännchen“ bekannte Mandelbrot-Menge ist wahrscheinlich eines der schönsten Fraktale überhaupt. Die Berechnung, die zum Apfelmännchen führt, enthält jedoch komplexe Zahlen und ist deshalb normalerweise für Nichtmathematiker – insbesondere auch für Schüler – nicht nachvollziehbar.

Zomm in Visualisierung der Mandelbrot-Menge

Zoom in eigener Berechnung

Ich hoffe jedoch, dass sich mit solchen, für jedermann schön anzusehenden Fraktalen, auch die Begeisterung für Mathematik wecken lässt. Deshalb habe ich versucht eine, für interessierte Schüler schon in der Mittelstufe verständliche, Einführung zu verfassen. Sie sollte zum Einen als kleine Ergänzung des Schulstoffs im Mathematikunterricht geeignet sein, zum Anderen beschreibt sie aber auch, mit welchen Mitteln die Mandelbrot-Menge berechnet und dargestellt werden kann, ganz ohne dass man sich komplexen Zahlen beschäftigen muss. Damit kann man sich beispielsweise im Informatikunterricht ganz auf den Programmaufbau und das Programmieren konzentrieren.

Der Text ist in mehrere Abschnitte unterteilt: Nach einer kurzen Erklärung der imaginären Einheit wird die Definition der Mandelbrot-Menge angegeben und so umgeformt, dass alles mit reellen Zahlen berechnet werden kann. Dann wird erklärt, wie sich das alles in einem Programm umsetzen lässt (hier gibt es noch eine ausführlichere Erklärung mit Quellcode und lauffähigem Java-Applet). Abschließend gibt es noch Anregungen, welche Verbesserungen am Programm noch vorgenommen werden könnten. Und für alle diejenigen, die die Tiefen der Mandelbrot-Menge einfach selbst erkunden wollen, gibt es von mir noch ein entsprechendes Programm, das im Browser läuft.

Die Erklärung des Apfelmännchens für Schüler kann hier als .pdf-Datei heruntergeladen werden.

Vom „Apfelmännchen“: Die Mandelbrot-Menge

Darstellung der Mandelbrotmenge

Komplette Mandelbrotmenge

Die Mandelbrot-Menge ist ein Fraktal, das oft als das formenreichste geometrische Gebilde überhaupt bezeichnet wird. In die Randbereiche einer Darstellung dieser Menge (oft als „Apfelmännchen“ bezeichnet) kann man beliebig weit hinein zoomen und immer wieder neue, feinere Muster erkennen.

Da auf aktuellen Computern solche Bilder in Sekundenschnelle berechnet werden können, kann auch jeder selbst Fraktale erkunden oder sich mit den mathematischen Grundlagen dieser Gebilde auseinandersetzen.

Teil der Mandelbrot-Menge

Randbereich des Apfelmännchens

In der nächsten Zeit möchte ich zu diesem Thema verschiedene Beiträge verfassen, und hoffe, dass ich damit insbesondere Interessierte ohne besondere Fachkenntnisse auf diesem Gebiet für dieses und andere Fraktale begeistern kann.

Meine Beiträge zum Thema:

Programmierwettbewerbe

Wer gerne einfach so für sich programmiert, obwohl – oder gerade weil – er es nicht tun muss, hat oft wenig Austausch mit anderen. Eine Möglichkeit sich mit Anderen zu vergleichen und eventuell auch Gleichgesinnte zu treffen sind unterschiedliche Wettbewerbe.

Exemplarisch habe ich hier drei recht unterschiedliche Informatik- beziehungsweise Programmierwettbewerbe zusammengestellt:

Bundeswettbewerb Informatik

Dieser Wettbewerb startet jedes Jahr im September (ich habe hier schon darüber berichtet) und läuft über mehrere Runden. In jeder Runde muss eine Reihe von Aufgaben bearbeitet werden, wobei nicht nur auf die Funktionalität des Codes sondern vor allem auch auf die Dokumentation der Lösung Wert gelegt wird. Die Programmiersprache kann fast beliebig gewählt werden.

Dieser Wettbewerb richtet sich nur an Interessierte, die noch keine entsprechende Ausbildung begonnen haben (schwerpunktmäßig an Schüler). In den späteren Runden ist keine Gruppenarbeit mehr erlaubt und die Aufgaben müssen komplett eigenständig bearbeitet werden. Zu gewinnen gibt es am Ende unter anderem Geldpreise und Stipendien.

Robocode

Robocode ist ein Spiel bei dem in Java Roboter dafür programmiert werden, auf Wettbewerben gegeneinander kämpfen zu können. Zum englischen Spiel steht auch ein (inoffizielle?) deutsche Seite bereit. Das Ganze ist recht einsteigerfreundlich gestaltet, sodass auch Programmierer mit wenig Erfahrung schnell funktionierende Roboter entwickeln können. Um sich mit den anspruchsvolleren Demobots messen zu können braucht es dann allerdings schon etwas länger.

Hier kann grundsätzlich jeder mitmachen und Gruppen können ohne viel Aufwand auch selbst Wettbewerbe gegeneinander veranstalten.

Al Zimmermann’s Programming Contests

Bei diesem Wettbewerb wird – ein bis zwei Mal jährlich – genaugenommen eine mathematische Aufgabe gestellt, die jeder lösen darf wie er möchte. Praktisch erfordert die perfekte Lösung dieser Aufgabe allerdings deutlich mehr Rechenleistung als irgendeinem Wettbewerbsteilnehmer zur Verfügung stehen dürfte. Je besser die Lösung ist, desto mehr Punkte gibt es für eine Teilaufgabe. Es kommt also darauf an, ein möglichst effizientes Programm zu schreiben (dabei schadet ein bisschen Mathematik sicherlich nicht) und dieses dann längere Zeit rechnen zu lassen.

Hier ist die Zusammenarbeit (der Austausch von Code und Lösungen) mit anderen angemeldeten Teilnehmern verboten, die Zusammenarbeit mit Freunden, die nicht selbst teilnehmen, ist dagegen ausdrücklich erlaubt. Zu gewinnen gibt es hier für die besten beiden Teilnehmer mathematische Skulpturen.

Google Wave – kollaborative Selbstgespräche und babyblaue Revolution

Eindrücke einer Revolution

Google Wave – die Revolution der digitalen Kommunikation, die Email des Web 2.0s, die Eier legende Wollmilchsau des Internets – wird seit einigen Monaten viel diskutiert. Die Zugänge zu diesem Ort von historischer Bedeutung werden von Google unter einer Schaar von flehenden und willigen Möchtegern-Revolutionsgardisten (Beitrittsgesuche können hier eingereicht werden) verteilt. Nun hat es auch mich erwischt – ich habe keine Schweinegrippe sondern ich bin mit dem Glück der Dummen gesegnet vom Google Zufallsgenerator auserkoren zu sein.

Mein erster Eindruck ist: Dieser Wendepunkt wird als babyblaue Revolution in die Annalen der Kommunikationsgeschichte eingehen. Nach Adaption an die neuen farblichen Verhältnisse werde ich von „Doctor Wave“ in einem unterhaltsamen Video begrüßt – so unterhaltsam wird die Einführung in ein fertiges Produkte wohl kaum einmal werden. Nach diversen weiteren Videos, die all das, was ich sowieso schon im Nachbartab per try-and-error herausgefunden habe noch einmal per Screen-Capture vorführen – eigentlich ist Google wave intuitiv bedienbar – geht es los: Jetzt wird kommuniziert. Die Frage ist nur mit wem? Acht Kommunikationspartner kann ich mir einladen. Fragt sich nur, wer fähig und willens ist, die nötige revolutionäre Energie aufzubringen und die testende Verantwortung mit auf sich zu laden …

Da die Bearbeitung der Einladungen dauert, kann ich mich zunächst nur mit mir selbst unterhalten – und wie! In keinem anderen Medium haben mir je Selbstgespräche dermaßen viel Spaß gemacht. Ich kann neue Textabschnitte unten anhängen – langweilig. Ich kann aber auch jeden beliebigen Abschnitt meines bisherigen textuellen Ergusses kommentieren (also auch jede Stelle in einem Kommentar), kann unterhalb jedes Kommentars weitere unabhängige anfügen und so weiter. Auch was die Formatierung angeht kann ich, von der protzigen Hauptüberschrift bis hin zur kleinen, unsicher kursiven, aber frechgelb hinterlegten Selbstkritik, ein genaues Abbild meines Innersten erzeugen (Vorsicht an alle Datenschützer: neue Dimensionen der Möglichkeiten des Datenmissbrauchs tun sich hier auf!). Nun denn, die Kommunikationstheorie wird sich wohl in Zukunft noch mehr als bisher auch mit Chaostheorie beschäftigen müssen, wenn meine ersten Ergebnisse repräsentativ für das Verhalten anderer Nutzer von Google Wave sind.

Jetzt haben sich die ersten Freunde angemeldet. Die Jagd danach, schnellstmöglich dorthin zu scrollen, wo gerade etwas passiert, um ihnen beim Tippen zusehen zu können, beginnt und wird mit jedem zu einer Wave hinzugefügten Nutzer schwieriger. Die Möglichkeiten, diesem Treiben Einhalt zu gebieten, sind aber begrenzt. Denn es stellt sich heraus, dass der Button zum Entfernen von Nutzern nicht deshalb nicht aktiv ist, weil ich in irgendeiner Hinsicht nicht im richtigen Bedienmodus bin. Es liegt schlicht daran, dass diese Funktion noch nicht zur Verfügung steht – eine unsanfte Landung in der Realität. Einige Funktionen vermisse ich bisher sehr und manche Dinge scheinen im Moment noch etwas provisorisch gelöst. Aber alleine die Tatsache, dass die vorgesehene Einstellungsseite selbst als Wave implementiert ist, demonstriert wie flexibel und mächtig dieses Werkzeug werden wird: Vielleicht wird es irgendwann tatsächlich Einstellungsmöglichkeiten in Google Wave geben.

Nun denn, wir werden wohl noch warten müssen, bis sich dieses Werkzeug durchsetzen kann. Aber die Möglichkeit, dass Google Wave zumindest eine wertvolle Ergänzung zu bestehender Technik ist, und in vielen Fällen Kommunikation und auch gemeinsames Arbeiten an Gebrauchstexten erleichtern wird, sehe ich gegeben.

Bundeswettbewerb Informatik – jetzt lässt man rechnen!

Mittlerweile wurde schon der nächste Bundeswettbewerb gestartet. Hier meine Hinweise zum 29. Bundeswettbewerb Informatik.

Heute ist Abgabeschluss der zweiten Runde des Bundeswettbewerbs Mathematik 2009 – noch sind Aufgaben wie Lösungen vertraulich zu behandeln, erfahrungsgemäß wird es dann aber beides demnächst auf der Webseite des Wettbewerbs geben.

Heute geht aber auch schon der nächste Bundeswettbewerb los, bei dem man das Rechnen dem Computer überlassen soll – wenn man denn weiß wie: Der 28. Bundeswettbewerb Informatik (BWINF) startet jetzt pünktlich, damit sich niemand langweilen muss. Alles Wesentliche zum Wettbewerb findet sich in den Aufgaben und auch dieser Wettbewerb wird, ähnlich wie der Mathewettbewerb, in zwei Runden von zu Hause aus und anschließend für die letzten noch Verbliebenen durch direkten Menschenkontakt im Real-Life (hier: Uni Freiburg) ausgetragen. Zu gewinnen gibt es am Ende diverse Preise, auch die Aufnahme in die “Studienstiftung des deutschen Volkes”, die den Bundessiegern winkt, erinnert irgendwie entfernt an einen anderen Wettbewerb… Hat irgendwer eine Idee an was?

Die Aufgaben reichen jedenfalls von eher verwaltungstechnischen Problemen wie einem Bestellsystem für Pizzas bis zu Problemen die vermutlich viel mehr Denk- als Programmierarbeit bedeuten werden. Was Programmiersprachen angeht ist der Wettbewerb auch relativ liberal. Ich habe den Eindruck, dass kaum eine verbreitete Sprache nicht akzeptiert wird. Nur wer Wert auf den produktiven Gebrauch esoterischer Programmiersprachen legt, könnte Probleme bekommen.

PS: Zwei Wochen nach dem Abgabeschluss des BWINF Mitte November startet der Bundeswettbewerb-Mathematik 2010 dann schon wieder mit einer neuen ersten Runde. Zur 3. Runde des Bundeswettbewerbs Mathematik werde ich wohl nichts mehr schreiben, ein zweistelliges Leserpotential ist wirtschaftlich nicht sinnvoll (ok, von daher würde es dann doch wieder hierher passen).