נסיכת המדעים

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

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

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

הפרדיגמה הראשונה היא מה שאלון כינה: "Randomization -Derandomization". הרעיון הוא לתקוף בעיה דטרמיניסטית באמצעות אלגוריתם הסתברותי (כלומר, אלגוריתם הנותן תשובה נכונה לבעיה בהסתברות מסויימת, ואך יש הסתברות חיובית כי התשובה שהאלגוריתם נתן אינה נכונה). לאחר מכן, ניתן (אולי) לקחת את האלגוריתם הההסתברותי ו"לשפצר" אותו באופן שיהפוך לדטרמינסטי. הוא נתן שתי דוגמאות. דוגמא אחת היא אלגוריתם הסתברותי לקביעה האם מספר טבעי נתון הוא ראשוני או פריק, שפיתחו Agrawal ושותפיו. מספר שנים לאחר מכן, פרסמו Agrawal ושותפיו אלגוריתם דטרמינסטי יעיל לקביעת הראשוניות/פריקות של מספרים טבעיים, המבוסס על עקרונותיו של האלגוריתם ההסתברותי. אלון טוען כי הדרך לאלגוריתם הדטרמינסטי הייתה חייבת לעבור באלגוריתם ההסתברותי שקדם לא, ולא ניתן היה לבצע ישירות את הקפיצה המחשבתית אל האלגוריתם הדטרמינסטי. דוגמא נוספת שנתן אלון היא בעיה בתורת הגרפים עליה עבד עם מספר שותפים (קביעה האם גרף מכיל מסלול באורך נתון) שעברה תהליך דומה – אלגוריתם הסתברותי תחילה, ולאחר מכן אלגוריתם דטרמיניסטי שהוא שכלול של האלגוריתם ההסתברותי.

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

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

פורסם לראשונה באתר "רשימות" בתאריך 6 במאי 2008  שם התקבלו 8 תגובות

עומר  בתאריך 5/6/2008 6:06:57 PM

אם ההסתברות

היא אפס אין משמע שאין כדור אדום (באותו אופן אפשר לטעון שאין רציונליים). השיטה ההסתברותית גורסת שאם ההסתברות גדולה מאפס אז יש עצם שמקיים את הדרוש.

אלעד-וו  בתאריך 5/6/2008 7:52:46 PM

כתבת היטב

עומר: הנח שמס' הכדורים בעולם סופי.

עומר  בתאריך 5/6/2008 8:44:38 PM

אלעד-

אפילו במקרה זה – יתכנו מרחבי הסתברות שבהם למאורעות לא ריקים יש סיכוי אפס; השיטה ההסתברותית טוענת רק את הכיוון "הסתברות >0 גוררת מאורע לא ריק".

אלעד-וו  בתאריך 5/6/2008 8:54:28 PM

עומר, אתה מתקטנן

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

אלעד-וו  בתאריך 5/6/2008 8:55:19 PM

פוסט מצויין

