שיחה:משפט אימרמן

זיכרון

מעלעול במאמר של אימרמן, לא נראה שנדרש שs(n)‎ תהיה פונקציית זיכרון, אלא רק גדולה מ$\log n$ (בפרט-ראה הערה במאמר של אימרמן בתחתית עמוד 3). אני מפספס משהו? זו הייתה הכוונה בפונקציה "סבירה"? Gran - שיחה 06:50, 12 בנובמבר 2009 (IST)

לא קראתי את המאמר של אימרמן כך שאני לא יודע אם זה אכן לא נדרש או שזה מובלע שם. עקרונית, צריך פונקצית זכרון כדי שאפשר יהיה לשחק עם גרף הקונפיגורציות; אולי כאן זה באמת לא הכרחי. אנסה לחפש מקור שמתייחס יותר טוב לנקודה הזו (סיפסר פשוט לא נכנס לזה ומדבר רק על זכרון לוגריתמי). גדי אלכסנדרוביץ' - שיחה 07:48, 12 בנובמבר 2009 (IST)

אה, מצאתי משהו. כאן הם מוכיחים את המשפט ראשית תחת ההנחה שזו פונקצית זכרון, ואז אומרים שהם יראו איך להיפטר מההנחה הזו (לא קראתי עדיין). אם כן, נראה לי שאפשר להשאיר רק את התנאי של גדול מלוג. גדי אלכסנדרוביץ' - שיחה 07:59, 12 בנובמבר 2009 (IST)

ראה את המאמר של אימרמן. שמתי קישור בדף עצמו. אחלה מאמר 4-5 עמודים ופרס גדל. ככה צריך! Gran - שיחה 08:48, 12 בנובמבר 2009 (IST)

שכתוב ההוכחה

עבודה טובה. רק הערה סגונית קטנה - השתדלתי בכתיבת הערך להימנע מלייחס לפעולת המכונה את המילה "ניחוש" שלדעתי בעייתית כאן (נותנת את התחושה האינטואיטיבית שהאלגוריתם הוא הסתברותי - זה בלבול נפוץ אצל מי שאינו בקיא בתחום), והשתדלתי להימנע מכתיבת דברים בסגנון "אנחנו צריכים להראות" וכדומה שלטעמי אינם אנציקלופדיים אלא מתאימים לספר לימוד. גדי אלכסנדרוביץ' - שיחה 11:53, 13 בנובמבר 2009 (IST)

שמתי לב לנושא ה"ניחוש" והשתדלתי להמנע ממנו ולכתוב "בחירה".. כנראה חמק לי. מה שכן, ניסיתי להמנע משימוש ב"מסלול חישוב". (א) כי זה לא מוגדר ו(ב) כי זה מבלבל לאיזה מסלול מתכוונים - מסלול בגרף או מסלול חישוב. Gran - שיחה 05:51, 14 בנובמבר 2009 (IST)

לגבי ההערה השניה - מסכים בהחלט, אתה מוזמן לתקן אם אתה מוצא עוד מקומות כאלה. כמו כן יש יותר מדי "סוגרים", אבל אני לא רואה דרך לצמצמם אותם. Gran - שיחה 05:54, 14 בנובמבר 2009 (IST)

אני דווקא לא רואה בעיה עם "מסלול חישוב" - זה מסלול בגרף שמתאר חישוב אחד אפשרי של האלגוריתם האי-דטרמיניסטי. נראה לי מוגדר היטב. כמובן שאם לא הכרחי להשתמש בו, אז עדיף שלא. גדי אלכסנדרוביץ' - שיחה 08:59, 14 בנובמבר 2009 (IST)