הצגת המקור של הדף "שיטת מונטה קרלו"

'''שיטת מונטה קרלו''' היא שיטה לפתרון בעיות חישוביות באמצעות [[מספרים אקראיים]] (בניגוד ל[[אלגוריתם דטרמיניסטי|אלגוריתמים דטרמיניסטיים]] הנהוגים בדרך כלל).

אלגוריתמי מונטה קרלו הם אלגוריתמים חישוביים שמגרילים מספרים אקראיים מספר גדול של פעמים ומבצעים חישובים על המספרים שהוגרלו. לעיתים קרובות משתמשים באלגוריתמי מונטה-קרלו כדי לבצע סימולציות על מערכות פיזיקליות או מתמטיות מורכבות. השימוש העיקרי בהם הוא כדי לפתור בעיות שאינן ניתנות לפתרון מתמטי מדויק, או כדי לחסוך בכוח [[חישוב (מדעי המחשב)|חישוב]].

אלגוריתמים אלו מוצלחים במיוחד עבור מערכות שבהן יש הרבה [[דרגות חופש (פיזיקה וכימיה)|דרגות חופש]] שתלויות אחת בשנייה, כמו ב[[הידרודינמיקה]], מבנים תאיים וב[[פיזיקת חלקיקים]]. שימוש נוסף חשוב שנעשה בהם הוא לצורך חישוב [[אינטגרל רב-ממדי|אינטגרלים רב ממדיים]]. זו שיטה מצוינת לחישוב של [[סיכון שוק|סיכונים]], טובה יותר משיטות מתמטיות אחרות ומאינטואיציה אנושית.

השם "שיטות מונטה קרלו" (Monte-Carlo methods) ניתן לאלגוריתמים אלו על ידי פיזיקאים אמריקאיים ב[[המעבדה הלאומית לוס אלמוס|מעבדה הלאומית לוס אלמוס]]. שם זה נובע מהטכניקה האקראית שביסוד השיטה, ומהמוניטין שיצא ל[[קזינו]] של [[מונטה קרלו]], והוא ניתן לשיטה על ידי חלוציה: ה[[פיזיקאי]] [[אנריקו פרמי]] וה[[מתמטיקאי]]ם [[סטניסלב אולם]], [[ג'ון פון נוימן]] ו[[ניק מטרופוליס]].

שיטות אקראיות לביצוע חישובים היו בשימוש עוד לפני המצאת ה[[מחשב]]. בשנת [[1930]] השתמש [[אנריקו פרמי|פרמי]] בשיטה כזו לחישוב תכונותיו של ה[[נייטרון]], שהתגלה באותה עת. עם זאת, המצאת המחשב, שאיפשרה ביצוע סימולציות בקלות רבה, נתנה דחיפה עיקרית לחקירתן של שיטות אלה ולהתפתחותן. בפרט, שיטות אלה שימשו בהיקף נרחב ב[[פרויקט מנהטן]] לפיתוח [[פצצת אטום]].

שיטה דומה היא [[שיטת לאס-וגאס]] שבה האלגוריתמים מניבים תמיד תוצאה נכונה, אך זמן החישוב לרוב ארוך יותר.

== מבנה האלגוריתמים ==

ישנה קבוצה גדולה של אלגוריתמים שנמצאים בשימוש נרחב שנקראים אלגוריתמי מונטה-קרלו. לרוב האלגוריתמים האלו במבנה הבא:

# מוגדר מרחב של קלטים אפשריים לאלגוריתם.
# הקלטים נבחרים על ידי מחשב מתוך מרחב הקלטים האפשריים על ידי שימוש ב[[פונקציית הסתברות]] מסוימת המופעלת על מרחב זה.
# על קלטים אלו מחושב חישוב [[אלגוריתם דטרמיניסטי|דטרמיניסטי]] מסוים.
# הסטטיסטיקה של כל התוצאות נאספת ומוצגת.

== דוגמה: אלגוריתם מונטה קרלו לקירוב π ==
[[קובץ:Estimacion de Pi por Montercarlo.gif|שמאל|ממוזער|250px|אנימציה של חישוב פאי באמצעות הטלת מיליון נקודות אקראיות אל עיגול החסום בריבוע]]
דוגמה פשוטה המממשת שיטה זו היא הדרך הבאה לחישוב ערך מקורב של [[פאי|π]]:

# על לוח נצייר [[ריבוע]] שאורך צלעו שתי יחידות. נצייר [[מעגל חסום]] בריבוע - מעגל שרדיוסו שווה ליחידה אחת.
# נטיל חצים לעבר הריבוע. לא נכוון את החץ למרכז הריבוע, אלא אל הריבוע כולו באופן אקראי. פונקציית ההסתברות במקרה זה היא אחידה, כלומר יש הסתברות שווה לפגיעה בכל נקודה על פני הריבוע.
# כל חץ שפגע נבדק האם הוא בתוך העיגול או מחוץ לעיגול (אך בתוך הריבוע). למשל, נבדוק האם ה[[מרחק]] בין כל נקודת פגיעה לבין הנקודה (0,0) גדול מרדיוס המעגל או לא, וכך נדע האם היא בתוך העיגול או מחוץ לעיגול (אך בתוך הריבוע).פעולה זו מקבילה לחישוב הדטרמיניסטי שמבוצע.
# נבדוק כמה חיצים היו בתוך העיגול מתוך כמות החצים הכוללת. לאחר מספר רב של הטלות, היחס בין מספר הפעמים שהחצים פגעו בתוך המעגל, למספר הפעמים שבהם פגעו בתוך הריבוע שואף ליחס שבין שטחי שתי הצורות, שהוא <math>\pi/4</math> (כאשר רדיוס העיגול הוא <math>\ r</math>, שטח העיגול הוא <math>\pi r^2</math> ושטח הריבוע החוסם הוא <math>\ 4r^2</math>). 

ככל שמטילים יותר חיצים, הערך של מספר החצים בתוך העיגול חלקי מספר החצים הכללי, [[גבול (מתמטיקה)|ישאף]] לערך <math>\pi/4</math>,  ויש להכפיל פי 4 להערכת  <math>\pi</math>.

מובן שמימוש פיזי של שיטה זו, באמצעות הטלה של חצים מוחשיים, עלול להיות מייגע. דרך מייגעת פחות תהיה כתיבת [[תוכנית מחשב]] שמבצעת [[סימולציה]] של פעולה זו.

לחישובו של <math>\pi</math> קיימות שיטות פשוטות יותר ומדויקות יותר, אך לפתרונן של בעיות חישוביות מסובכות יותר עשויה שיטת מונטה-קרלו להיות הדרך הפשוטה והמהירה לקבלת תוצאה ברמת דיוק סבירה. לשיטה זו חשיבות רבה ב[[פיזיקה חישובית]].

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}
* {{בריטניקה}}
* {{דף שער בספרייה הלאומית|987007543534905171|שיטת מונטה קרלו}}

{{בקרת זהויות}}

[[קטגוריה:אלגוריתמים]]
[[קטגוריה:פיזיקה סטטיסטית]]
[[קטגוריה:אנליזה נומרית]]
[[קטגוריה:תורת ההסתברות]]
[[קטגוריה:אקראיות]]