ג'ון הופקרופט: ספר הלימוד שהכשיר תחום
מיליוני סטודנטים למדעי המחשב מעולם לא קראו מילה שג'ון הופקרופט כתב בכתב עת מחקרי, ובכל זאת כמעט כולם למדו ממנו בכל זאת – דרך ספרי הלימוד על תורת האוטומטים ואלגוריתמים הנושאים את שמו לצד ג'פרי אולמן (Jeffrey Ullman) ואלפרד אהו (Alfred Aho), ספרים שאומצו ביסודיות כתוכנית לימודים סטנדרטית עד שעיצבו את האופן שבו הדיסציפלינה מלמדת את עצמה.
מבנו של שרת לסטנפורד
ג'ון אדוארד הופקרופט נולד ב-7 באוקטובר 1939, בסיאטל, וושינגטון, למשפחה ממעמד הפועלים; אביו, וטרן בריטי ממלחמת העולם הראשונה, עבד כשרת, ואף אחד מהוריו לא סיים תיכון. הוא היה גם נכדו של ג'ייקוב ניסט (Jacob Nist), מייסד חברת Seattle-Tacoma Box. למרות השכלתם המוגבלת, הוריו עודדו את סקרנותו האינטלקטואלית, והוא קיבל תואר ראשון בהנדסת חשמל מאוניברסיטת סיאטל ב-1961, ואחריו תואר שני ב-1962 ודוקטורט ב-1964, שניהם בהנדסת חשמל, מאוניברסיטת סטנפורד. הכשרה הנדסית זו, ולא רקע במתמטיקה טהורה או במדעי המחשב, עיצבה את האינסטינקט המאוחר שלו לאלגוריתמים שלא היו רק אלגנטיים תאורטית אלא יעילים באמת להרצה.
בניית ספרי הלימוד של הדיסציפלינה
הופקרופט החל את הקריירה האקדמית שלו באוניברסיטת פרינסטון כפרופסור עוזר לפני שעבר לאוניברסיטת קורנל, שם בילה את רוב הקריירה שלו, כשהוא מחזיק בתואר פרופסור להנדסה ומתמטיקה שימושית של IBM וממלא תפקידי מנהיגות כולל ראש מחלקה ודיקן הנדסה. בקורנל הוא כתב בשיתוף, עם ג'פרי אולמן ומאוחר יותר אלפרד אהו, סדרה של ספרי לימוד על שפות פורמליות, תורת האוטומטים ותכנון אלגוריתמים שהפכו לטקסטים הלימודיים המוגדרים עבור דורות של סטודנטים למדעי המחשב ברחבי העולם. ספרים אלו עשו יותר מאשר לסכם ידע קיים – הם קידדו ניתוח סיבוכיות אסימפטוטית ותורת השפות הפורמליות לצורה שנלמדת עדיין בקורסי תאוריה מבואיים כיום, והעניקו לתחום אוצר מילים משותף לפני שאוצר מילים זה היה קיים במלואו במקום אחר.
אלגוריתמים שעדיין רצים כיום
מעבר לספרי הלימוד, המחקר של הופקרופט עצמו הפיק כלים שנמצאים עדיין בשימוש פעיל. אלגוריתם הופקרופט-קארפ (Hopcroft-Karp), שפותח עם ריצ'רד קארפ (Richard Karp), מוצא שידוכים מקסימליים בגרפים דו-צדדיים מהר יותר מכל שיטה שקדמה לו, ונשאר טכניקה סטנדרטית בבעיות זרימה ברשתות ושיבוץ. הוא גם פיתח אלגוריתם יעיל למיזעור אוטומטים סופיים דטרמיניסטיים, כלי יסודי בתכנון מהדרים ואימות פורמלי. התוצאה המפורסמת ביותר שלו, לעומת זאת, הייתה עבודה משותפת עם רוברט טארג'ן (Robert Tarjan): האלגוריתם הראשון בזמן ליניארי לבדיקה אם גרף הוא מישורי – האם ניתן לצייר אותו על משטח שטוח ללא הצטלבות קשתות – שפורסם ב-1974. השניים בנו את האלגוריתם סביב שימוש שיטתי בחיפוש לעומק (depth-first search), והפכו את מה שהיה בעיה איטית ואד-הוק לבעיה הניתנת לפתרון בזמן פרופורציונלי לגודל הגרף עצמו.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →פרס טיורינג ואופיו המשותף
בשנת 1986, הופקרופט וטארג'ן קיבלו במשותף את פרס טיורינג של ה-ACM, הכבוד הגבוה ביותר במחשוב, "על הישגים יסודיים בתכנון וניתוח של אלגוריתמים ומבני נתונים". הציטוט מציין את שני הגברים יחד ומייחס גוף של עבודה שיתופית ומקבילה ולא פריצת דרך אינדיבידואלית אחת – אלגוריתם המישוריות הוא העיקרי מבין ההישגים שהציטוט התכוון אליהם, לצד תרומותיו העצמאיות של כל אדם לתחום הרחב יותר של תכנון אלגוריתמים.
קריירה שנייה בסין
בעשורים שלאחר פרס טיורינג שלו, הופקרופט הפנה חלק ניכר מהאנרגיה שלו לחיזוק החינוך למדעי המחשב מחוץ לארצות הברית, במיוחד בסין. הוא הפך למנהל משותף של המרכז לחזיתות לימודי המחשוב באוניברסיטת פקינג ומוביל מרכזים הנושאים את שמו באוניברסיטת שנגחאי ג'יאו טונג ובאוניברסיטת הואז'ונג למדע וטכנולוגיה, חונך סטודנטים ועוזר לבנות תוכניות מחקר באלגוריתמים, ולאחרונה, בלמידה עמוקה. סין העניקה לו את פרס הידידות שלה ב-2016, הכרה השמורה למומחים זרים שתרמו תרומות יוצאות דופן לפיתוח המדינה – מערכה שנייה יוצאת דופן עבור חתן פרס טיורינג שכבר עשורים עברו מאז העבודה שזיכתה אותו בפרס.
הכרה
הופקרופט נבחר לאקדמיה הלאומית להנדסה ב-1989, הפך לעמית ACM ב-1994, וקיבל את מדליית ג'ון פון נוימן של ה-IEEE ב-2010 על הישגים יוצאי דופן במדעי המחשב והנדסה, בנוסף לפרס טיורינג ב-1986 ופרס הידידות הסיני ב-2016.
מדוע ג'ון מכונה גאון
הטיעון לגאונותו של הופקרופט אינו נשען על הוכחה מסנוורת אחת אלא על שילוב נדיר יותר: תרומות מחקריות משמעותיות מספיק כדי לזכות בפרס הגבוה ביותר בתחום, בשילוב עם כישרון שאין שני לו לזקק את יסודות התחום לצורה ניתנת להוראה. אלגוריתם המישוריות ואלגוריתם השידוך של הופקרופט-קארפ הם סוג התוצאות שמדעני מחשב תאורטיים מצביעים עליהן כחכמות באמת – צמצום בעיות שנראו כדורשות חיפוש בכוח גס לזמן ליניארי או כמעט ליניארי באמצעות תובנה מבנית. אבל הניסוח הכנה, שציטוט פרס טיורינג עצמו מבהיר, הוא שהתוצאה המפורסמת ביותר שלו שייכת במשותף לו ולרוברט טארג'ן; הציטוט של אף אחד מהם לא עומד לבדו, והפרס היה על גוף הישגים משותף, לא פריצת דרך של אדם יחיד. מה שפחות משותף, ופחות נחגג כ"גאונות", הוא הכישרון השני שלו: שלושה ספרי לימוד נפרדים שנכתבו בשיתוף, בנויים כל כך טוב שהם הפכו לדרך המוגדרת שבה דיסציפלינה שלמה מלמדת את עצמה את יסודותיה, צורה של תרומה אינטלקטואלית הקרובה יותר להוראת אמן מאשר להמצאה אינדיבידואלית.
מורשת
מורשתו של הופקרופט נעה בשני מסלולים מקבילים שלעיתים רחוקות מצטלבים בקריירה אחת – שיא מחקרי זוכה פרס טיורינג באלגוריתמים, ומערכה שנייה של עשורים בבניית תשתית לחינוך למדעי המחשב בסין. מעט דמויות בהיסטוריה של התחום עיצבו את האופן שבו הוא נלמד בצורה ישירה כל כך, או למשך זמן רב כל כך, כמו מחבר ספרי הלימוד המוקצים ביותר שלו. העובדה שהאדם שעזר למסד את תורת החישוב בשנות ה-60 וה-70 היה, עד שנות ה-2010, חונך סטודנטים בלמידה עמוקה באוניברסיטת פקינג אומרת משהו על האורך והטווח הבלתי רגילים של חיי העבודה שלו: קריירה שהחלה בעידן הנדסת החשמל של שפופרות הריק ונמשכה לעידן הרשתות העצביות, מבלי לאבד מעולם את הקו המנחה של הוראת הדור הבא את המבנה הבסיסי של התחום.