כתבת מצויין ומדוייק.
הנה מספר תיקונים קטנים:
1. האלגוריתם הרנדומי לבדיקת ראשוניות הוא של מיכאל רבין (ישראלי, אגב) ולא של Agrawal)
2. כתבת "אלון טוען כי הדרך לאלגוריתם הד טרמינסטי הייתה חייבת לעבור באלגוריתם ההסתברותי שקדם לא, ולא ניתן היה לבצע ישירות את הקפיצה המחשבתית אל האלגוריתם הדטרמינסטי.".
הייתי מחליף את הביטויים "לא ניתן" ו"הייתה חייבת" במשהו יותר שמרני. הייתי כותב "היה מאד קשה קונספטואלית להגיע לאלגוריתם הדטרמיניסטי בלי למצוא קודם את האלגוריתם הרנדומי" או משהו בסגנון. תמיד ייתכן שמישהו ימצא ישירות את האלגוריתם הדטרמיניסטי, אבל הדרך היחידה שידועה לקבל אלדוריתם דטרמיניסטי לבעיה הזאת עברה (בראיה היסטורית) דרך האלג' הרנדומי.
3. כתבת "המטרה שלו, כפי שהבנתי מאוחר יותר, הייתה להצביע על כך שחשיבה במונחים הסתברותיים אינה טריויאלית, ויותר מכך, האינטואיציה לא תמיד "עובדת" כשדנים בהסתברות.".
לא הייתי כותב "לא תמיד עובדת". מישהו שאינו בקיא במתימטיקה יכול לחשוב שזו פילוסופיה, ושלא תמיד 1 ועוד 1 שווה 2. הייתי במקום זה אומר שכשחושבים במונחים הסתברותיים קל להתבלבל ולעשות טעויות. למשל, קל להתבלבל כשמתעסקים עם הסתברויות מותנות.
4. לבסוף, בנוגע לשיטה ההסתברותית, הבנתי למה החלפת את הדוגמה שנוגה נתן בדוגמה אחרת. (אם יותר לי לנחש, נוגה הראה חסם תחתון למספרי רמזי?). אבל הדוגמה שנתת לטעמי לא ממש קולעת — אין בה מספיק מה"אופי" של השיטה ההסתברותית. שתי דוגמאות מצויינות (אבל, כמו שאמרת, לא טריוויאליות) ניתנות במאמר וויקיפדיה שכבר קישרת אליו: http://en.wikipedia.org/wiki/Probabilistic_method
דוגמה נוספת לשימוש בשיטה ההסתברותית היא להוכיח שיש אוסף של מליון תתי קבוצות של המספרים בין 1 ל-1000
, כך שהחיתוך בין כל שתי קבוצות באוסף הוא בגודל לכל היותר 600. קשה מאד לבנות כזה אוסף, אבל קל להוכיח שקיים כזה אוסף: בוחרים את הקבוצות באקראי, ומוכיחים בעזרת יוניון-באונד שבהסתברות גדולה מאפס הוא מקיים את התכונות הנדרשות. זו דוגמה שחביבה על טימוטי גאוארס, ונידונה במאמר (הפופולרי) המעננין שלו "שתי התרבויות של המתימטיקה" שניתן לקריאה כאן:
http://www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf
תודה על הפוסט. תמיד תענוג לשמוע הרצאות של נוגה, ואפילו לשמוע על הרצאות של נוגה.

עומר  בתאריך 5/7/2008 9:21:14 AM

אלעד וו-

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

גיל  [אתר]  בתאריך 5/8/2008 8:03:51 AM

בהקשר הזה חשוב לציין

שלא רק חשיבה הסתברותית חשובה, אלא גם שהיא במקרים רבים לא אינטואטיבית לאנשים. חשוב להדגיש חשיבה הסתברותית בהקשרים רלוונטיים ולא רק מבחינה תיאורטית כי יש גורמים שונים המשפיעים על סטטיסטיקה נאיבית.

יוסי לוי  [אתר]  בתאריך 5/11/2008 7:36:57 AM

תודה לכל המגיבים עד כה

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

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

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

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

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

לכן, שמחתי כשיצא לאור לא מזמן ספרו החדש של פרופ' רון אהרוני – "מתמטיקה, שירה ויופי".

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

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

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

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

פורסם לראשונה באתר "רשימות" בתאריך 14 באפריל 2008  שם התקבלו 5 תגובות

גיא  בתאריך 4/15/2008 12:24:10 AM

אם היינו מבינים את כל היופי

החיים היו הרבה פחות מעניינים

ענת פרי  [אתר]  בתאריך 4/15/2008 10:33:06 AM

ללא נושא

הרשימה הזו מאד פיוטית, וגם מורים לספרות יכולים לטעות.

אדם  בתאריך 4/15/2008 11:48:19 AM

אינני מתמתיקאי ואינני משורר.

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

נציגת 372  בתאריך 4/15/2008 12:57:37 PM

אז…

לקרוא או לא לקרוא?
לקנות או לא לקנות?

יוסי לוי  [אתר]  בתאריך 4/15/2008 2:33:31 PM

לנציגת 372

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

