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