שרשור חידות

[vinney]

שרשור חידות

כי מזמן לא היה

 

[vinney]

שאלו אותי משהו כזה בעבודה

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

 

[nadav1974]

מזכיר לי חידה דומה ששמעתי פעם

ועדיין לא ידוע לי אם יש לה פתרון: על ציר המספרים השלמים נפלה פצצה. צריך למצוא על איזה מספר היא נפלה. קל? אז אילוץ נוסף: O(1) זיכרון. פתרון שלא עומד ב-O(1) זיכרון: בודקים ב-0. בודקים ב-1. בודקים במינוס 1. בודקים ב-2. בודקים במינוס 2. וכו' עד שמוצאים. הסיבה: החזקת המקום שאותו בודקים דורשת O(log n) זיכרון אם עובדים בבסיס ספירה שאינו 1.

 

[inbal76]

מה לגבי...

סימון המקום שנבדק? אם מותר אז אפשר אלגוריתם כזה: א- התחל בכיוון ימין ב- אם התא כבר מסומן, התקדם צעד נוסף ג- אם הגעת לתא שעוד לא סומן, סמן אותו והחלף כיוון ד- חזור ל-ב

 

[nadav1974]

זה גם לא O של 1 זיכרון

 

[inbal76]

למה?

 

[nadav1974]

כי יש אינסוף מספרים

וצריך לשמור מצב לכל מספר.

 

[inbal76]

זה תלוי במודל

אני חשבתי על מודל תיאורטי שבו נתון מערך (ביטים נניח) "אינסופי" ואז אין צורך לשמור דבר והסימון לא עולה לך בזכרון נוסף. אם המודל הוא "בחרתי מספר בין מינוס אינסוף לאינסוף, נחשו מהו" אז אתה צודק. במקרה כזה אני לא חושבת שזה פתיר, כיוון שהכרחי לשמור מידע שיתאר את "המצב" (=מה כבר נבדק) ובזיכרון קבוע ניתן לשמור רק מספר סופי של מצבים.

 

[nadav1974]

על ההתחלה אמרתי שאני לא יודע אם...

הבעייה פתירה או לא.

 

[DadleFish]

מה זאת אומרת "בודקים ב-1"?

אם אתה בודק ב-N, אתה צריך לדעת מה N. אם אתה מחזיק את N, אתה משתמש ב-logN זכרון. חסרות הגדרות לשאלה.

 

[nadav1974]

לכן, כאמור, זה לא פתרון טוב

השאלה מוגדרת היטב. מה שכן, לא ברור לי אם היא פתירה.

 

[DadleFish]

שוב,

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

 

[nadav1974]

למה?

אם הבדיקה היא פונקציה של המספר, היא לא צריכה לקבל שום פרמטר, ואז אין שום log של n זיכרון. אני חושב שזאת הנחה סבירה מאוד.

 

[DadleFish]

אנחנו לא משדרים על אותו גל.

נגיד שיש לי מספר N שאותו אני רוצה לבדוק. איך אני בודק אותו?

 

[nadav1974]

אני מבין בדיוק מה אתה אומר

תנסה להתמודד עם הנתונים שיש. בהנתן שאתה נמצא במקום כלשהו, הבדיקה היא ב-O של 1. זה לא אומר שאתה יודע משהו על המקום הזה, חוץ מהערך שהבדיקה מחזירה לך.

 

[inbal76]

אם המודל הוא כזה שמאפשר לך

"להיות במקום כלשהו" בלי לדעת איפה אתה נמצא, אז זה המודל שדיברתי עליו קודם (מערך אינסופי נתון שאתה מטייל עליו) ובמודל כזה אתה יכול לסמן תאים מבלי להשתמש בזיכרון נוסף.

 

[nadav1974]

אני דווקא חושב שהכוונה למודל השני

שהזכרת. אם לא, ברור איך פותרים את הבעייה.

 

[DadleFish]

אין לזה משמעות.

בוא נדבר "C" לרגע. אם אתה קורא לפונקציה ()CheckNow, על מה בדיוק היא מתבססת?

 

[nadav1974]

נו באמת

הבעייה הוצגה, ולדעתי הגדרת הבעייה סגורה. וכמו שכבר אמרתי, אני לא יודע אם הבעייה פתירה, ואם כן - איך. אין לי עוד מה להגיד לגבי זה.

 

[DadleFish]

קצת קשה לדעת עם בעיה היא

פתירה, כשהיא לא מוגדרת עד הסוף. לא נתת כלים לביצוע הבדיקה, מה אתה מצפה לקבל? זה כמו שאומר לך שאתה צריך לקרוא קובץ מהדיסק אבל אני לא אומר לך מה הפונקציות שעומדות לרשותך, או מה מערכת הקבצים הספציפית, וכו'. הבעיה לא מוגדרת. זה לא עניין של "לדעתי". תגדיר אותה כמו שצריך, ויהיה אפשר לראות אם היא פתירה או לא. לכל היותר, ב"הגדרה" שנתת, אפשר להוכיח שאי אפשר לפתור את הבעיה ב-(O(1 זכרון.