פורסם לראשונה באתר "רשימות" בתאריך 18 בפברואר 2007 שם התקבלו 4 תגובות

מרזבאן  בתאריך 2/18/2007 10:33:07 PM

מבריק

מבריק ומקסים,
ובחיי, שאני לומד מתמטיקה שנה שנייה וזה היה לא טריוויאלי..

טלג  [אתר]  בתאריך 2/18/2007 11:58:25 PM

חמוד חמוד חמוד

אחלה ששיתפת, תודה יוסי

דובי  [אתר]  בתאריך 2/19/2007 8:32:18 AM

ללא נושא

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

ערן  בתאריך 2/19/2007 11:06:25 AM

יש בכלל דרך אחרת ללמוד מתמטיקה?

בעצם, איך לימדו חיסור לפני השיטה הזאת?

את הידיעה על מותו של המתמטיקאי פרופסור אמנון פזי, שהיה רקטור ונשיא האוניברסיטה העברית, שמעתי רק לפני יומיים, באיחור של כמעט שבועיים.

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

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

בתקופת נשיאותו, שינתה האוניברסיטה באופן חד צדדי ושנוי במחלוקת את מעמדם של אנשי הסגל האקדמי הזוטר – רובם ככולם תלמידי מחקר. האסיסטנטים, הלא הם דוקטורנטים שלמדו באוניברסיטה וקיבלו שכר תמורת עבודתם במשך כל השנה, נעלמו ממצבת כח האדם של האוניברסיטה. האנשים עצמם נשארו עם תואר חדש: "מורה עוזר". המשמעות לא הייתה רק סמנטית. שכרם קוצץ ב-50%, ושולם כעת רק במשך 8 חודשים. כך נשבר רצף ההעסקה, והאוניברסיטה פטרה את עצמה מתשלום פיצויי פיטורים. המחצית השניה של השכר הפכה ל"מלגת מחיה", שאכן שולמה במשך 12 חודשים, אבל האוניברסיטה חסכה את תשלומי המעביד (בעיקר תשלומים לביטוח הלאומי). כמו כן, תוספות שכר להם היו זכאים האסיסטנטים, כגון תשלום עבור ימי חופשה, דמי הבראה והוצאות נסיעה, "הפכו" לפתע לחלק משכר היסוד, שכזכור קוצץ ב-50%. בסך הכל הקיצוץ האפקטיבי בשכר הסגל הזוטר היה מעל ל-20%. גרוע מכך – בעוד שהביטוח הלאומי אכן לא ראה במלגה (ששולמה רק לאנשי הסגל הזוטר, ולא לכל הדוקטורנטים) שכר, מס הכנסה כן דרש ממקבלי המלגה תשלום מס, בטענה (הנכונה לכשעצמה) כי זהו שכר לכל דבר. כמה כסף חסך התרגיל לאוניברסיטה? איני יודע, אבל לדעתי הפגיעה הייתה מיותרת והנזק לטווח ארוך שנגרם על ידי הפגיעה במחקר עלה על התועלת. אני יכול לומר בבטחון מלא כי לו פנתה האוניברסיטה אל נציגי הסגל הזוטר ובקשה מהם להשתתף במאמץ להצלת האוניברסיטה, הפניה הייתה נענית ברצון. אני יודע זאת כי הייתי חבר בוועד המורים העוזרים שניסה (לשוא) לנהל משא ומתן עם האוניברסיטה על תנאי ההעסקה המפלים האלה. לבסוף נאלצנו לתבוע את האוניברסיטה בבית הדין לעבודה, ורק אז נכנעה האוניברסיטה, ובהסכם פשרה שילמה לכל אחד מ-800 חברי הסגל הזוטר כמה אלפי שקלים ובסך הכל קרוב ל-3 מליון ש"ח. האם התרגיל הזה היה שווה לאוניברסיטה? מבחינה כספית אולי כן, אבל לא מכל בחינה אחרת.

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

פרופ' אחר לכלכלה מניו-אינגלנד (שעבר לפני מספר שנים לניו-יורק) הוא ג'פרי זקס (שמו נכתב בד"כ סאקס, משום מה). לא חתן פרס נובל (עדיין), אבל ללא ספק נמנה עם השורה הראשונה של הכלכלנים בעולם. האם דמותו של בארטלט מבוססת במידת מה על דמותו של זקס? שאלה נחמדה, אבל לא ממש חשובה. שאלה הרבה יותר מעניינת וחשובה היא האם זקס יכול להיות המימוש של בארטלט. יש אנשים שחושבים שכן, ומנהלים קמפיין נמרץ כדי… לשכנע את פרופ' זקס להציג את מועמדותו. האם יצליחו, ואם כן, האם ייבחר זקס לנשיא? ימים יגידו. אני מקווה רק שיספיק לזכות בפרס נובל לפני שייכנס לפוליטיקה.

פורסם לראשונה באתר "רשימות" בתאריך 31 באוגוסט 2006 שם התקבלו 4 תגובות

סקרנית  בתאריך 9/2/2006 1:21:21 PM

שאלה

מהפוסטים שלך עולה אצלי רושם שאתה יחסית צעיר, באמת התחלת ללמוד בעברית ב84'?

יוסי לוי  [אתר]  בתאריך 9/3/2006 8:32:37 AM

תשובה לסקרנית

כן. ותודה על המחמאה, בכל אופן.

עומר  בתאריך 9/3/2006 12:20:16 PM

למדתי את הקורס

באינפי מתקדם עם אמנון פזי. ליתר דיוק – פזי לימד את הקורס בזמן שלקחתי אותו. אני, כדרכי בתואר הראשון (וגם השני), לא ממש הייתי נוכח בכיתה. אבל זכורה לי אמרה אחת של פרופ' פזי (עליה שמעתי מאחד הפרופ' שהיו מעורבים בעניין שלהלן): באותה שנה ממוצע הקורס הנ"ל היה גבוה משמעותית מאשר בשנים הקודמות. כאשר פנה יו"ר החוג דאז לפרופ' פזי לקבלת הסבר הוא ענה:"איני מבין מה הבעיה. סוף סוף התלמידים למדו והצליחו!". איני יודע אם הצלחנו כי המבחן היה קל יותר, אך אותו מחזור אכן הניב מספר שנים לאחר מכן את אחד ה"יבולים" המוצלחים ביותר של תלמידי מוסמך בחוג למתמטיקה בשנים האחרונות (כפי שטען יו"ר החוג דאז).
בהחלט יתכן כי כל פרופ' אחר היה מנסה להתגונן. תגובתו הטבעית של פרופ' פזי היתה תמיכה בתלמידיו!
(נ.ב. – יוסי, בשנים האחרונות הורע מצבן של המחלקות השונות באונ' העברית, ובינהן המחלקה למתמטיקה, עקב קיצוצי תקציב המוסדות והשתת מרבית הקיצוץ על תקציבי החוגים. דווקא בשנתיים שעברו, מצא לנכון החוג למתמטיקה לשתף את תלמידי המחקר בשיקולים השונים, ויחד הצלחנו למצוא פתרונות לבעיות הכלכליות ללא פגיעה בסגל הזוטר. אולי דברים כן משתנים בסופו של דבר…).

שי  בתאריך 10/13/2006 7:44:15 PM

ללא נושא

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

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

השעשוע של אוילר הפך לכלי שימושי בסטטיסטיקה המודרנית

בבעיה הזאת התחבט ליאונרד אוילר, מתמטיקאי שוויצרי, בשנת 1779. אוילר אמנם התעניין בבעיה כדי לשעשע את עצמו, אך משלא הצליח לפתור אותה החליט לתקוף אותה ביתר רצינות. ארבע שנים לפני מותו הובילה אותו בעיית הקצינים למחקר של יצור מתמטי חדש – הריבוע הלטיני.

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

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

הכימאי ממבשלת הבירה הניח את היסודות לענף מרכזי בסטטיסטיקה

ויליאם גוסט (Gosset), מחלוצי הסטטיסטיקה, היה כימאי שעבר לפרנסתו במבשלות הבירה של גינס. אחד מתפקידיו היה למצוא דרכים לשיפור כמות ואיכות השעורה שגודלה עבור מפעלי הבירה. גוסט התבקש לבחון חמישה סוגי דשן שהוצעו לשימוש בגידול השעורה. פתרון פשטני לבעיה הוא לבחור חמישה שדות, ובכל שדה לנסות סוג אחר של דשן. ניסוי כזה הוא בעייתי. אם יהיו הבדלים ביבולים השונים, לא יהיה אפשר להסיק בודאות כי ההבדלים נגרמו על ידי הדשנים. בשדות שונים יש תנאי גידול שונים: אדמה, אקלים מזיקים, כל אלה יכולים להשפיע על גידול השעורה. הניסוי חייב להיות מבוקר: כל תנאי הגידול, פרט לסוג הדשן, חייבים להיות זהים במידת האפשר. הפתרון של גוסט היה לבחור שדה ריבועי, ולחלק אותו ל-25 ריבועים קטנים. בכל אחד מחלקי הריבוע נעשה שימוש בדשן אחר, כך שבכל שורה ובכל עמודה נעשה שימוש בכל סוגי הדשן. אם נסמן את סוגי הדשן ב-A, B, C, D, ו-E, השדה של גוסט נראה בערך כך:

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

פורסם לראשונה באתר "רשימות" בתאריך  17 ביוני 2005 שם התקבלה שם התקבלה שם התקבלו9 תגובות

סודוקון  בתאריך 6/18/2005 12:00:01 AM

שאלה ליוסי

האם יש אלגוריתם כללי לפתרון בעיות סודוקו (כלומר, האם הבעיה כריעה)?
אם כן, האם ידוע אלגוריתם יעיל? (פולינומיאלי בזמן ריצה)

אבנר  בתאריך 6/18/2005 8:36:20 AM

התנאי היותר מורכב של ריבוע לטיני

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

יוסי  [אתר]  בתאריך 6/18/2005 1:22:21 PM

תשובה לסודוקון

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

יוסי  [אתר]  בתאריך 6/18/2005 1:25:03 PM

תשובה לאבנר

התנאי שציינת יכול להתקיים בכל ריבוע לטיני מסדר זוגי, ואינו יכול להתקיים בריבוע לטיני מסדר אי זוגי.

  בתאריך 6/19/2005 12:00:23 AM

ישנה הוכחה מסודרת יותר

ישנה הוכחה מסודרת יותר להיות הבעיה של הסודוקו NP-שלמה (כל הבעיות בP הן בNP זה לא עוזר לי כלום לדעת שהיא בNP השאלה היא אם היא NP שלמה או בP)
אפשר למצוא במאמר מסויים של סינים.

יוסי לוי  [אתר]  בתאריך 6/19/2005 7:40:44 AM

תשובה למגיב הקודם

תודה על ההערה הנכונה

הראל  בתאריך 7/5/2005 12:14:56 PM

לאונדר פולר, ידיהוט אחרונוט

בספרון שהוצאת ידיעות אחרונות הוציאה ונקרא משהו כמו "נפלאות הסודוקו", כתוב בהקדמה שהסודוקו הומצא תחת השם "משבצות לטיניות" על ידי מתמטיקאי שוויצרי משועמם בשם לאונרד פולר.
ידיעות אחרונות כבר קראתם??

הראל  בתאריך 7/5/2005 12:16:11 PM

NP-C

בערך האנגלי על סודוקו בויקיפדיה תמצאו קישור למאמר שמוכיח כי הבעייה היא NP שלמה.

ג. יפית  בתאריך 8/31/2005 11:47:37 AM

גם חבר שלך כותב פה על סודוקו

http://www.notes.co.il/ben-hateva/12445.asp
אבל עם כל הצרה נשגבה ממני הדרך שהוא הרכיב שם את המשחק. די מבולבל מה שהוא עשה שמה.