סיפורו של ג'ורג' דנציג

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

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



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

ג'ורג' דנציג בצעירותו

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

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

התזה של ג'ורג' דנציג התבססה על שני הפתרונות והוא יכול היה להגיש אותה כבר ב-1941, אלא שאז נכנסה ארצות הברית למלחמת העולם השנייה ודנציג החליט לסייע למאמץ המלחמתי. הוא שימש במהלך המלחמה כסטטיסטיקאי עבור חיל האוויר. כעבור חמש שנים חזר דנציג לברקלי והגיש את עבודת הדוקטורט. לאחר מכן פנה לעבוד עבור משרד ההגנה ושם פיתח ב-1947 את שיטת הסימפלקס לפתרון בעיות אופטימיזציה, שיטה שהקנתה לו את פרסומו. בשיטה זו ניתן לפתור בעיות של תכנות לינארי - מציאת מקסימום לביטוי לינארי מוגדר תחת אילוצים לינאריים. ביטוי לינארי מכיל רק קבועים ומשתנים בחזקה ראשונה, למשל 5x+4y, והאילוצים יכולים להופיע בבעיה כשוויונות או כאי-שוויונות. האלגוריתם של דנציג הוא אחד החשובים במדעי המחשב והוא משמש באופן נרחב ביותר עד ימינו אלו. רבים סבורים כי ועדת פרס נובל טעתה כשלא הכלילה אותו עם מקבלי הפרס בכלכלה בשנת 1975 שניתן לחלוצי התכנות הלינארי. אגב, הייחוד בשיטה של דנציג לפתרון הבעיה הוא הגישה ההנדסית - ייתכן שאלפי הבעיות שהוא פתר בילדותו עזרו לו לחשוב בכיוון זה. דנציג בילה שנים רבות באקדמיה: ב-1960 הוא קיבל משרת פרופסור בברקלי וכעבור שש שנים עבר לאוניברסיטת סטנפורד שבה נשאר עשרות שנים. הוא נפטר בשיבה טובה בשנת 2005.

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

לקריאה נוספת:
האם דמותו של וויל האנטינג מבוססת על חייו של ויליאם סיידיס? - ויליאם סיידיס (William Sidis) הוא גאון אמריקאי שחי במחצית הראשונה של המאה העשרים.
מאמר אודות ג'ורג' דנציג (pdf)