בתשובה להאייל השואל, 22/09/05 16:03
 |
|
 |
||
|
||||
 |
"סיעור מוחות" הוא טכניקה שאני מכיר (אם כי בעוונותי אף פעם לא הייתי חסיד גדול שלה). גם בעצומו של סיעור כזה, הרעיונות הפרועים שמועלים הם בתוך מערכת מוסכמת של חוקים וידע על העולם. אני לא צופה עתיד ורוד לאף מתכנת שיציע ברצינות הצעות פרועות ממש אפילו אם אינן עומדות בסתירה מתמטית למה שידוע - למשל מישהו שיציע לבסס את עתיד החברה על אלגוריתם שמניח p=np. לדעתי הפרטית, היכולת להכניס את עצמך למצב של הקשבה אמיתית לשטויות הוא בזבוז זמן. היכולת להבחין בין מה שראוי להקדיש לו מחשבה לבין שטויות היא באמת תכונה חשובה למנהל. האתיקה של גילוי נאות מחייבת אותי להוסיף שאינני מתכנן/מנהל טוב. |
 |
 |
 |
|
|
|
||
|
||||
|
א. ואני חשבתי שעזבנו את הדיון ההוא. בסה"כ הסברתי איפה הייתה הטעות שלי ועפ"י איזו דרך הראש שלי עובד ולמה. אני חושב שבצורה מסויימת אפילו טענתי שטעיתי שניסיתי ללכת בדרך הזו כאן באייל. ב. זה נכון ולא נכון. השאלה היא כמובן מה אתה מגדיר כשטות. p=np זו אולי שטות גמורה, ובשבילך מן הסתם גם חלומות נבואיים. אבל אני דיברתי על משהו אחר וגם הסברתי אותו. בסיעור מוחות איכותי, עם אנשים מוכשרים ופתוחים, לא יעלה בכלל רעיון של p=np. נקודת ההנחה היא שאנשים לא מעלים סתם רעיונות. מצד שני - בסיעור מוחות לא מדובר על חקר האמת.1 בכלל, זה לא שחור ולבן. יש גם רעיונות שלא נעביר עליהם שעה. תמיד צריך להיות מישהו *אחראי* שמחליט, ובסופו של דבר גם עוצר את הדיון. הרי אחרי המון רעיונות אפשר להמשיך גם עד אין סוף. יש מן הסתם עוד המון שיטות. ____________ 1 שזה שוב דרך להסביר את הטעות שלי. יש הבדל בין חשיבה המצאתית, לבין חקר האמת. אנשים רגילים הרי שיש רק אמת אחת (אם זה נכון או לא זו כבר שאלה פילוסופית), ומצד שני - פתרונות יש הרבה. |
|
|
|
|
|
|
||
|
||||
|
מה אם n=1 ? _____________ ברקת, 3 יחידות מתימטיקה פלוס העתקה בבגרות. |
|
|
|
|
|
|
||
|
||||
|
הא! כבר סיפרו באייל את הבדיחה הזאת. בדיחות שמספרים יותר מפעם אחת, חובה להרוס :) NP זה שם של אובייקט אחד ולא כפל בין שני אובייקטים. P ו-NP הן מחלקות ולא מספרים. להלן קצרקורס-מזורז-רצח: הסבר בעיית P=?=NP ב-30 שניות (מהזיכרון ועם נסיון להמנע מהגדרות פורמליות): P היא מחלקת1 השפות2 המתקבלות3 ע"י מכונות טיורינג4 דטרמיניסטיות5 בזמן פולינומיאלי6. NP היא מחלקת השפות המתקבלות ע"י מכונות טיורינג לא-דטרמיניסטיות7 בזמן פולינומיאלי. ניסוח הבעיה: אנחנו יודעים ש-P מוכלת ב-NP (כל שפה ב-P היא גם ב-NP). אנחנו לא יודעים להראות (או להפריך) ש-NP מוכלת ב-P ולכן איננו יודעים בודאות אם הן שוות או שונות. הרוב סבור שהטענה ש-P=/=NP היא הסבירה מבין שתי האופציות, אבל אף אחד עדיין לא הוכיח או הפריך את אחת משתי האפשרויות. למה זה טוב, איך זה קשור לאלגוריתמים/מחשבים, למה אנשים נוטים להאמין באפשרות אחת על פני השניה ואת מי זה פריקינג מעניין? בקצרקורס-מזורז-רצח הבא. ______ 1 מחלקה זו מן קבוצה גדולה שכזו. 2 שפה זה אוסף של מילים הכתובות באיזה א"ב סופי. 3 "שפה שמתקבלת ע"י מ"ט M" זה אוסף של מילים כך שעבור כל מילה המכונה M תעצור ותקבל אותה (ז'תומרת המכונה תעצור ותגיד לנו "חביבי, המילה שנתת לי היא בסדר היא"). 4 מ"ט זה בסה"כ מן מחשב פרימיטיבסקי שכל מה שיש לו זה אוסף סופי של מצבים וזיכרון (סרט עליו הוא יכול לכתוב ולקרוא). 5 דטרמניסטית משום שבהינתן רגע נתון במהלך החישוב בו "מצב המכונה+האות עליה מביטה המכונה" (בקיצור: קונפיגורציה) בו היא נמצאת - תמיד מוגדר לה מה היא צריכה בדיוק לעשות והיא תמיד עושה בדיוק את זה (במילים אחרות: יש לה פונקציית מעבר דטרמניסטית). 6 ז"א בזמן החסום ע"י פולינום כלשהו. או במילים פשוטות: מהר יחסית (בניגוד לריצה בזמן אקספוננציאלי). 7 מכונה נוירוטית שיכולה "לנחש" במהלך החישוב, בהיותה בקונפיגורציה מסוימת, לאיזה מצב מתחשמק לה לקפץ לפני ביצוע צעד החישוב הבא. מילה מסוימת מתקבלת ע"י מכונה כזאת אם קיימת סידרה *כלשהי* של צעדים/ניחושים שיובילו את המכונה מהמצב ההתחלתי אל המצב המקבל. השפה המתקבלת היא אוסף כל המילים המתקבלות ע"י המכונה הזאת. על פניו נראה כאילו מ"ט כאלה הן הרבה יותר מהירות ממכונות "רגילות" (דטרמניסטיות). |
|
|
|
|
|
|
||
|
||||
|
ב-3 צריך להיות "שעבור כל מילה *בשפה*, המכונה M...". | |
|
|
|
|
|
||
|
||||
|
לדעתי, בקצרקורס-מזורז-רצחים עדיף להשתמש בהגדרה אחרת ל־P ו¯NP (שקולה): P היא קבוצת הבעיות שניתן למצוא להן פתרון ביעילות (בזמן פולינומי). NP היא קבוצת הבעיות שניתן לוודא ביעילות האם משהו הוא פתרון שלהן או סתם קשקוש. בהצגה הזאת, כל בר דעת מבין ש־NP הרבה יותר גדולה מ־P, וקולט את התסכול של מדעני המחשב שכבר 40 שנה לא מצליחים להוכיח כזה דבר ברור. |
|
|
|
|
|
|
||
|
||||
|
אכן, גם אני אוהב יותר את הפשטות שבההגדרה הזאת של NP, אם כי אני לא שותף להרגשה שנביעת גודלה של NP מכך זה "כזה דבר ברור" (אם כי אני לא בטוח שבר דעת אנוכי). אבל אולי כדאי לחזור לנושא הדיון המעניין, לפני ששדמי יצוץ פה ויוכיח ש-NP מוכלת *ממש* ב-P, באמצעות מ"ט בעלת קבוצת מצבים מלאה. |
|
|
|
|
|
|
||
|
||||
|
הערה לגבי 1: במקרה הזה "מחלקה" היא באמת קבוצה (שלא כמו "מחלקת כל הקבוצות", למשל). היא אפילו די קטנה. העוצמה שלה היא א_0. | |
|
|
|
|
|
||
|
||||
|
וואלה. | |
|
|
|
|
|
||
|
||||
|
פשששששי... אתה מנסה להחזיר לי על הפעם ההיא שניסיתי להסביר לך מה זה פוסט מודרניזם? :-) | |
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |