בתשובה לגדי אלכסנדרוביץ', 14/07/09 19:47
שיטה פרקטית להבחנה באקראיות 516380
אצלי זה מתקשר משום מה אבל אתה צודק, זה לגמרי אוברקיל למקרה של מכונה דטרמיניסטית. אז חידה (אני מקוה שלא קלה מדי): מה סיבוכיות המקום הנדרשת על מנת להכריע אם מכונת טיורינג (דטרמיניסטית ללא קלט) בסיבוכיות מקום s עוצרת או לא?
שיטה פרקטית להבחנה באקראיות 516397
החסם העליון הסטנדרטי הוא אקספוננציאלי ב-s (במדויק, גודל האלפבית בחזקת s, ועוד לוג של s, ועוד לוג של גודל קבוצת המצבים). אני מפספס כאן משהו?
שיטה פרקטית להבחנה באקראיות 516421
סיבוכיות המקום.
שיטה פרקטית להבחנה באקראיות 516424
אוי, בעצם יש פתרון טריוויאלי למה ששאלתי. אז בואו נגיד שהאלגוריתם צריך לעבוד אפילו בלי לדעת את s.
שיטה פרקטית להבחנה באקראיות 516432
הפתרון הקודם שלי עשה מיש-מש - התחלתי מסיבוכיות הזמן, ואז עברתי לסיבוכיות המקום (אקספוננציאלי ב-s, אבל אז לוגריתמי ב-s?). מן הסתם סיבוכיות המקום, במקרה הקודם, היא s ועוד הלוגים הללו.

במקרה שאתה מתאר לא מספיק לספור קונפיגורציות אלא צריך לשמור את כולן, לא? זה מקפיץ אותנו שוב לסיבוכיות אקספוננציאלית, אלא אם אני שוב מפספס משהו.
שיטה פרקטית להבחנה באקראיות 516508
יופי, זו בדיוק החידה. סיבוכיות מקום אקספוננציאלית זה הרבה יותר מדי.
שיטה פרקטית להבחנה באקראיות 516576
המממ, אפשר לשמור מונה של מספר הצעדים ובנוסף לשמור את כמות המקום שהמכונה המסומלצת השתמשה בה עד כה. אם מספר הצעדים עובר מתישהו את מספר הקונפיגורציות האפשריות בהינתן כמות המקום הנוכחית, סיימנו. זה הרעיון?
שיטה פרקטית להבחנה באקראיות 516609
זה לא הרעיון שלי אבל זה עונה על השאלה. אני אנסה לחשוב על חידות יותר טובות בפעם הבאה...

מה שכן, האלגוריתם שהצעת עלול לקחת זמן רב הרבה יותר מהדרוש. אתה יודע לתת אלגוריתם עם סיבוכיות מקום טובה ועם סיבוכיות זמן כמו של האלגוריתם הנאיבי (כלומר פרופורציונית למספר המצבים בפועל של המכונה ולא לחסם העליון)? החידה הזו נעשית יותר מדי "תפורה", אני אבין אם תעדיף לפרוש.
שיטה פרקטית להבחנה באקראיות 516620
אפשר אולי להשתמש בתעלול הסטנדרטי למציאת אורך מעגל - מבצעים שתי ריצות במקביל שאחת מהן מהירה פי שתיים יותר מהשנייה, ובכל סיבוב בודקים אם יש ''התנגשות'' (ליתר דיוק, אם ההרצה המהירה עקפה את ההרצה האיטית).
שיטה פרקטית להבחנה באקראיות 516634
כן, זה מה שרציתי. כאמור, פעם הבאה יהיה (אולי) יותר טוב.
שיטה פרקטית להבחנה באקראיות 516637
זו חידה יפה דווקא, אם כי לא נראה לי שמי שלא מכיר את תעלול המעגל יחשוב על הפתרון שכיוונת אליו (נראה לי שהם כן יוכלו למצוא את הפתרון הנאיבי יותר של ספירת הקונפיגורציות).
שיטה פרקטית להבחנה באקראיות 516646
הנחמד בעיני (אתה הזכרת לי את זה בהערה שלך על סאוויץ') הוא המעבר בין השאלה החישובית לשאלה קומבינטורית/אלגוריתמית על גרף הקונפיגורציות.
שיטה פרקטית להבחנה באקראיות 517000
למרות שעכשיו ברור הפתרון, איך מנוסחת החידה על אורך מעגל?
שיטה פרקטית להבחנה באקראיות 517009
יש לך מעגל שנתון באמצעות רשימה מקושרת (כלומר, סדרה של מצביעים שכל אחד מצביע לכתובת של הבא). תמצא את האורך שלו.

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

שמא לתת כנתון לא רק מעגל, אלא גרף קשיר שמכיל מעגל?
שיטה פרקטית להבחנה באקראיות 517026
אה... כן, זה כמובן מה שהתכוונתי אליו (גרף קשיר שמכיל מעגל).
שיטה פרקטית להבחנה באקראיות 517077
ואז, כשזיהית ששני ה"פועלים" שלך באותו מקום, כבר השלמת סיבוב, אבל צריך לעשות אותו שוב כדי לספור, נכון?
שיטה פרקטית להבחנה באקראיות 517079
אז מה. זה לא מוסיף לסיבוכיות (לכל היותר מעלה את זמן הביצוע פי 1.5 או משהו בסביבה).
שיטה פרקטית להבחנה באקראיות 517167
ברור. זה רק גורע, ואני קטנוני פה, שמץ של שמץ מהחן של הפתרון, בעיקר אם לפני-כן חשבת שנתון שאתה על המעגל, שאז זה לא נחוץ.
שיטה פרקטית להבחנה באקראיות 517199
העניין הוא שלא חושבים כך. למשל, בדוגמה שהתחילה את העניין (סימולציה של מכונת טיורינג עם חסם זכרון) לא ידוע אם בכלל יש מעגל, ומאוד לא סביר שנהיה עליו כבר בהתחלה.
שיטה פרקטית להבחנה באקראיות 517200
הנוסח שאני מכיר הוא למצוא אם רשימה מקושרת מכילה מעגל.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים