Monte-Carlo Algorithmus mathematisch begründen/beweisen
Summary
TLDRDieses Video erklärt den Monte Carlo Algorithmus aus mathematischer Perspektive, insbesondere wie er zur Annäherung der Kreiszahl Pi verwendet wird. Es zeigt, wie zufällige Punktplatzierung im Einheitskreis die Flächeninhaltsverhältnisse misst und somit Pi schätzt. Der Erklärer verwendet ein Schaubild von Wikipedia und ein Struktogramm, um den Algorithmus zu veranschaulichen. Er diskutiert auch die Geometrie und Flächenberechnung, die hinter der Methode steckt, und zeigt, wie die Punktverteilung zur Bestimmung von Pi beiträgt. Der Algorithmus ist ineffizient, da er viele Punkte erfordert, um eine gute Annäherung zu erreichen, was die lineare Laufzeit und die damit verbundene Zeit zur Berechnung hervorhebt.
Takeaways
- 🎥 Das Video erklärt den Monte Carlo Algorithmus aus mathematischer Sicht.
- 🔍 Ziel des Monte Carlo Algorithmus ist es, die Kreiszahl Pi zu schätzen.
- 📐 Es wird ein Viertel-Einheitskreis als Schaubild verwendet, um Pi anzunähern.
- 📍 Der Algorithmus basiert auf der zufälligen Platzierung von Punkten innerhalb des Einheitskreises.
- 🎯 Punkte, die im Viertel-Einheitskreis landen, werden als 'Treffer' gezählt.
- 🔢 Das Verhältnis von Trefferpunkten zu gesamten Punkten wird zur Annäherung von Pi verwendet.
- 📚 Der Algorithmus multipliziert das Verhältnis der Trefferpunkte mit 4, um Pi zu schätzen.
- 📉 Je mehr Punkte verwendet werden, desto genauer ist die Annäherungswert für Pi.
- 📈 Der Algorithmus hat eine lineare Laufzeit und ist daher nicht sehr effizient für hochpräzise Berechnungen.
- 🤖 Ein Java-Programm wurde genutzt, um die Kreiszahl Pi auf etwa 3 Nachkommastellen genau zu schätzen.
- 📚 Um Pi auf fünf Nachkommastellen genau zu bestimmen, wären 10 Milliarden Punkte nötig.
Q & A
Was ist der Hauptzweck des Monte Carlo Algorithmus?
-Der Hauptzweck des Monte Carlo Algorithmus ist es, die Kreiszahl Pi zu approximieren.
Wie wird Pi im Monte Carlo Algorithmus approximiert?
-Pi wird approximiert, indem man zufällige Punkte im Einheitskreis verteilt und das Verhältnis der Punkte, die innerhalb des Viertelkreises liegen, zu den gesamten Punkten berechnet. Dieses Verhältnis multipliziert man dann mit 4, um eine Näherung von Pi zu erhalten.
Welche Rolle spielt der Satz des Pythagoras im Monte Carlo Algorithmus?
-Der Satz des Pythagoras wird verwendet, um zu bestimmen, ob ein zufällig platzierter Punkt innerhalb des Viertelkreises liegt, indem man prüft, ob die Summe der Quadrate der x- und y-Koordinaten kleiner oder gleich 1 ist.
Was ist das Verhältnis von Treffern im Viertelkreis zu den gesamten zufällig platzierten Punkten und warum ist es wichtig?
-Das Verhältnis von Treffern im Viertelkreis zu den gesamten zufällig platzierten Punkten ist wichtig, weil es verwendet wird, um Pi zu approximieren. Je mehr Punkte man verwendet, desto genauer ist die Approximation.
Wie viele Punkte wurden im Beispiel des Skripts verwendet, um Pi auf etwa zwei Nachkommastellen zu approximieren?
-Im Beispiel des Skripts wurden 500.000 Punkte verwendet, um Pi auf etwa zwei Nachkommastellen genau zu approximieren.
Was ist die Komplexitätsklasse des Monte Carlo Algorithmus?
-Die Komplexitätsklasse des Monte Carlo Algorithmus ist O(n), was bedeutet, dass die Laufzeit linear mit der Anzahl der zufällig platzierten Punkten, also der Eingabegröße, ansteigt.
Welche Anwendung des Monte Carlo Algorithmus wird im Skript erwähnt?
-Im Skript wird die Anwendung des Monte Carlo Algorithmus zur Approximation der Kreiszahl Pi erwähnt.
Welche Programmiersprache wurde im Skript verwendet, um den Monte Carlo Algorithmus zu implementieren?
-Im Skript wurde Java verwendet, um den Monte Carlo Algorithmus zur Approximation von Pi zu implementieren.
Was ist der Radius des Einheitskreises, der im Monte Carlo Algorithmus verwendet wird?
-Der Radius des Einheitskreises, der im Monte Carlo Algorithmus verwendet wird, beträgt 1.
Wie viele Punkte müsste man theoretisch setzen, um Pi auf fünf Nachkommastellen genau zu approximieren?
-Um Pi auf fünf Nachkommastellen genau zu approximieren, müsste man theoretisch 10 Milliarden Punkte setzen, da die Anzahl der benötigten Punkte exponentiell mit der gewünschten Genauigkeit anwächst.
Outlines
🔍 Einführung in den Monte Carlo Algorithmus
Dieses Video stellt den Monte Carlo Algorithmus aus mathematischer Perspektive vor, mit dem Ziel, die Kreiszahl Pi zu schätzen. Der Algorithmus basiert auf der zufälligen Platzierung von Punkten innerhalb eines Einheitskreises und der Berechnung des Verhältnisses zwischen den im Viertelkreis liegenden Punkten und den insgesamt geworfenen Punkten. Durch Multiplikation dieses Verhältnisses mit 4 wird eine Näherung von Pi erhalten. Der Erklärungsprozess nutzt das Schaubild aus Wikipedia und die Geometrie, um zu verdeutlichen, wie die Flächeninhaltsberechnung des Kreises und die Anwendung des Pythagorasche Satzes zur Bestimmung der Position der Punkte innerhalb des Viertelkreises eingesetzt werden.
📊 Monte Carlo Algorithmus zur Pi-Schätzung
Der zweite Absatz vertieft das Verständnis der Monte Carlo Methode, indem er den Prozess der zufälligen Punktplatzierung und die Berechnung des Flächeninhalts des Viertelkreises beschreibt. Es wird erklärt, dass durch die Punktverteilung ein Verhältnis gebildet wird, das die Fläche des Viertelkreises annähert, und dieses Verhältnis mit 4 multipliziert wird, um Pi zu schätzen. Der Absatz beinhaltet auch eine Diskussion über die Notwendigkeit einer großen Anzahl von Punkten für eine genaue Schätzung und die lineare Laufzeit des Algorithmus, die durch die Schleife im Programmcode illustriert wird. Es wird auch auf die Herausforderungen der Algorithmeneffizienz und die Notwendigkeit einer großen Anzahl von Punkten für eine genauere Pi-Schätzung hingewiesen.
🛠 Anwendung des Monte Carlo Algorithmus
Der dritte Absatz behandelt die praktische Anwendung des Monte Carlo Algorithmus, indem er die Schritte zum Schätzen von Pi mit Hilfe von Java-Programmcode beschreibt. Es wird erläutert, wie man eine große Anzahl von Punkten zufällig platziert, um die Fläche des Viertelkreises zu schätzen und wie man die Pi-Schätzung durch Multiplikation des Verhältnisses der im Viertelkreis liegenden Punkte mit 4 erhält. Der Absatz betont auch die lineare Laufzeit des Algorithmus und die damit verbundene Zeit, die benötigt wird, um eine genaue Schätzung von Pi zu erhalten. Es wird auch auf die Möglichkeit hingewiesen, die Schätzung mit mehr Punkten zu verbessern, was jedoch zu einer exponentiellen Steigerung der benötigten Rechenzeit führen kann.
Mindmap
Keywords
💡Monte Carlo Algorithmus
💡Kreiszahl Pi
💡Viertelkreis
💡Zufallspunkte
💡Flächeninhalt
💡Satz des Pythagoras
💡Verhältnis
💡Lineare Laufzeit
💡Einheitskreis
💡Struktogramm
💡Zählschleife
Highlights
Willkommen zum Video über den Monte Carlo Algorithmus aus mathematischer Sicht.
Der Monte Carlo Algorithmus nutzt zufällige Punktplatzierung, um die Kreiszahl Pi anzunähern.
Das Schaubild stammt von Wikipedia und hilft, das Konzept zu visualisieren.
Zufällige Punkte mit X und Y Koordinaten sollen im Viertelkreis landen.
Das Verhältnis von Treffern im Viertelkreis zu gesamten Punkten gibt eine Näherung von Pi.
Je mehr Punkte gesetzt werden, desto genauer ist die Pi-Annäherung.
Mit Hilfe der Geometrie und des Satzes des Pythagoras kann die Effektivität des Algorithmus erklärt werden.
Der Flächeninhalt des Einheitskreises ist Pi, was für die Annäherung von Pi relevant ist.
Der Vierteleinheitskreis hat einen Flächeninhalt von Pi/4.
Die zufällige Punktplatzierung hilft, den Flächeninhalt des Vierteleinheitskreises zu schätzen.
Das Verhältnis der Treffer multipliziert mit 4 ergibt eine Pi-Annäherung.
Der Monte Carlo Algorithmus wird mit einem Struktogramm dargestellt.
Die Algorithmus-Implementierung in Java, um Pi auf 3 Nachkommastellen zu bestimmen.
Für eine genauere Pi-Annäherung sind Millionen von Punkten erforderlich.
Der Algorithmus ist ineffizient, da eine große Anzahl von Punkten benötigt wird.
Die lineare Laufzeit des Algorithmus hängt von der Eingabegröße ab.
Eine Waldschleife könnte als alternative Implementierung dienen, mit der gleichen linearen Laufzeit.
Für eine Pi-Annäherung auf fünf Nachkommastellen wären 10 Milliarden Punkte nötig.
Die Praxisanwendung des Algorithmus ist limitiert durch die notwendige Punktzahl und Laufzeit.
Das Geheimnis hinter dem Monte Carlo Algorithmus ist die zufällige Punktplatzierung zur Pi-Bestimmung.
Ein Übungsaufschlag bietet die Möglichkeit, die Pi-Bestimmung mit Hilfe des Satzes des Pythagoras zu verständigen.
Transcripts
so herzlich willkommen zum Video in
diesem Video wollen wir uns mal mit dem
Monte Carlo Algorithmus
auseinandersetzen und zwar W wir das
Ganze von einer mathematischen Seite her
betrachten warum funktioniert dieser
Algorithmus überhaupt h neben haben wir
auch schon ein entsprechendes Schaubild
das habe ich von
Wikipedia
und die Aufgabe des Monte Algorithmus
ist ist jetzt halt
m die die Kreiszahl Pi anzunähren ne das
dieser Algorithmus funktioniert dass wir
hier tatsächlich die kiszahl P annäheren
können davon können wir uns ohne
Probleme überzeugen indem wir das ganze
Z nachprogrammieren
m aber die Frage ist wie funktioniert
das Ganze also wie schafft der
Algorithmus hier eine entsprechende
Nährung zu
bieten wir betrachten dazu den
vierteleinheitskreis also gerade diesen
Kreisabschnitt ne ne also dieses
Stückchen hier dieses
Viertel
und der Algorithmus schreibt uns jetzt
vor dass wir allgemein zufällige Punkte
P mit zufälligen X und Y Koordinaten
platzieren sollen ne und diese sollen
natürlich im Idealfall hier im
Viertelkreis landen das sind hier diese
roten Punkte die schwarzen Punkte können
sich vorstellen das sind die Punkte die
neben dran
gehen das ist
also das ist also Sinn und Zweck der
Übung es sollen ja also zufällige Punkte
hier platziert werden im Idealfall in
unserem vierteleinheitskreis aber warum
das
ganze und wie kommen wir dadurch zu
einer Nährung von
anschließend soll nun das schreibt uns
der Algorithmus vor wenn wir hier eine
entsprechende Platzierung von Punkten
vorgenommen haben müssen sich vorstellen
wir haben z.B als Beispiel das jetzt
rein beispielhaft stellen sich vor wir
haben 20 Punkte platziert ne insgesamt
und von den 20 Punkten werden jetzt zehn
Stück im Viertel einheitsgras gelandet
ne da geht es da dar um das Verhältnis
zu
bilden so das Verhältnis also aus
Treffern also an Punkten die wirklich
hier im Viertelkreis gelandet sind und
von Punkten die nebendran gegangen sind
die keine Treffer sind die wir nicht
hier zählen und dann bilden wir das
Verhältnis aus den Treffern zu den
Punkten die wir insgesamt verschossen
haben das heißt wir erhalten dann ein
Verhältnis und nach unserem Algorithmus
der schreibt uns dann vor wenn wir
dieses Verhältnis was wir dann errechnet
haben mit 4
multiplizieren dann erhalten wir eine
Näherung von PI die Näherung ist
natürlich abhängig davon wie viele
Punkte wir insgesamt gesetzt haben ne
also ganz einfach je mehr Punkte sich
setzen desto genauer wie die Näherung ne
so können sich das ganz allgemein
vorstellen aber wie gesagt die Frage ist
jetzt warum funktioniert das Ganze
überhaupt die Frage nach dem Warum und
das ganze können wir ein bisschen mit
Hilfe der Geometrie bzw der
flächenrechnung und so weiter und auch
mit Hilfe des Satz des Pythagoras können
wir das ganze einfach
ermitteln z.B die Frage ob so ein Punkt
hier auch wirklich im Viertele
Einheitskreis sitzt das können Sie ganz
einfach mit Hilfe des Satz des
Pythagoras
können Sie da einfach eine Beziehung
aufstellen werden wir gleich noch sehen
mit Hilfe der sie dann ermitteln können
ob tatsächlich der Punkt mit den
gegebenen X und Y Koordinaten hier im
einheits in dem vierteleinheitsgras
chuldigung den vierteleinheitsgras hier
sitzt oder
nicht als erstes ein Mal beschäftigen
wir uns mit dem Flächeninhalt des
Einheitskreises Achtung des gesamten
Einheitskreises also nicht nur mit
diesem viertelstückchen hier sondern der
gesamte nach unserer Formel für die
grisberechnung wir das ganzeem mit r²r
mal Pi und da wir wissen im
Einheitskreis ist dieser Radius
GLE 1 das heißt also dann kartex wir
haben einen Flächeninhalt von PI den
also dieser Einheitskreis besitzt
so das ist schon mal das das heißt also
der einhealskreis hat ein Flächeninhalt
von PI
entsprechend hat unser
vierteleinheitskreis also dieses
Stückchen hier hat dann entsprechend
einen Flächeninhalt von PI vierel soweit
so gut das ist jetzt noch nichts
bahnbrechendes und jetzt kommen wir
allerdings zu dieser zufälligen
Platzierung von Punkten das wird nämlich
jetzt interessant denn mit Hilfe dieser
zufälligen Platzierung von
Punkten können wir tatsächlich den
Flächeninhalt in diesem
vierteleinheitskreis hier
annähren und zwar ist das gerade unser
Verhältnis welches mir welches wir
bilden das ist eine
an den Flächeninhalt dieses Stückchens
hier dieses
vierteleinheitsgrases und dieses
Verhältnis entspricht ja dann gemäß hier
unserer formelbedingung gerade diesem
term PI durch 4 also PI
vier das heißt also wir haben dieses
diesen diesen Bruch hier PI vi haben wir
dann also durch unsere Punkteverteilung
angenäht
und dann wissen wir auch warum wir dann
mit 4 multiplizieren müssen was uns hier
unser Algorithmus vorschreibt dass wir
dieses Verhältnis mal 4 rechnen weil
dann erhalten wir nach unserer
formelumstellung hier die Kreiszahl Pi
da wir jetzt dieses pi4el hier
nährungsweise durch unsere
Punkteverteilung bestimmt haben hatten
wir auf die Weise auch nährungsweise die
Kreiszahl Pi das ist das ganze Geheimnis
was jetzt hinter unserem Monte Carlo
Algorithmus
steckt das heißt also durch diese
zufällige Platzierung können wir das
ganze entsprechend nährungsweise
bestimmen hier habe ich den Monte Carlo
Algorithmus mal mit Hilfe eines
struktogramms dargestellt das ganze habe
ich mit dem kostenlosen Nessi
struktogrammeditor gemacht
das ganz einfach aufgebaut
iniitalisieren hier eine zählerariable
mit ull damit zählen wir später die
Treffer die die in unserem Viertelkreis
landen hier habe ich eine Variable
eingeführt gesamt die haben wir hier mal
auf 500.000
gesetzt gesamt gibt an wie viele Punkte
wir insgesamt setzen hier haben wir eine
einfache zählchleife eine
vorschleife die zählt einfach von 0 bis
500.000 also 500.000 Durchgänge na für
jeden Punkt den wir hier setzen einen
Durchgang wir setzen hier X und Y mit
zufälligen Werten Idealfall zwischen 0
und
1 durch dieses Feld durch diese
Beziehung hier x² + y² soll kleiner
gleich 1 sein wie gesagt das können sie
durch einfach durch den Satz des
Pythagoras bestimmen ne können wir dann
hier ganz einfach
prüfen ob dieser Punkt den wir hier
zufällig gebildet haben durch X und Y
Koordinaten im viertelinheitskreis
sitzt und wenn er da sitzt dann zählen
wir ihn natürlich wenn er da nicht sitzt
machen wir nichts das heißt also wenn x²
+ y² kleiner g= 1 ist dann wird unser
Punkt
gezählt ansonsten passiert nichts und
wenn diese Schleife dann hier komplett
durchgelaufen ist da können wir hier
einfach uns verhältnisbilden aus den
Treffern im
viertelinheitskreis und den Punkten die
wir insgesamt gesetzt
haben und die Kreiszahl P wird dann
einfach gebildet Verhältnis mal 4 und
das geben wir dann einfach noch in der
Konsole
aus da habe ich mal so ein bisschen
rumexerimentiert um die Kreiszahl P auf
etwa zwei nachkommerstellen genau zu
bilden musste ich 500.000 Punkte
insgesamt hier setzen
m das ganze habe ich mit Java Programm
realisiert um die Kreiszahl Pi auf etwa
3 Nachkommastellen genau zu setzen
musste ich schon 3 Millionen Punkte
insgesamt hier setzen und ab dann wurde
es schon deutlich schwieriger
denn um die kreiszah P auf hier
nachkommerstellen genau zu bestimmen
muss ich im
Optimalfall bereits 500 Millionen 500
Millionen Punkte insgesamt
setzen Problem was wir haben dieser
Algorithmus
ist nicht gerade effizient einmal weil
wir hier eine entsprechend große Anzahl
an Punkten setzen müssen also hier
gesamt entsprechend setzen müssen dieses
gesamt hier ist dann auch gleichzeitig
unsere eingabegröße
entspricht also hier diesem n habe ich
hier noch mal hingeschrieben n
entspricht Gesamtgröße oder BZ ist die
Gesamtgröße und dieser Algorithmus hat
eine lineare Laufzeit also die
komplexitätsklasse o von M und in Jahre
Laufzeit haben wir eben wegen dieser
Schleife hier wegen dieser Zählschleife
in dem Fall weil die abhängig ist von
unserer eingabegrößen komplett
durchzählt das ganze hätten wir auch Ken
mit einer waldschleife realisieren
können al ein klein bisschen aufwendiger
aber dann hätten wir ebenfalls eine
lineare Laufzeit
gehabt und sie sehen dann schon für eine
entsprechend gute Annäherung zu bilden
brauchen Sie natürlich entsprechend
viele Punkte sie können sich schon
denken wir auf 4 nachkommerstell genau
die kasszahl P anzunehen 500 Millionen
Punkte für fünf Nachkommstellen hätten
sie dann schon 10 Milliarden Punkte
benötigt und bei einer linearen Laufzeit
ist das natürlich nicht gerade moderat
von der Laufzeit hier es seidem
natürlich sie sagen ist mir egal ob der
Rechner mehrere Stunden arbeiten muss ne
oder wenn Sie beispielsweise einen
Hochleistungscomputer zur Verfügung
hätten aber wir hat das schon ist also
nicht so effizient ne aber okay
das wä es an dieser Stelle schon wieder
gewesen
ne also ganz wichtig was Sie sich merken
müssen mit dieser mit dieser Beziehung
her können Sie tatsächlich ermitteln ob
der Punkt im viertelinheitsreis liegt
und als kleine Übungsaufgabe kten sie
z.B versuchen mal auf diese Beziehung zu
kommen
Stichwort Satz des Pythagoras ne
und dann müssen sie noch beachten dass
der Radius in unserem Einheitskreis also
auch in unserem vierteleinheitskreis
eins beträgt ne und da können sie mal
versuchen auf diese Beziehung jetzt zu
kommen okay das war's an dieser Stelle
schon wieder ich bedanke mich recht
freundlich fürs zuschauen würde mich
noch über ein abon freuen vielen lieben
Dank
Browse More Related Video
Pinterest Algorithm: How to Beat it in 2024
Was ist ein Algorithmus? - Einstieg Algorithmen 1
29. What is Return On Equity - Warren Buffett's Favorite Number
Topologie-Optimierung: Mach es gleich richtig!
Dropshipping Produkte finden, wie es keiner tut (aber jeder tun sollte)
I spent $41k to Make $177k with TikTok Ads
5.0 / 5 (0 votes)