הדיפלומה בהנדסת חשמל שקיבל מיכאליס ינאקאקיס (Mihalis Yannakakis) מהאוניברסיטה הטכנית הלאומית של אתונה בשנת 1975 סימנה את תחילתה של קריירה ארוכה בתורת הסיבוכיות החישובית. הוא נולד בשנת 1953 באתונה, ובהמשך השלים דוקטורט במדעי המחשב באוניברסיטת פרינסטון, ולאחר מכן השפיע על תורת מסדי הנתונים, אימות מערכות ותורת הגרפים האלגוריתמית.
יסודות בסיבוכיות
ינאקאקיס בילה למעלה משני עשורים במחקר תעשייתי, והחל את כהונתו במעבדות בל (Bell Laboratories) בשנת 1978. הוא כיהן שם כמנהל מחלקת מחקר עקרונות המחשוב בין השנים 1991 ל-2001. במהלך תקופה זו, הוא שיתף פעולה עם כריסטוס פאפאדימיטריו (Christos Papadimitriou) בשנת 1988 כדי להגדיר את מחלקות הסיבוכיות Max-NP ו-Max-SNP, ובכך סיפק הסבר קפדני למגבלות שנצפו בקירוב של בעיות NP-קשות כמו בעיית הסוכן הנוסע ו-3SAT. עבודתו משנת 1993 עם קארסטן לונד (Carsten Lund) הבהירה עוד יותר את הקושי המובנה בחישוב פתרונות מקורבים לבעיות מינימיזציה כגון צביעת גרפים.
חידושים במסדי נתונים
תרומותיו לתורת מסדי הנתונים התמקדו באופטימיזציה של עיבוד שאילתות באמצעות מחקר של סכימות אציקליות. הוא הציג את אלגוריתם ינאקאקיס עבור שאילתות צירופיות אציקליות, והוכיח כי ניתן לפתור מבנים אלו בזמן פולינומי. מעבר לאופטימיזציית שאילתות, הוא חקר מדיניות נעילה, והוכיח שניתן לשמור על בטיחות מסד הנתונים מחוץ למגבלות הנוקשות של נעילה דו-שלבית על ידי שימוש במבנה ההיפרגרף של הנתונים ובאילוצי עקביות של טרנזקציות כדי למנוע קיפאון.
אימות ומנהיגות אקדמית
במעברו לאקדמיה, ינאקאקיס החזיק במשרת פרופסור באוניברסיטת סטנפורד בשנת 2002 לפני שהצטרף לאוניברסיטת קולומביה בשנת 2004. כיום הוא מכהן כפרופסור למדעי המחשב על שם פרסי ק. ווידה ל. ו. הדסון. מחקריו באימות בעזרת מחשב ביססו יסודות אלגוריתמיים לבדיקת לוגיקה זמנית בזמן ליניארי (Linear-time temporal logic) ותרשימי רצף הודעות (Message Sequence Charts). הוא גם פיתח את בדיקת המודלים האדפטיבית (Adaptive Model Checking) לצד אלכס גרוס (Alex Groce) ודורון פלד (Doron Peled), שיטה המעדנת מודלים של מערכות על סמך תוצאות אימות.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →הכרה מקצועית
ינאקאקיס שמר על נוכחות עריכתית משמעותית, לאחר ששימש כעורך ראשי של ה-SIAM Journal on Computing בין השנים 1998 ו-2003. מעמדו האקדמי משתקף בחברותו באקדמיה הלאומית למדעים, באקדמיה הלאומית להנדסה, באקדמיה האמריקאית לאמנויות ולמדעים ובאקדמיה אירופיאה (Academia Europaea). פרסיו כוללים את פרס קנות' לשנת 2005 ואת פרס ג'ון פון נוימן לתורת המחשב לשנת 2023.
עובדות מהירות
- נולד: 1953, אתונה, יוון - דוקטורט: אוניברסיטת פרינסטון, 1979 - פרס קנות': 2005 - פרס ג'ון פון נוימן לתורת המחשב: 2023 - עמית ACM: 1998 - אזרחות: ארצות הברית; יוון - שפות: יוונית מודרנית
שאלות שקוראים שואלים
### מהו אלגוריתם ינאקאקיס?
זוהי שיטה המשמשת לביצוע שאילתות צירופיות אציקליות במערכות מסדי נתונים, המאפשרת לפתור אותן בזמן פולינומי.
### עם אילו מוסדות היה ינאקאקיס קשור?
הוא עבד במעבדות בל, מעבדות אוואיה, אוניברסיטת סטנפורד ואוניברסיטת קולומביה.