רוברט טארג'ן: הדקדוק של אלגוריתמים יעילים
בקשו מכל סטודנט למדעי המחשב לעקוב אחר גרף עם חיפוש לעומק (depth-first search) והם, בין אם הם יודעים זאת ובין אם לא, מריצים טכניקה שרוברט טארג'ן הפך מסקרנות למשמעת. המאמר שלו מ-1972 "חיפוש לעומק ואלגוריתמים של גרפים ליניאריים" נקרא כיום כמו ספר דקדוק בסיסי – סוג העבודה שנספג כל כך ביסודיות בתחום עד ששמו של מחברו כמעט נעלם מהאופן שבו אנשים מדברים עליו, גם כששמו נקשר לחצי תריסר מהמבנים שהם משתמשים בהם בכל יום.
מסלולו של מתמטיקאי לתוך מכונות
רוברט אנדרה טארג'ן נולד ב-30 באפריל 1948, בפומונה, קליפורניה, לג'ורג' טארג'ן, פסיכיאטר ילדים המתמחה במוגבלות שכלית; אחיו הצעיר ג'יימס הפך לרב-אמן בשחמט. טארג'ן רצה להיות אסטרונום כילד, עד שטורי הפאזלים של מרטין גרדנר ב-Scientific American ומורה מעורר השראה בכיתה ח' משכו אותו לעבר מתמטיקה במקום. הוא קיבל תואר ראשון במתמטיקה מ-Caltech ב-1969, ואז הלך לסטנפורד לתואר שני במדעי המחשב ב-1971 ודוקטורט ב-1972, עם עבודת גמר על אלגוריתמים של מישוריות בהנחיית רוברט פלויד ודונלד קנות'. הוא יתאר מאוחר יותר את בחירת התחום שלו בפשטות: מדעי המחשב היו דרך לעשות מתמטיקה שיכולה להיות לה השפעה מעשית – משפט שמשמש גם כתיאור של כל גוף עבודתו.
בניית ארגז הכלים
הקריירה של טארג'ן, המשתרעת על פני קורנל, UC ברקלי, סטנפורד, AT&T Bell Labs, NYU, מכון המחקר NEC, Microsoft Research, Compaq, Hewlett Packard ו-Intertrust Technologies לפני שהשתקע בפרינסטון ב-1985 כפרופסור מכובד של ג'יימס ס. מקדונל, הפיקה גוף של אלגוריתמים ומבני נתונים יוצאי דופן בכך שרבים מהם הפכו לתשתית נושאת עומס ולא לסקרנויות תיאורטיות. שמו נקשר לאלגוריתם של טארג'ן למציאת רכיבים קשורים חזק בגרף, אלגוריתם לא מקוון לחישוב אבות קדמונים משותפים, ואלגוריתם בזמן ליניארי למציאת גשרים – כל הטכניקות בנויות על מסגרת החיפוש לעומק שהוא פורמליז. ב-1975 הוא נתן את הניתוח המדויק הראשון של מבנה הנתונים union-find בשילוב עם דחיסת נתיבים, והוכיח את זמן הריצה המופחת כמעט קבוע שלו באמצעות פונקציית אקרמן ההפוכה, תוצאה כל כך קשורה לביצועים בעולם האמיתי שהיא עומדת כיום בבסיס הכל, מאלגוריתם עץ הפריסה המינימלי של קרוסקל ועד אופטימיזציות של מהדרים. עם דניאל סליטור ב-Bell Labs הוא המציא יחד עצי splay, עצי חיפוש בינאריים מתכווננים עצמית שמאזנים את עצמם באמצעות שימוש במקום לשאת מטא-נתונים של איזון מפורש, ואיתם חלוץ בניתוח תחרותי, מסגרת לשיפוט אלגוריתמים מקוונים מול יריב יודע כל. עם מייקל פרדמן הוא פיתח ערימות פיבונאצ'י ב-1985, מבנה תור עדיפויות שהפך את אלגוריתם המסלול הקצר ביותר של דייקסטרה ואלגוריתמי אופטימיזציית רשת למהירים אסימפטוטית מכל מה שבא לפני כן. ספר הלימוד שלו, Data Structures and Network Algorithms, זכה בפרס פרדריק ו. לנקסטר והפך לקריאת חובה בתחום.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →פריצת הדרך במישוריות עם הופקרופט
ההישג היחיד שזוכה להכרה מפורשת בציטוט פרס טיורינג שלו הוא עבודה משותפת עם ג'ון הופקרופט: האלגוריתם הראשון בזמן ליניארי לבדיקה אם ניתן לצייר גרף על מישור ללא הצטלבות קצוות, שפורסם ב-1974. בדיקת מישוריות הייתה בעיה איטית ומסורבלת לפני שהאלגוריתם שלהם צמצם אותה לעניין של מעבר זהיר לעומק – טכניקה כל כך מרכזית לפתרון שלהם שהפורמליזציה המוקדמת של טארג'ן לחיפוש לעומק הפכה, בדיעבד, לכלי שאפשר את תוצאת הופקרופט-טארג'ן. השניים חלקו את פרס טיורינג של ACM לשנת 1986 "על הישגים בסיסיים בתכנון וניתוח של אלגוריתמים ומבני נתונים", ציטוט שנותן קרדיט לגוף של עבודה משותפת ומקבילה ולא לאף מאמר בודד.
הכרה לאורך ארבעה עשורים
טארג'ן היה הזוכה הראשון בפרס נבנלינה במדעי המידע ב-1983, המכבד תרומות יוצאות דופן להיבטים מתמטיים של מדעי המחשב. הוא זכה בפרס טיורינג ב-1986, נבחר לאקדמיה האמריקאית לאמנויות ומדעים ב-1985, לאקדמיה הלאומית למדעים ב-1987, ולאקדמיה הלאומית להנדסה ב-1988. הוא קיבל את פרס פריס קנלאקיס בתיאוריה ובפרקטיקה ב-1999 ואת פרס הבוגרים המכובדים של Caltech ב-2010. שיא הפרסומים שלו עובר את ה-250 מאמרים עם ספירות ציטוטים בעשרות אלפים, והוא מחזיק ביותר מתריסר פטנטים אמריקאיים במבני נתונים ואבטחה, המשקפים קריירה שנעתה בצורה זורמת בין תיאוריה אקדמית בפרינסטון למחקר יישומי במעבדות תעשייתיות כמו Bell Labs, NEC ומיקרוסופט.
מדוע רוברט מכונה גאון
המקרה של טארג'ן למילה נשען על משהו ספציפי: הוא לא רק פתר בעיות קשות בודדות, הוא זיהה את המכונות הקומבינטוריות הבסיסיות – חיפוש לעומק, ניתוח מופחת, התאמה עצמית – שהפכו מחלקות שלמות של אלגוריתמים איטיים בעבר למהירים, והוא עשה זאת שוב ושוב לאורך ארבעה עשורים ולא פעם אחת. הניתוח של union-find ואלגוריתם המישוריות של הופקרופט-טארג'ן נותרו חומר לימוד בדיוק משום שהם לא טריקים חכמים אלא טכניקות כלליות שחוקרים אחרים יכלו לעשות בהן שימוש חוזר; שימוש חוזר זה, יותר מכל תוצאה בודדת, הוא מה שוועדות פרס נבנלינה ופרס טיורינג תגמלו. הסיבוך הכנה הוא שהתוצאה המפורסמת ביותר שלו, אלגוריתם המישוריות בזמן ליניארי, היא עבודה משותפת במפורש עם ג'ון הופקרופט, וציטוט פרס טיורינג נותן קרדיט לשני הגברים במשותף במקום להכתיר את אחד מהם כגאון סולו – הפרס עצמו הוא הוכחה שהתחום רואה בכך הישג שיתופי, לא המצאה יחידה. התוצאות הבולטות האחרות של טארג'ן נבנו באופן דומה עם מחברים שותפים בעלי שם: עצי splay עם דניאל סליטור, ערימות פיבונאצ'י עם מייקל פרדמן. מה שלא שנוי במחלוקת הוא הצפיפות העצומה של תוצאות בסיסיות שנלמדות עדיין הנושאות את שמו, שיא שמעטים בתחום השתוו לו.
מורשת
כל סטודנט למדעי המחשב שלומד חיפוש לעומק, union-find, עצי splay או ערימות פיבונאצ'י, למעשה, עדיין נלמד על ידי המאמרים של טארג'ן, עשורים לאחר שנכתבו. עבודתו יושבת מתחת למהדרים, ניתוב רשתות ומערכות מידע גיאוגרפיות מבלי שרוב המשתמשים בה ידעו את שמו – הגורל השקט של מתמטיקה ברמת תשתית שהצליחה לחלוטין. הוא המשיך להפיק תוצאות חדשות היטב לתוך שנות השבעים לחייו, נע בין הסגל של פרינסטון לתפקידים כמדען ראשי ב-Intertrust Technologies וחוקר במיקרוסופט ו-Hewlett Packard, צורת קריירה שבעצמה טוענת נגד התייחסות אליו כאל דמות אקדמית גרידא: חלק גדול מעבודתו המצוטטת ביותר נעשתה, נבדקה ויושמה בתוך מעבדות מחקר תעשייתיות ולא בריק אקדמי. חיים כפולים אלה, פרסום מתמטיקה קפדנית תוך פטנט על מערכות מעשיות, הם חלק ממה שמפריד את השיא שלו מתיאורטיקנים שרעיונותיהם נותרו כלואים בכתבי עת.