בתשובה למ. השור, 15/07/09 16:12
שיטה פרקטית להבחנה באקראיות 516620
גדי אלכסנדרוביץ' • בתשובה למ. השור יום ד', 15/7/2009, 16:33
אפשר אולי להשתמש בתעלול הסטנדרטי למציאת אורך מעגל - מבצעים שתי ריצות במקביל שאחת מהן מהירה פי שתיים יותר מהשנייה, ובכל סיבוב בודקים אם יש ''התנגשות'' (ליתר דיוק, אם ההרצה המהירה עקפה את ההרצה האיטית).
שיטה פרקטית להבחנה באקראיות 516634
מ. השור • בתשובה לגדי אלכסנדרוביץ' יום ד', 15/7/2009, 16:51
כן, זה מה שרציתי. כאמור, פעם הבאה יהיה (אולי) יותר טוב.
שיטה פרקטית להבחנה באקראיות 516637
גדי אלכסנדרוביץ' • בתשובה למ. השור יום ד', 15/7/2009, 16:55
זו חידה יפה דווקא, אם כי לא נראה לי שמי שלא מכיר את תעלול המעגל יחשוב על הפתרון שכיוונת אליו (נראה לי שהם כן יוכלו למצוא את הפתרון הנאיבי יותר של ספירת הקונפיגורציות).
שיטה פרקטית להבחנה באקראיות 516646
מ. השור • בתשובה לגדי אלכסנדרוביץ' יום ד', 15/7/2009, 17:04
הנחמד בעיני (אתה הזכרת לי את זה בהערה שלך על סאוויץ') הוא המעבר בין השאלה החישובית לשאלה קומבינטורית/אלגוריתמית על גרף הקונפיגורציות.
שיטה פרקטית להבחנה באקראיות 517000
ירדן ניר-בוכבינדר • בתשובה לגדי אלכסנדרוביץ' שבת, 18/7/2009, 5:19
למרות שעכשיו ברור הפתרון, איך מנוסחת החידה על אורך מעגל?
שיטה פרקטית להבחנה באקראיות 517009
גדי אלכסנדרוביץ' • בתשובה לירדן ניר-בוכבינדר שבת, 18/7/2009, 9:32
יש לך מעגל שנתון באמצעות רשימה מקושרת (כלומר, סדרה של מצביעים שכל אחד מצביע לכתובת של הבא). תמצא את האורך שלו.

מקום אחר, ופרקטי, שבו החידה צצה - מציאת מעגלים בפונקציות תמצות קריפטוגרפיות. כאן אתה מתחיל ממספר כלשהו, מפעיל עליו את הפונקציה שוב ושוב עד שאתה מגיע למספר שכבר "ביקרת" בו. אותו רעיון נמצא בשימוש גם באלגוריתם ה-rho של פולרד לפירוק לגורמים.
שיטה פרקטית להבחנה באקראיות 517024
ירדן ניר-בוכבינדר • בתשובה לגדי אלכסנדרוביץ' שבת, 18/7/2009, 12:47
יש לך דרך אלגנטית לחסום בניסוח החידה את הפתרון הטריוויאלי, לזכור את הכתובת הראשונה?

שמא לתת כנתון לא רק מעגל, אלא גרף קשיר שמכיל מעגל?
שיטה פרקטית להבחנה באקראיות 517026
גדי אלכסנדרוביץ' • בתשובה לירדן ניר-בוכבינדר שבת, 18/7/2009, 13:34
אה... כן, זה כמובן מה שהתכוונתי אליו (גרף קשיר שמכיל מעגל).
שיטה פרקטית להבחנה באקראיות 517077
ירדן ניר-בוכבינדר • בתשובה לגדי אלכסנדרוביץ' יום א', 19/7/2009, 12:30
ואז, כשזיהית ששני ה"פועלים" שלך באותו מקום, כבר השלמת סיבוב, אבל צריך לעשות אותו שוב כדי לספור, נכון?
שיטה פרקטית להבחנה באקראיות 517079
צפריר כהן • בתשובה לירדן ניר-בוכבינדר יום א', 19/7/2009, 13:36
אז מה. זה לא מוסיף לסיבוכיות (לכל היותר מעלה את זמן הביצוע פי 1.5 או משהו בסביבה).
שיטה פרקטית להבחנה באקראיות 517167
ירדן ניר-בוכבינדר • בתשובה לצפריר כהן יום ב', 20/7/2009, 3:13
ברור. זה רק גורע, ואני קטנוני פה, שמץ של שמץ מהחן של הפתרון, בעיקר אם לפני-כן חשבת שנתון שאתה על המעגל, שאז זה לא נחוץ.
שיטה פרקטית להבחנה באקראיות 517199
גדי אלכסנדרוביץ' • בתשובה לירדן ניר-בוכבינדר יום ב', 20/7/2009, 10:09
העניין הוא שלא חושבים כך. למשל, בדוגמה שהתחילה את העניין (סימולציה של מכונת טיורינג עם חסם זכרון) לא ידוע אם בכלל יש מעגל, ומאוד לא סביר שנהיה עליו כבר בהתחלה.
שיטה פרקטית להבחנה באקראיות 517200
האייל האלמוני • בתשובה לירדן ניר-בוכבינדר יום ב', 20/7/2009, 10:11
הנוסח שאני מכיר הוא למצוא אם רשימה מקושרת מכילה מעגל.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות