Quelltext der Seite Fraktale

Ein '''Fraktal''' ist ein Schema (oder Muster), welches ein Bild erzeugt. Fraktale kommen auch sehr häufig in der Natur vor. Bekannte Fraktale sind z.B. das {{wpd|Sierpinski-Dreieck}}, die {{wpd|Koch-Kurve}} oder die {{wpd|Mandelbrot-Menge}}.

Fraktale werden meist in mehreren Schritten, sogenannten Iterationen aufgebaut. Jede Iteration verfeinert das Fraktal. Das Fraktal selbst benötigt theoretisch unendlich viele Iterationen, kann aber in der Praxis mit einer endlichen Anzahl von Iterationen angenähert werden.
[[Datei:mandelbrot.png|right|320px]]

== Koch-Kurve ==
[[Datei:Kochkurve4Iterationen.png|300px|right]]
Die Koch-Kurve ist ein relativ simples Fraktal, welches deshalb auch sehr einfach in Scratch implementiert werden kann. Wie der Name schon sagt, besteht dieses Fraktal nur aus einer Linie. Die Koch-Kurve ist Bestandteil der [https://de.wikipedia.org/wiki/Koch-Kurve#Kochsche_Schneeflocke Koch-Schneeflocke].

Die Koch-Kurve wird in mehreren Schritten gezeichnet. Am Anfang hat man nur eine gerade Linie. Dann wird in jedem Schritt die Linie in drei gleich große Teile geteilt. Aus dem mittleren Teil wird eine "Spitze". Dieser Prozess wird für alle jetzt entstandene Linien wiederholt. Das sind die Iterationen.

=== Programmierung in Scratch ===
Das Dreieck, durch das das mittlere Drittel einer Linie ersetzt wird, ist gleichseitig. Das bedeutet auch, dass jeder Winkel 60° beträgt.<br/>
[[Datei:KochImplementation1.png|650px]]

Dann müssen die Winkel, um die sich der Malstift dreht, berechnet werden.<br/>
[[Datei:KochImplementation2.png|420px]]

Mit diesem Wissen kann jetzt auch schon die erste Iteration der Koch-Kurve gezeichnet werden.

<scratchblocks>
Wenn die grüne Flagge angeklickt
setze Richtung auf (90) Grad
gehe zu x: (-240) y: (-179)
lösche alles
schalte Stift ein
male die erste Iteration mit Länge (480)
schalte Stift aus

Definiere male die erste Iteration mit Länge (länge)
gehe ((länge)/(3)) er Schritt
drehe dich nach links um (60) Grad
gehe ((länge)/(3)) er Schritt
drehe dich nach rechts um (120) Grad
gehe ((länge)/(3)) er Schritt
drehe dich nach links um (60) Grad
gehe ((länge)/(3)) er Schritt
</scratchblocks>

Wenn man allerdings mehrere Iterationen durchführen will, ist das hier sehr unpraktisch. Da bietet sich [[Rekursion]] an. Das heißt, statt dem "gehe (länge / 3)er-Schritt"-Block der eigene Block nochmal aufgerufen, mit einem drittel der Länge. Das könnte z.B. so aussehen:

<scratchblocks>
Wenn die grüne Flagge angeklickt
setze Richtung auf (90) Grad
gehe zu x: (-240) y: (-179)
lösche alles
schalte Stift ein
male (4) Iterationen mit Länge (480)
schalte Stift aus

Definiere male (iterationen) Iterationen mit Länge (länge)
falls <(iterationen)=(1)>, dann
gehe ((länge)/(3)) er Schritt
sonst
male ((iterationen)-(1)) Iterationen mit Länge ((länge)/(3))
ende
drehe dich nach links um (60) Grad
falls <(iterationen)=(1)>, dann
gehe ((länge)/(3)) er Schritt
sonst
male ((iterationen)-(1)) Iterationen mit Länge ((länge)/(3))
ende
drehe dich nach rechts um (120) Grad
falls <(iterationen)=(1)>, dann
gehe ((länge)/(3)) er Schritt
sonst
male ((iterationen)-(1)) Iterationen mit Länge ((länge)/(3))
ende
drehe dich nach links um (60) Grad
falls <(iterationen)=(1)>, dann
gehe ((länge)/(3)) er Schritt
sonst
male ((iterationen)-(1)) Iterationen mit Länge ((länge)/(3))
ende
</scratchblocks>

{{Scratch-Projekt|username=Kangalioo|projektnr=110807869|projektname=Koch-Kurve}}

[[Datei:KochSchneeflocke.png|right|150px|Die Koch-Schneeflocke nach 7 Iterationen]]

=== Koch-Schneeflocke ===
Man kann auch statt einer einzigen Linie ein gleichseitiges Dreieck als Startbild benutzen. Die oben beschriebenen Schritte werden dann für alle drei Linien des Dreiecks durchgeführt. Das ist die Koch-Schneeflocke.

== Mandelbrot-Menge ==
[[Datei:mandelbrot.png|right|350px]]
Die Mandelbrot-Menge ist eine Gruppe von Zahlen (eine Menge), welche allesamt eine bestimmte Eigenschaft aufweisen. Diese Zahlen sind [http://de.wikipedia.org/wiki/Komplexe_Zahlen komplexe Zahlen]. 

=== Komplexe Zahlen ===
Komplexe Zahlen sind eine andere Art von Zahlen. Diese Zahlen bestehen im Grundprinzip aus 2 einzelnen Zahlen. Die erste Zahl nennt man den "Realteil" der komplexen Zahl und die zweite Zahl nennt man "Imaginärteil". Warum das so ist, ist nicht so wichtig (Andernfalls auf [http://de.wikipedia.org/wiki/Komplexe_Zahlen Wikipedia] nachlesen). Dass eine komplexe Zahl aus zwei Teilen besteht, bedeutet, dass man eine komplexe Zahl nicht mit einem [http://de.wikipedia.org/wiki/Zahlengerade Zahlenstrahl] darstellen kann, weil sie nicht 1-dimensional sondern 2-dimensional ist. Zur Darstellung einer komplexen Zahl wird in der Praxis häufig ein Koordinatensystem benutzt.

Es gibt verschiedene Schreibweisen für komplexe Zahlen. Es gibt einmal folgende Schreibweise: (''Realteil''|''Imaginärteil''). Eine komplexe Zahlen mit Realteil 3 und Imaginärteil 4 würde man also so schreiben: (3|4). Möglich wäre auch eine andere Schreibweise: ''Realteil''+i*''Imaginärteil''. Eine komplexe Zahlen mit Realteil 3 und Imaginärteil 4 sähe hier so aus: 3+i*4. Hier wird beides verwendet, je nachdem ob es passt.

Wenn der Realteil der ersten Zahl a ist, der Imaginärteil der ersten Zahl b, der Realteil der zweiten Zahl c, der Imaginärteil der vierten Zahl d und das Ergebnis e, dann werden Grundrechenarten wie folgt durchgeführt:

Zur Addition zweier komplexer Zahlen werden einfach die beiden Realteile und die beiden Imaginärteile addiert.<br/>
e= '''a+c'''+i*'''b+d'''

Die Multiplikation ist etwas schwieriger. Der Realteil des Ergebnisses ist die Differenz zwischen dem Produkt der Realteile der ersten und der zweiten Zahl und dem Produkt der Imaginärteile der ersten und zweiten Zahl. Der Imaginärteil des Ergebnisses ist die Summe des Produktes des Realteils der ersten Zahl und des Imaginärteils der zweiten Zahl und des Produktes des Imaginärteils der ersten Zahl und des Realteils der zweiten Zahl.<br/>
e= '''(a*c-b*d)'''+i*'''(a*d+b*c)'''

Subtraktion und Division braucht man für die Mandelbrot-Menge nicht.

=== Die Formel ===
Man muss wissen: Ein Bild vom Mandelbrot-Fraktal ist eigentlich ein Koordinatensystem, auf dem viele komplexe Zahlen dargestellt sind. Jeder Pixel ist eine komplexe Zahl im Koordinatensystem.

Die Definition der Mandelbrot-Menge kann man so beschreiben: Eine komplexe Zahl c gehört zu der Mandelbrot-Menge wenn sie in der Folge z beschränkt bleibt.<br/>
[[Datei:MandelbrotGleichung.png|114px]]

Was bedeutet das jetzt? C ist die Zahl, für die geprüft werden soll, ob sie in der Mandelbrot-Menge enthalten ist. Z ist eine Reihe von Zahlen, die berechnet werden muss. Das "nullte" Element von z ist 0 (bzw. Realteil 0, Imaginärteil 0). Ein Element von z ist gleich die Summe von c und dem Quadrat der vorherigen Zahl. Die vierte Zahl von z ist also gleich 3. Zahl von z, zum Quadrat, plus c. Man muss immer daran denken, dass alle Zahlen von z und c komplex sind.
Jede Berechnung eines neuen Elements von z ist eine Iteration. Wenn das letzte Element von z kleiner als 2 ist (Realteil kleiner 2 u. Imaginärteil kleiner 2), gehört c, also die Zahl welche geprüft wird, definitiv '''nicht''' zur Mandelbrot-Menge. 

Dieser Vorgang muss für alle komplexen Zahlen, die geprüft werden sollen, einzeln durchgeführt werden. Hier sind zwei Beispiele:

==== Erstes Beispiel ====
Die komplexe Zahl die überprüft werden soll ist (-0.2|0.5). Das ist also c. Die Folge z muss jetzt berechnet werden. Wichtig ist, dass z<sub>0</sub>=(0|0) ist. Jetzt wird in jedem Schritt ein neues Element von z berechnet.

z<sub>n</sub>=z<sub>n-1</sub><sup>2</sup>+c

z<sub>1</sub> = z<sub>0</sub><sup>2</sup>+(-0.2|0.5) = (0|0)<sup>2</sup>+(-0.2|0.5) = (-0.2|0.5)<br/>
z<sub>2</sub> = z<sub>1</sub><sup>2</sup>+(-0.2|0.5) = (-0.2|0.5)<sup>2</sup>+(-0.2|0.5) = (-0.41|0.3)<br/>
z<sub>3</sub> = z<sub>2</sub><sup>2</sup>+(-0.2|0.5) = (-0.41|0.3)<sup>2</sup>+(-0.2|0.5) = (-0.122|0.254)<br/>
z<sub>4</sub> = z<sub>3</sub><sup>2</sup>+(-0.2|0.5) = (-0.122|0.254)<sup>2</sup>+(-0.2|0.5) = (-0.25|0.438)<br/>
z<sub>5</sub> = z<sub>4</sub><sup>2</sup>+(-0.2|0.5) = (-0.25|0.438)<sup>2</sup>+(-0.2|0.5) = (-0.329|0.281)<br/>
...

Hier sind 5 Iterationen aufgeführt. Das letzte Element von z ist kleiner als 2, also ist (-0.2|0.5) '''wahrscheinlich''' in der Mandelbrot-Menge. Man kann es nicht zu hundert Prozent sagen, weil man nicht weiß, ob der Wert in den nächsten Iterationen über 2 steigt.

==== Zweites Beispiel ====
Die komplexe Zahl die hier überprüft werden soll ist (0.1|0.8).

z<sub>n</sub>=z<sub>n-1</sub><sup>2</sup>+c

z<sub>1</sub> = z<sub>0</sub><sup>2</sup>+(0.1|0.8) = (0|0)<sup>2</sup>+(0.1|0.8) = (0.1|0.8)<br/>
z<sub>2</sub> = z<sub>1</sub><sup>2</sup>+(0.1|0.8) = (0.1|0.8)<sup>2</sup>+(0.1|0.8) = (-0.53|0.96)<br/>
z<sub>3</sub> = z<sub>2</sub><sup>2</sup>+(0.1|0.8) = (-0.53|0.96)<sup>2</sup>+(0.1|0.8) = (-0.541|-0.218)<br/>
z<sub>4</sub> = z<sub>3</sub><sup>2</sup>+(0.1|0.8) = (-0.541|-0.218)<sup>2</sup>+(0.1|0.8) = (0.345|1.036)<br/>
z<sub>5</sub> = z<sub>4</sub><sup>2</sup>+(0.1|0.8) = (0.345|1.036)<sup>2</sup>+(0.1|0.8) = (-0.854|1.515)<br/>
z<sub>6</sub> = z<sub>5</sub><sup>2</sup>+(0.1|0.8) = (-0.854|1.515)<sup>2</sup>+(0.1|0.8) = (-1.466|-1.788)<br/>
z<sub>7</sub> = z<sub>6</sub><sup>2</sup>+(0.1|0.8) = (-1.466|-1.788)<sup>2</sup>+(0.1|0.8) = (-0.948|6.042)<br/>

Man sieht hier, dass 5 Iterationen nicht ausgereicht hätten. Wäre die 6. Iteration nicht berechnet worden, wäre der Wert noch unter 2. Man würde also vermuten, dass (0.1|0.8) zur Mandelbrot-Menge gehört. Bei Iteration 6 sieht man jedoch das Gegenteil.

=== Darstellung ===
Es gibt verschiedene Möglichkeiten zur Darstellung des Mandelbrot-Fraktals. Die einfachste ist, jeden Punkt einer komplexen Zahl auf dem Koordinatensystem schwarz zu färben, wenn er in der Mandelbrot-Menge enthalten ist und weiß zu färben, wenn er nicht in der Mandelbrot-Menge enthalten ist.
=== Scratch Beispiele===
{|style="text-align: center;" border=1
|-
|{{SBildlink|user=uiopscratch327|nr=107716095|name=Mandelbrot}}
|{{SBildlink|user=kieranblackley|nr=95388932|name=Mandelbrot Pen Made Pattern}}
|{{SBildlink|user=Cyclone103|nr=194167|name=Super Fast Mandelbrot}}
|{{SBildlink|user=twins_paradox|nr=20912974|name=Mandelbrot Set Explorer 2.5}}
|{{SBildlink|user=PeaBrainProgram|nr=48815918|name=Koch curve with a Mandelbrot set formula}}
|-
|{{SBildlink|user=hugmyster|nr=83837694|name=Mandelbrot with full details}} 

sehr schnell 

durch Klones!!
|{{SBildlink|user=Zro716|nr=53610528|name=mandelbrot}} 
|
|
|-
|}
siehe auch:
* [https://scratch.mit.edu/studios/1440978/ Studio: "Mandelbrot and Julia sets"]
* [https://scratch.mit.edu/studios/1037658/ Studio: "Mandelbrot set projects"]
== Hintergrundvideo ==
{{AdvancedYouTube|qqRiZWGwk-A}}
Fraktale Die verborgene Ordnung der Natur Mandelbrot und seine Welt

{{en|Recursion and Fractals}}
[[hu:Fraktálok]]

[[Kategorie:Algorithmen und Datenstrukturen]][[en:Recursion and Fractals]]