סטיבן קוק

מתוך ויקיפדיה, האנציקלופדיה החופשית
סטיבן ארתור קוק
Stephen Cook
סטיבן ארתור קוק
סטיבן ארתור קוק
לידה 14 בדצמבר 1939 (בן 84)
באפלו, ארצות הברית עריכת הנתון בוויקינתונים
שם לידה Stephen Arthur Cook עריכת הנתון בוויקינתונים
ענף מדעי מדעי המחשב
מקום מגורים קנדה וארצות הברית
מקום לימודים
מנחה לדוקטורט האו ואנג עריכת הנתון בוויקינתונים
מוסדות
תלמידי דוקטורט Toniann Pitassi, Leslie Michael Goldschlager, Derek C. Oppen, Daniel Brand, Steven Perron, Tsuyoshi Morioka, Phuong The Nguyen, Tomoyuki Yamakami, Martin Dowd, Stephen Bellantoni, Lila A. Fontes, R. Dustin Wehr, Gloria Kissin, Dai Tri Man Le, Robert A. Reckhow, Akitoshi Kawamura, Kaveh Ghasemloo, Alan Ramsay Skelley, Antonina Kolokolova, ארבינד גופטה, Michael Soltys, H. James (Howard) Hoover, ולטר סאביץ', Anna Lubiw, מרק ברברמן, Roberto Lins de Carvalho, Paul William Beame, Valentine Kabanets, Xudong Fu, Patrick William Dymond, Romas Aleliunas, Pierre Murdock McKenzie, François Pitt, Bruce M. Kapron, Robert Robere עריכת הנתון בוויקינתונים
פרסים והוקרה
  • John L. Synge Award (2006)
  • מדליית הזהב של קנדה ע״ש גרהרד הרצברג למדע והנדסה (2012)
  • פרס חזית הידע של קרן BBVA (2015)
  • עמית ACM (2008)
  • מסדר אונטריו (2013)
  • קצין/ה במסדר קנדה (2015)
  • פרס מרכז מחקר המתמטיקה הקנדי-פילדס-המכון הפסיפי למדעים מתמטיים (1999)
  • פרס טיורינג (1982)
  • Gödel Lecturer (1999)
  • עמית החברה המלכותית של קנדה
  • עמית החברה המלכותית עריכת הנתון בוויקינתונים
צאצאים גורדון קוק עריכת הנתון בוויקינתונים
www.cs.toronto.edu/~sacook/
תרומות עיקריות
NP-שלמות
משפט קוק-לוין
לעריכה בוויקינתונים שמשמש מקור לחלק מהמידע בתבנית

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

מחקר[עריכת קוד מקור | עריכה]

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

במאמרו מ-1971 "המורכבות של הוכחת משפט",[1][2] קוק טבע פורמלית את המושגים של רדוקציה פולינומית ובעיות NP-שלמות, והוכיח את קיומה של בעיה NP-שלמה על ידי שהראה שבעיית הספיקות היא NP-שלמה. משפט זה הוכח באופן עצמאי על ידי לאוניד לוין בברית המועצות, ולכן מכונה משפט קוק-לוין. המאמר גם מציג פורמלית את הבעיה המפורסמת במדעי המחשב, שאלת P=NP.

פרסים[עריכת קוד מקור | עריכה]

קוק זכה בפרס טיורינג בשנת 1982 על תרומתו לתורת הסיבוכיות.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא סטיבן קוק בוויקישיתוף

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ "The Complexity of Theorem Proving Procedures", PDF file of a scanned version
  2. ^ "The Complexity of Theorem Proving Procedures", PDF file of a retyped version