בתשובה לשלוסמם, 14/07/09 19:03
 |
|
 |
||
|
||||
 |
דווקא קיימת הוכחה שאין תוכנית שמסוגלת להכריע בזמן סופי האם אלגוריתם שרץ על הקלט הריק עוצר. הבעיה הזו היא שינוי קל (ולא מהותי) של בעיית העצירה [ויקיפדיה]. |  |
 |
 |
|
|
|
||
|
||||
|
אולי הוא מתבלבל עם אלגוריתמים בעלי זיכרון חסום, עבורם דווקא אפשר (ואפילו קל, בזמן אקספוננציאלי) לדעת אם הם עוצרים או לא (סאוויץ'). | |
|
|
|
|
|
||
|
||||
|
לא קשור לסאוויץ' (שמדבר על הקשר בין דרישות הזכרון של אלגוריתם אי דטרמיניסטי ואלגוריתם דטרמיניסטי שקול), אלא סתם לכך שמספר הקונפיגורציות של אלגוריתם כזה הוא סופי. | |
|
|
|
|
|
||
|
||||
|
אצלי זה מתקשר משום מה אבל אתה צודק, זה לגמרי אוברקיל למקרה של מכונה דטרמיניסטית. אז חידה (אני מקוה שלא קלה מדי): מה סיבוכיות המקום הנדרשת על מנת להכריע אם מכונת טיורינג (דטרמיניסטית ללא קלט) בסיבוכיות מקום s עוצרת או לא? | |
|
|
|
|
|
||
|
||||
|
החסם העליון הסטנדרטי הוא אקספוננציאלי ב-s (במדויק, גודל האלפבית בחזקת s, ועוד לוג של s, ועוד לוג של גודל קבוצת המצבים). אני מפספס כאן משהו? | |
|
|
|
|
|
||
|
||||
|
סיבוכיות המקום. | |
|
|
|
|
|
||
|
||||
|
אוי, בעצם יש פתרון טריוויאלי למה ששאלתי. אז בואו נגיד שהאלגוריתם צריך לעבוד אפילו בלי לדעת את s. | |
|
|
|
|
|
||
|
||||
|
הפתרון הקודם שלי עשה מיש-מש - התחלתי מסיבוכיות הזמן, ואז עברתי לסיבוכיות המקום (אקספוננציאלי ב-s, אבל אז לוגריתמי ב-s?). מן הסתם סיבוכיות המקום, במקרה הקודם, היא s ועוד הלוגים הללו. במקרה שאתה מתאר לא מספיק לספור קונפיגורציות אלא צריך לשמור את כולן, לא? זה מקפיץ אותנו שוב לסיבוכיות אקספוננציאלית, אלא אם אני שוב מפספס משהו. |
|
|
|
|
|
|
||
|
||||
|
יופי, זו בדיוק החידה. סיבוכיות מקום אקספוננציאלית זה הרבה יותר מדי. | |
|
|
|
|
|
||
|
||||
|
המממ, אפשר לשמור מונה של מספר הצעדים ובנוסף לשמור את כמות המקום שהמכונה המסומלצת השתמשה בה עד כה. אם מספר הצעדים עובר מתישהו את מספר הקונפיגורציות האפשריות בהינתן כמות המקום הנוכחית, סיימנו. זה הרעיון? | |
|
|
|
|
|
||
|
||||
|
זה לא הרעיון שלי אבל זה עונה על השאלה. אני אנסה לחשוב על חידות יותר טובות בפעם הבאה... מה שכן, האלגוריתם שהצעת עלול לקחת זמן רב הרבה יותר מהדרוש. אתה יודע לתת אלגוריתם עם סיבוכיות מקום טובה ועם סיבוכיות זמן כמו של האלגוריתם הנאיבי (כלומר פרופורציונית למספר המצבים בפועל של המכונה ולא לחסם העליון)? החידה הזו נעשית יותר מדי "תפורה", אני אבין אם תעדיף לפרוש. |
|
|
|
|
|
|
||
|
||||
|
אפשר אולי להשתמש בתעלול הסטנדרטי למציאת אורך מעגל - מבצעים שתי ריצות במקביל שאחת מהן מהירה פי שתיים יותר מהשנייה, ובכל סיבוב בודקים אם יש ''התנגשות'' (ליתר דיוק, אם ההרצה המהירה עקפה את ההרצה האיטית). | |
|
|
|
|
|
||
|
||||
|
כן, זה מה שרציתי. כאמור, פעם הבאה יהיה (אולי) יותר טוב. | |
|
|
|
|
|
||
|
||||
|
זו חידה יפה דווקא, אם כי לא נראה לי שמי שלא מכיר את תעלול המעגל יחשוב על הפתרון שכיוונת אליו (נראה לי שהם כן יוכלו למצוא את הפתרון הנאיבי יותר של ספירת הקונפיגורציות). | |
|
|
|
|
|
||
|
||||
|
הנחמד בעיני (אתה הזכרת לי את זה בהערה שלך על סאוויץ') הוא המעבר בין השאלה החישובית לשאלה קומבינטורית/אלגוריתמית על גרף הקונפיגורציות. | |
|
|
|
|
|
||
|
||||
|
למרות שעכשיו ברור הפתרון, איך מנוסחת החידה על אורך מעגל? | |
|
|
|
|
|
||
|
||||
|
יש לך מעגל שנתון באמצעות רשימה מקושרת (כלומר, סדרה של מצביעים שכל אחד מצביע לכתובת של הבא). תמצא את האורך שלו. מקום אחר, ופרקטי, שבו החידה צצה - מציאת מעגלים בפונקציות תמצות קריפטוגרפיות. כאן אתה מתחיל ממספר כלשהו, מפעיל עליו את הפונקציה שוב ושוב עד שאתה מגיע למספר שכבר "ביקרת" בו. אותו רעיון נמצא בשימוש גם באלגוריתם ה-rho של פולרד לפירוק לגורמים. |
|
|
|
|
|
|
||
|
||||
|
יש לך דרך אלגנטית לחסום בניסוח החידה את הפתרון הטריוויאלי, לזכור את הכתובת הראשונה? שמא לתת כנתון לא רק מעגל, אלא גרף קשיר שמכיל מעגל? |
|
|
|
|
|
|
||
|
||||
|
אה... כן, זה כמובן מה שהתכוונתי אליו (גרף קשיר שמכיל מעגל). | |
|
|
|
|
|
||
|
||||
|
ואז, כשזיהית ששני ה"פועלים" שלך באותו מקום, כבר השלמת סיבוב, אבל צריך לעשות אותו שוב כדי לספור, נכון? | |
|
|
|
|
|
||
|
||||
|
אז מה. זה לא מוסיף לסיבוכיות (לכל היותר מעלה את זמן הביצוע פי 1.5 או משהו בסביבה). | |
|
|
|
|
|
||
|
||||
|
ברור. זה רק גורע, ואני קטנוני פה, שמץ של שמץ מהחן של הפתרון, בעיקר אם לפני-כן חשבת שנתון שאתה על המעגל, שאז זה לא נחוץ. | |
|
|
|
|
|
||
|
||||
|
העניין הוא שלא חושבים כך. למשל, בדוגמה שהתחילה את העניין (סימולציה של מכונת טיורינג עם חסם זכרון) לא ידוע אם בכלל יש מעגל, ומאוד לא סביר שנהיה עליו כבר בהתחלה. | |
|
|
|
|
|
||
|
||||
|
הנוסח שאני מכיר הוא למצוא אם רשימה מקושרת מכילה מעגל. | |
|
|
|
|
|
||
|
||||
|
אין תוכנית שמסוגלת להכריע עבור כל האלגוריתמים האפשריים, אבל לכל אלגוריתם ספציפי יש הוכחה משלו | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |