Faul sein: Simulieren statt grübeln!
0. Hintergrund
Viele mathematische Probleme kann man zwar exakt lösen, doch dazu muss man überlegen, und zu viel Überlegen macht nur Kopf-Aua! ;-) Wozu haben wir schnelle (aber dumme) Computer, mit denen wir in Windeseile das Problem simulieren können und so eine näherungsweise Lösung bekommen?
Das Schreiben einer geeigneten Monte-Carlo-Simulation ist dagegen eine vergleichsweise einfache Sache, wobei sie aber dennoch komplex genug ist, um z.B. für ein Coding-Dojo geeignet zu sein, das man in 15 … 45 Minuten schaffen sollte.
1. Tetraeder in der Kugel
Auf Youtube bin ich vor kurzem über diese Aufgabe gestolpert:
Auf einer Kugeloberfläche werden zufällig vier Punkte ausgewählt. Wie hoch ist die Wahrscheinlichkeit,
dass der Mittelpunkt der Kugel innerhalb des Tetraeders liegt, der aus diesen vier Punkten gebildet wird?
Das Video leitet den exakten Wert für die Wahrscheinlichkeit her, aber man kann es ja auch einfach per MC-Simulation
lösen, oder? :-D
2. Schnitt dreier Würfel
Schneidet man 3 konzentrische, gleich große, aber gegeneinander verdrehte Würfel, ergibt sich
ein komplexer Schnittkörper, siehe nebenstehende Abbildung für ein paar Beispiele. Das Volumen
dieser Schnittkörper variiert, je nach Drehwinkel der Würfel.
O.B.d.A. sei der erste Würfel in unverdrehter, achsparalleler Lage und die anderen
beiden Würfel nacheinander um die X-, Y- und Z-Achse gedreht. Die Winkel mögen mit
φx, φy, φz und
θx, θy, θz bezeichnet werden.
Gesucht sind nun die Drehwinkel, die das Volumen des Schnittkörpers minimieren.
3. Flächeninhalt der Mandelbrotmenge
Die Fläche der Mandelbrotmenge hat die Form des bekannten "Apfelmännchens" (siehe nebenstehende Grafik).
Die Größe dieser Fläche ist aber bis heute nicht exakt bekannt. Also lasst uns einen
speziellen Fraktalgenerator schreiben, dessen Fokus nicht auf eine hübsche Darstellung dieses
Fraktals liegt, sondern eben auf die Berechnung des Flächeninhalts der in der nebenstehenden Grafik
schwarzen Fläche.
"Teile und Herrsche" sei der hier verfolgte Ansatz, indem man an den zerfransten Kanten rekursiv
immer weiter hinabsteigt, bis man an die Genauigkeitsgrenzen des verwendeten (Gleitkomma-)Zahlenformats
kommt.
4. Polyominos
Wer Tetris kennt, kennt auch die 7 verschiedenen Figuren (davon zwei spiegelsymmetrische Paare), die man aus vier aneinander liegenden
Quadraten bilden kann. Diese Figuren nennt man auch "Tetrominos". Nebenstehende Grafik zeigt alle
Figuren, die sich aus fünf Quadraten bilden lassen ("Pentominos"), wobei hierbei die spiegelsymmetrsichen
Varianten nicht doppelt gezählt wurden.
Die Aufgabe besteht nun darin, ein Programm zu schreiben, das die Anzahl der "n-ominos" bestimmt,
wahlweise mit Zählung der spiegelsymmetrischen Varianten oder nicht. Streng genommen ist das keine
MC-Simulation, aber ein Programm, das stupide "herumprobiert" sollte ausreichend sein, zumindest
für n<10.