לדלג לתוכן

פרס גדל

מתוך ויקיפדיה, האנציקלופדיה החופשית
פרס גדל
Gödel Prize
קורט גדל
קורט גדל
תיאור פרס למאמר במדעי המחשב
הגוף המעניק ACM, האיגוד האירופי לתאוריה של מדעי המחשב עריכת הנתון בוויקינתונים
סכום הזכייה 5,000 דולר אמריקאי עריכת הנתון בוויקינתונים
תקופת הפרס 1992–הווה (כ־34 שנים) עריכת הנתון בוויקינתונים
נקרא על שם קורט גדל עריכת הנתון בוויקינתונים
אתר רשמי
לעריכה בוויקינתונים שמשמש מקור לחלק מהמידע בתבנית

פרס גֶדֶל (באנגלית: The Gödel Prize) הוא פרס המוענק אחת לשנה, החל משנת 1993, עבור מאמר בולט באיכותו בתחום מדעי המחשב. הפרס מוענק על ידי האיגוד האירופי לתאוריה של מדעי המחשב (EATCS)[1] ו-ACM[2]. מעמד הענקת הפרס מתחלף מדי שנה בין הקולוקוויום הבינלאומי על אוטומט, שפות ותכנות (ICALP) (השייך ל-EATCS) לבין הסימפוזיון על תורת המחשוב (STOC) (השייך ל-ACM) לסירוגין. גובה הפרס עומד על 5,000 דולר אמריקאי. הפרס הוא השני בחשיבותו בתחום מדעי המחשב, לאחר פרס טיורינג.

הפרס קרוי על שם הלוגיקן האוסטרי קורט גדל, לאור תרומותיו הרבות בתחום הלוגיקה המתמטית, ולאור הגדרת אחת הבעיות הפתוחות המרכזיות במדעי המחשב שנודעה לימים כבעיית P=NP‏[3].

מבין 82 הזוכים בפרס עד שנת 2023, 21 הם ישראלים.

ארבעה מהזוכים – שפי גולדווסר, יוהאן הסטאד, סנג'יב ארורה ומריו סגדי – זכו פעמיים בפרס.

הזוכים בפרס

