כוח גס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במדעי המחשב, כוח גס (או: כוח ברוטאלי, מאנגלית: Brute Force) הוא סוג של אלגוריתם שאין בו תחכום, כזה הפועל בדרך הפשוטה ביותר להשגת המטרה, תוך שהוא צורך לעתים כמויות גדולות יחסית של משאבי מחשב (זמן או זיכרון).

דוגמה לאלגוריתם מסוג זה הוא פיצוחן של סיסמאות כניסה למחשב באמצעות ניסיון להיכנס עם כל הסיסמאות האפשריות, עד להצלחה. טכניקה זו אינה יעילה, בדרך-כלל, מכיוון שמספר הצירופים האפשריים הוא עצום. לסיסמה בת 8 תווים עם אלפבית בן 36 סוגי תווים ישנם 2,821,109,907,456 = 368 אפשרויות שונות. נניח שישנה אפשרות לנסות מיליון סיסמאות בשנייה, במצב הזה יקח לנסות את כלל האפשריות 2,821,109 שניות שהן קצת יותר מחודש. במקרה זה אלגוריתם הפועל בכוח גס אינו מצליח לתת פתרון נאות לבעיה (למעשה במקרים רבים תינעל האפשרות להזדהות כבר לאחר ניסיונות מעטים).

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

המושג "כוח גס" תקף גם להוכחות מתמטיות שבהן השיטה להוכחה היא ביצוע חישובים ארוכים ומייגעים, אך ישירים, של כל המקרים האפשריים, במקום לחשוב על פתרון אלגנטי יותר. ההוכחה הראשונה של משפט ארבעת הצבעים מורכבת משני צעדים: ראשית מראים שכדי להוכיח את הטענה (המתייחסת לאינסוף מצבים), מספיק לבדוק אותה ב- 1,936 מקרים מסוימים; אלו נבדקים ב'כוח', במחשב.

ראו גם[עריכת קוד מקור | עריכה]