בתשובה לאלון עמית, 29/01/04 21:45
שיו, אני *בטוח* שהיה שם פרפר 193979
האייל האלמוני • בתשובה לאלון עמית יום ה', 29/1/2004, 22:43
זה לא מפתיע אותי שאתה קראת אותו, נראה לי שיש משהו בספרים האלה שמושך יותר מתמטיקאים ממדעני מחשב.

ככלל, אחד מהדברים שמפריד בין מתמטיקאים למדעני מחשב הוא הנטיה של האחרונים להתמקד בהערכות (approximations) לעומת הנטיה של הראשונים להתמקד בחישובים מדויקים. כך למשל לרוב מדעני מחשב מתעניינים רק בסדרי גודל של כל מיני כמויות ‏1 לעומת הערך המדויק של הכמות. אחת הסיבות לכך היא שהרבה פעמים יש כלל של 80/20 (או אפילו משהו ששואף ל100/0) בבעיות כאלה: בשביל לקבל הערכה שמספיקה לך ל80% מהצרכים, אתה צריך לעשות 20% מהעבודה. מדעני מחשב לא מוכנים בד"כ "להזיע" ע"מ לשפר את ההערכה, אם השיפור הוא לא קריטי עבורם.

מהמעט שקראתי בספרו, Knuth במובן הזה (ואני חושב שגם במובנים אחרים) הוא יותר דומה למתמטיקאי מאשר למדען מחשב. הוא רוצה לחשב בדיוק כל כמות. זה מצריך ירידה לפרטים‏2 שיכולה להיות מאוד מעייפת ומייאשת למדעני מחשב, אבל בהחלט יכול להיות שבדרך הוא משתמש או מפתח מתמטיקה מאוד מעניינת.

---
‏1 כמו למשל מספר צעדי החישוב שמחשב לוקח ע"מ לבצע משימה מסוימת או הגודל של קליקה מקסימלית בגרף מקרי.

‏2 כמו הגדרה מדויקת של איזה מחשב ואיזה שפת מחשב משתמשים בה.
שיו, אני *בטוח* שהיה שם פרפר 193980
האייל האלמוני • בתשובה להאייל האלמוני יום ה', 29/1/2004, 22:45
בינתיים ראיתי שבתגובה 193976 נתת עוד דוגמא (שלא ידעתי עליה) למקרה שבו K מוכן להשקיע הרבה מאמץ בשביל לתת חישוב יותר מדויק, כאשר רמת הדיוק הזו לא ממש מעניינת את רוב מדעני המחשב.
שיו, אני *בטוח* שהיה שם פרפר 193985
האייל האלמוני • בתשובה להאייל האלמוני יום ה', 29/1/2004, 22:56
דוגמא לפער הזה בין מתמטיקאים למדעני המחשב הוא המשפט שנקרא ה Prime Number Theorem

המשפט הזה נחשב למשפט מפורסם וחשוב במתמטיקה, והוא מראה מספר המספרים הראשוניים בין 1 ל n שואף ל n/lnn (ככל שn שואף לאינסוף).

עעבור מדעני מחשב,כמעט לכל שימוש אפשרי מספיקה התוצאה של צ'בישב שהמספר הזה הוא בתחום שבין 0.8n/lnn ל 1.2n/lnn, את ההערכה הזו אפשר לקבל בצורה הרבה יותר פשוטה מאשר ה prime number theorem (יש לתוצאה הזו הוכחה של בערך 4 שורות), ולכן מן הסתם אם זה היה תלוי במדעני מחשב, לתוצאה של צ'בישב היו קוראים ה prime number theorem.
שיו, אני *בטוח* שהיה שם פרפר 193989
עוזי ו. • בתשובה להאייל האלמוני יום ה', 29/1/2004, 23:14
כשיגיעו לכאן היצורים הירוקים בעלי שלוש העיניים, אני בטוח שהשאלה הראשונה שלהם תהיה אם כבר הצלחנו להוכיח שההפרש בין מספר הראשוניים מתחת x לבין (x/log(x אינו עולה על קבוע כפול (sqrt(x)*log(x.
שיו, אני *בטוח* שהיה שם פרפר 193994
שוטה הכפר הגלובלי • בתשובה לעוזי ו. יום ה', 29/1/2004, 23:21
ואני חושב שהם יתעניינו יותר במיקומו של פח הזבל הקוסמי. עד שיקחו אותם לרמת חובב.
שיו, אני *בטוח* שהיה שם פרפר 194006
האייל האלמוני • בתשובה לעוזי ו. יום ה', 29/1/2004, 23:55
זאת תהיה השאלה השניה, אחרי שהם ישאלו אם הצלחנו להוכיח שאין מעגל בגודל
2^{sqrt(n)}
לחישוב ספיקות של נוסחה בוליאנית בגודל n.

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