[עריכת קוד מקור | עריכה]
שנה שמות הזוכים הסיבה לזכייה
1993לסלו בבאי, שפי גולדווסר, סילביו מיקאלי, שלמה מורן, צ'ארלס ראקוףפיתוח המושג של מערכת הוכחה אינטראקטיבית
1994יוהאן הסטאדעל מציאת חסם תחתון אקספוננציאלי על גודלם של מעגלים בוליאניים קבועי-עומק לחישוב פונקציית זוגיות
1995ניל אימרמן, רוברט סלפצ'ניעל ההוכחה כי מחלקות סיבוכיות מקום אי-דטרמיניסטיות סגורות לפעולת המשלים (משפט אימרמן)
1996מארק ג'רום, אליסטר סינקליירעל עבודתם בנושא שרשראות מרקוב וקירוב בעיית הפרמננטה
1997ג'וזף הלפרן, יורם מוזסעל הגדרת "ידע" במערכות מבוזרות
1998סינוסוק טודהעל הוכחת הקשר בין מחלקת הסיבוכיות PP וההיררכיה הפולינומית (משפט טודה)
1999פיטר שורעבור פיתוח אלגוריתם קוונטי למציאת גורם ראשוני בזמן פולינומי (אלגוריתם שור)
2000משה ורדי, פייר וולפרעל בדיקות מודאליות בעזרת אוטומט סופי
2001סנג'יב ארורה, אוריאל פייגה, שפי גולדווסר, קארסטן לאנד, לסלו לובאס, ראג'יב מוטוואני, שמואל ספרא, מדו סודן, מריו סגדיעל משפט ה-PCP והשלכותיו באלגוריתמי קירוב
2002ג'ארד סניזרגוסעל הוכחת כריעות של בעיית השקילות, בשפות של אוטומט מחסנית דטרמיניסטי
2003יואב פרוינד, רוברט שפירעבור המצאת אלגוריתם AdaBoost‏
2004מאוריס הרלי, מייק זאקס, ניר שביט, פוטיוס זהרוגלועל אפליקציות בטופולוגיה של חישוב מבוזר
2005נגה אלון, יוסי מטיאס, מריו סגדיעל תרומתם היסודית בתחום אלגוריתמים לזרמי מידע
2006מנינדה אגרוול, נירג' קייל, ניטין סקסנהעל אלגוריתם AKS לבדיקת ראשוניות של מספר בזמן פולינומי
2007אלכסנדר רזבורוב, סטיבן רודיךעל הוכחות טבעיות
2008שאנגואה טאנג, דניאל ספילמןעל שיטת ניתוח האלגוריתמים Smooth Analysis‏
2009עומר ריינגולד, סליל ודהן, אבי ויגדרזוןעל מכפלות "זיג-זג" של גרפים
2010סנג'יב ארורה, ג'וזף מיטשלעל פיתוח אלגוריתמי קירוב יעילים עבור בעיית הסוכן הנוסע במרחב אוקלידי
2011יוהאן הסטאדעל תוצאות אי-קיום של אלגוריתמי קירוב (בעלי פרמטרים "טובים") עבור בעיות NP קשות
2012אליאס קוטסופיאס, כריסטוס פאפאדימיטריו, טים ראפגרדן, אווה טרדוש, נעם ניסן, אמיר רונןעל הנחת היסודות בתחום תורת המשחקים האלגוריתמית
2013דן בונה, מת'יו פרנקלין, אנטואן ז'וקסעל כלים קריפטוגרפיים המבוססים על מיפוי בי-ליניארי
2014רונאלד פאגין, אמנון לוטם, מוני נאורעל תוצאות פורצות דרך באלגוריתמים של קיבוץ מידע (אגרגציה)[4]
2015דניאל שפילמן, שנגואה טנג
2016סטפן ברוקס, פטר הורן
2017סינתיה דבורק, פרנק מקשרי, קובי נסים, אדם סמיתעל המצאת פרטיות דיפרנציאלית
2018עודד רגבעל הצגת בעיית למידה עם שגיאות
2019אירית דינורעל הוכחה חדשה למשפט PCP
2020רובין מוסר, גבור טרדוסעל הוכחה קונסטרוקטיבית ללמת המקומיות של לובאס
2021אנדריי בולאטוב, ג'ין-אי קאי, אקס-צ'אן, מרטין דייר, דייוויד ריצ'רביעל עבודתם על סיווג בעיית הספירה של בעיית סיפוק אילוצים
2022צביקה ברקרסקי, קרייג ג'נטרי, וינוד וייקונטנתןעל עבודתם על הצפנה הומומורפית מלאה
2023סמואל פיוריני, סרג' מסאר, סבסטיאן פוקוטה, הנס ראג' טיוארי, רונלד דה וולף ותומס רוטבוסלהראות שלכל ניסוח מורחב לבעיית הסוכן הנוסע יש גדילה מעריכית
2024ראיין ויליאמס

תהליך הזכייה בפרס

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

מועמדות וזכאות

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

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

כל חבר בקהילה המדעית רשאי להציע מאמר כמועמד לפרס. מאמר ייחשב כמועמד אם שני אנשים הציעו אותו כמועמד.

החלטה על זוכה

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

המאמר הזוכה נבחר על ידי ועדה בת שישה חברים. הרכב הוועדה מתחלף מדי שנה. ליו"ר ACM וליו"ר EATCS זכות לבחור שלושה חברים לוועדה, כל אחד.

קישורים חיצוניים

[עריכת קוד מקור | עריכה]
ויקישיתוף מדיה וקבצים בנושא פרס גדל בוויקישיתוף

הערות שוליים

[עריכת קוד מקור | עריכה]
  1. ↑ אתר EATCS.
  2. ↑ אתר ACM-SIGACT.
  3. ↑ גדל עסק בנושא זה לראשונה, כפי שהתגלה במכתב ששלח אל ג'ון פון נוימן. ראו אתר פרס גדל ב-ACM-SIGACT.
  4. ↑ Ronald Fagin, Amnon Lotem, and Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences 66 (2003), pp. 614–656