פסלונים נפלאים
הטטריס האגדי נוצר בשנות ה-80 של המאה הקודמת על ידי אלכסיי פאג'יטנוב. מתמטיקאי
פאג'יטנוב הוציא את אחת הגרסאות הראשונות של המשחק על המיקרו-מחשב הסובייטי "Electronics-60"
המטרה של טטריס היא לזוז ולסובב נפילהצורות גיאומטריות כדי ליצור שורות שלמות בתחתית מגרש המשחקים, לצבור נקודות. מנקודת מבט מעשית זהו משחק של מהירות תגובה וריכוז, אבל מתמטיקאים מסתכלים על זה מזווית אחרת. מדענים ניתחו את המורכבות החישובית של אלגוריתם הטטריס וקבעו שהוא שייך למחלקה של פולינום NP-שלם - לא דטרמיניסטי; אין אלגוריתמי פתרון יעילים לדברים כאלה.
הבעיה המרכזית היא שהכמות שללמציאת פתרון לחישוב גדל באופן אקספוננציאלי עם עלייה במספר המשתנים (גודל הבעיה). לדוגמה, אם יש ארבעה פרמטרים, יש צורך ב-16 איטרציות, ואם 100, אז 2 ^ 100, שזה יותר מאטומים ביקום (!). מחשב טיפוסי, כשהוא מכוון כראוי, יכול לבצע כמה מיליארדי איטרציות אלו בשנייה. בהתאם לכך, הוא יכול בקלות לפתור בעיות NP-קטנות על ידי ספירה, וכאשר המשתנים יהיו יותר מ-15 באופן ניכר, הוא יפסיק לפתור.
לגבי טטריס.גודל המשימה של המשחק הקלאסי קטן: בשלב נפרד, יש נוף נוכחי בזכוכית (שדה המשחק) - זה פרמטר, זה לא משפיע באופן משמעותי על כמות החישובים. יש מידע על הדמות הנוכחית והבאה - אלו שתי קבוצות משתנים: לכל דמות יש מקסימום ארבע (אם כי לריבוע - רק אחד) כיוונים במרחב ומקסימום 10 קואורדינטות של "הנחיתה" של הצורות. לכל מהלך יש 40 מצבים, לשניים יש 1,600, אין יותר מידע, זו בעיה קטנה של NP. למרות שטטריס יכול להיות מסובך: הגדל את מספר התאים ל-100 וודא שהשחקן יודע לא רק מה יהיה הנתון הבא, אלא גם מאה מהתאים הבאים, אז יהיו בעיות.
אתה גם לא מכיר משחקים אחרים עם NPמשמועות: שולה מוקשים, סודוקו, תג ואפילו גרסה לא מסחרית של סופר מריו. למרות פשטות החוקים שלהם, בתנאים מסוימים הממד שלהם גדל, המחשב אינו יכול להציע פתרון אידיאלי. למה למתמטיקאים אכפת? מכיוון שבחירה במסלול הטוב ביותר, אופטימיזציה של תהליך או לוח זמנים הן גם בעיות במחלקת NP.
"מריו" הקלאסי נראה כך
משחקי לוגיקה הם שדה בדיקה נוח במיוחד עבורבדיקת אלגוריתמים והטמעת התוכנה שלהם. פאזלים הם לרוב "טהורים", ללא סוגים שונים של חריגים לכללים הגלומים בבעיות מעשיות. למרחב המצב של בעיות כאלה יש ממד מתכוונן, והמאפיינים אינם משתנים בעת שינוי קנה מידה (לדוגמה, תגים 2x2, 4x4, 3x6). כל המדינות מתוארות באותו אופן. גם התיאור המתמטי של חידות, ככלל, אינו מורכב כמו אלה של בעיות חיים.
הזמן של צעצועים "קוונטיים".
אותה בעיה לגבי תיק גב (איך להתאים עוד דבריםבשטח מוגבל) די מזכיר משחק של טטריס, והתוצאה האפקטיבית תהיה שימושית עבור חברות לוגיסטיקה, כי היא תאפשר להן לא לבזבז משאבים. אם נמצא אלגוריתם "מהיר פולינומי" עבור כל אחת מהבעיות או המשחקים הללו, אז כל בעיה אחרת ממחלקת NP יכולה להיפתר בדיוק כמו "מהיר". בתיאוריה, מחשבים קוונטיים יעזרו בכך, אך עד כה ישנם רק אבות טיפוס של מחשבי העתיד הללו. בשנת 2018 אף הומצא קונספט חדש כדי לתאר את מצב הייצור הנוכחי של מעבדים קוונטיים - עידן ה-NISQ (עידן קוונטי בקנה מידה ביניים רועש), או הזמן של טכנולוגיות תת-קוונטיות.
בעוד מדענים פועלים לשיפור הקוונטיםתהליכים, מנהלי החברה מחפשים אנלוגים מודרניים שעוזרים לייעל את עבודת הייצור. "תחליף" כזה הפך לאלגוריתמים בהשראת קוונטים שמוצאים פתרון אופטימלי של 95-99% במחשבים קונבנציונליים. ברוסיה, QuSolve עושה זאת - המשימות שהחברה עובדת עליהן שייכות למחלקת NP, ומתמטיקאים מפתחים ומשפרים אלגוריתמים לפתרון בעיות עסקיות. ב-QuSolve, כדי לבדוק את הפותר (פותר) משלהם, הם השתמשו בתגיות, שעזרו למצוא כמה שגיאות באלגוריתם ולבצע תוספות לממשק של חבילת התוכנה.
האם מדענים מודרניים באמת לא עושים דבר מלבדהאם אתה חושב על איך לשפר ולייעל הכל? ברור שלא. בזמנם הפנוי הם ממשיכים להמציא משחקים. המפתחים כבר הצליחו להפוך את רוב המשחקים ל-NP, והוסיפו מעט קסם של תופעות פיזיקליות קוונטיות.
כך הופיעו טכנולוגיות קוונטיות במהלך 10 השנים האחרונות.דמקה, קרב ים קוונטי וקוט-טק קוונטי. שחמט קוונטי זכה לפופולריות מיוחדת, שבה אפילו נערכים טורנירים, והאלוף זוכה בתואר רב-אמן. רוב "משחקי הקוונטים" החדשים בנויים על העיקרון הבסיסי של מכניקת הקוונטים - סופרפוזיציה.
לדוגמה, כלי שחמט יכולים להיות בפניםמספר מקומות על הלוח בו זמנית, מה שאומר שקשה יותר להגן ולתקוף - זה הופך את המשחק לבלתי צפוי ומרהיב. ב-2016 הם אפילו צילמו סרט קצר שהראה משחק שחמט קוונטי בין סטיבן הוקינג לפול ראד, שחקן הידוע בתפקידו כאנט-מן ביקום הקולנועי של מארוול.
צילום מסך של המשחק. כך נראה הלוח המקוון במשחק בין הוקינג לראד. ואז השחקן היכה את הפיזיקאי האגדי
אנחנו לא יודעים אם המשחקים האלה יהיו כאלה בעתידשגרתיים כמו טיק-טק רגילים, טטריס ותג, אבל הם בהחלט יעוררו למתמטיקאים ליצור אלגוריתמים ייחודיים לפתרון בעיות עסקיות מעשיות ופיתוח טכנולוגיה. אין ספק בכך.
קרא עוד:
צורת שביל החלב היא בכלל לא מה שחשבנו לאורך כל הדרך, מצאו מדענים
שני כדורי-על שנמצאו בקצה אזור המגורים: לאחד מהם טמפרטורה נוחה
מצא חור שחור שהורס תיעוד כוכב קרוב לכדור הארץ