מאמרו משנת 1969 "Gaussian Elimination is Not Optimal" הציג שיטה לכפל מטריצות ששברה את מגבלות המהירות הקיימות, והוכיחה כי פעולות מטריצות גדולות ניתן לבצע בהרבה מהירות יותר מסיבוכיות הזמן הקובעת של O(n³). גילוי זה הפך את פולקר שטרסן לדמות מפתח בהתפתחות מדעי המחשב התיאורטיים ועיצוב האלגוריתמים.
השכלה מוקדמת ומסלול אקדמי
נולד ב-1936 בדיסלדורף-גרסהיים, גרמניה, שטרסן למד תוכנית לימודים אקדמית רחבה הכוללת פילוסופיה, פיזיקה, מוזיקה ומתמטיקה. הוא סיים את לימודי הדוקטורט באוניברסיטת גטינגן ב-1962, בהדרכתו של קונרד יעקובס. קריירתו המוקדמה הביאה אותו לאוניברסיטת קליפורניה בברקלי, שם שירת במחלקות למתמטיקה וסטטיסטיקה, והגיע לדרגת פרופסור חבר. עד 1968 עבר לאוניברסיטת ציריך כדי לעמוד בראש הסמינר למתמטיקה יישומית, תפקיד שמילא במשך שני עשורים לפני שעבר לאוניברסיטת קונסטנץ ב-1988, שם נשאר עד פרישתו ב-1998.
תרומות י�ודיות לתורת ההסתברות
לפני מעברו לתורת הסיבוכיות החישובית, שטרסן עשה קידמה משמעותית בתורת ההסתברות. עבודתו מ-1964, "An Invariance Principle for the Law of the Iterated Logarithm", הקנתה לו הזמנה להרצות בקונגרס הבינלאומי של המתמטיקאים ב-1966 במוסקבה. עד 1965, הוא גזר תנאים הכרחיים ומספיקים בנוגע למידות הסתברות ומרטינגלים. עבודתו המשותפת עם הובר ב-1973 על בדיקות מינימקס והלמה של ניימן-פירסון שימשה אבן יסוד להתפתחויות מאוחרות יותר בתחום הסטטיסטיקה העמידה.
התקדמויות ביעילות אלגוריתמית
השפעתו של שטרסן על עיצוב אלגוריתמים כוללת את פיתוח אלגוריתם שנהאג'-שטרסן לכפל שלמים ב-1971, שסיפק את השיטה המהירה ביותר הידועה במשך עשורים. ב-1977, הוא שיתף פעולה עם רוברט מ. סולוביי כדי ליצור את בדיקת הפרימיות של סולוביי-שטרסן, שסימנה מעבר לאימות זמן פולינומי אקראי. שיתוף הפעולה שלו עם וולטר באור ב-1983 סיפק שיטה לגבול סיבוכיות של פונקציות רציונליות, מה שהרחיב את מחקרו המוקדם יותר על סיבוכיות אלגברית שהציג בקונגרס הבינלאומי של המתמטיקאים ב-1974 בוונקובר.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →הכרה מקצועית
לאורך קריירתו, שטרסן נבחר למספר מוסדות, כולל האקדמיה הגרמנית למדעים לאופולדינה, האקדמיה למדעים ולמדעי הרוח בגטינגן בסקסוניה התחתונה, והאקדמיה למדעים ולמדעי הרוח בהיידלברג. הוא גם עמית של החברה המתמטית האמריקאית. פרסיו כוללים את מדליית קנטור לשנת 1999, פרס פריס קנלאקיס לשנת 2003, פרס קנות' לשנת 2008, ומדליית קונרד צוזה לשנת 2011.
עובדות מהירות
- נולד: 1936, דיסלדורף - אזרחות: גרמניה - דוקטורט: אוניברסיטת גטינגן, 1962 - אלגוריתם בולט: אלגוריתם שטרסן לכפל מטריצות - פרס קנות': 2008 - מדליית קנטור: 1999 - מדליית קונרד צוזה: 2011 - בית אקדמי: אוניברסיטת קונסטנץ
שאלות שקוראים שואלים
### מה המשמעות של אלגוריתם שטרסן?
הוא הוכיח כי כפל מטריצות גדולות ניתן לבצע במהירות רבה יותר מגבול הזמן המקובל של O(n³).
### אילו פרסים חשובים קיבל פולקר שטרסן?
כבודו כולל את מדליית קנטור, פרס קנות', פרס פריס קנלאקיס ומדליית קונרד צוזה.