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

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

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

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

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