גזירת חסם המקום של סביץ'

ניתוח נגישות רקורסיבית בלי לחייב מקום עבור כל עץ הרקורסיה.

שאלה

בגרף קונפיגורציות יש $N\le2^{c s(n)}$ צמתים, וכל קונפיגורציה מקודדת ב-$O(s(n))$ ביטים. נתחו בדיקה דטרמיניסטית רקורסיבית לנגישות בתוך $N$ צעדים והראו שהיא משתמשת ב-$O(s(n)^2)$ מקום.

רמז 1

בדקו מסלול באורך $2^\ell$ על ידי מעבר על נקודות אמצע ושתי קריאות עם $\ell-1$.

רמז 2

הקריאות והמועמדים רצים בזה אחר זה. חייבו מסגרת אחת לכל עומק, לא לכל צומת בעץ הרקורסיה.

פתרון מלא

נגדיר $R(u,v,\ell)$. עבור $\ell=0$ מקבלים אם $u=v$ או אם קיימת קשת יחידה מ-$u$ ל-$v$. אחרת עוברים על כל קונפיגורציה $m$ ומקבלים אם גם $R(u,m,\ell-1)$ וגם $R(m,v,\ell-1)$ מקבלות.

אינדוקציה מראה שהבדיקה שקולה לקיום מסלול באורך לכל היותר $2^\ell$: חוצים מסלול קיים בנקודת אמצע, ובכיוון השני משרשרים את שני חצאי המסלול.

נבחר $\ell=\lceil\log N\rceil=O(s(n))$. מסגרת שומרת מספר קבוע של קונפיגורציות, מונה מועמד ואת $\ell$, בסך $O(s(n))$ ביטים. הזיכרון ממוחזר לאחר כל חזרה, ולכן

בעומק $O(s(n))$ מתקבל $S=O(s(n)^2)$.

נקודת בדיקה

הזמן עלול להיות עצום. משפט סביץ' הוא סימולציית מקום, והמעבר הסדרתי הוא ששומר על מקום קטן.

הערת מקור

זהו מהלך עצמאי של הניתוח הסטנדרטי. הגשת סטודנט אינה מקור לנכונות.

טעויות נפוצות

• השמטת כיוון בהוכחת הנכונות או מקרה קצה בקלט.
• מדידת משאבים לפי ערך מספרי במקום אורך הקידוד.
• החלפת הוכחת החסם באינטואיציה בלבד.

מקורות ואימות

• Merged summary, pp. 124-127
• Sipser 3e, sec. 8.1
• Arora-Barak draft, sec. 4.2
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

פתיחה בגלריית ההמחשות: רקורסיית סביץ׳