תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←בניית עץ השיוך: הרחבה |
|||
שורה 75:
התהליך משתמש ב[[w:en:dovetailing|dovetailing]], תהליך ה"הרצה במקביל" שראינו כבר במהלך הספר (לדוגמה, ב[[תורת החישוביות/מודל לבעיות הכרעה#שקילות למודל הכללי|הוכחת השקילות בין המודל הכללי למודל ההכרעה]]). מסדרים את כל התוכניות בסדר לקסיקורפי. מריצים את התוכנית הראשונה צעד אחד, לאחר מכן כ"א מ2 התוכניות הראשונות 2 צעדים, לאחר מכן כ"א מ3 התוכניות הראשונות 3 צעדים, וכו' וכו'.
במהלך הרצת הdovetailing, מדי פעם, תעצור תוכנית כלשהי עם פלט כלשהו. נסמן
<center><math>
P_U^k(x) = \sum_{i = 1, \ldots k \;|\; x_i = x_k} |\Sigma|^{-|\langle M_k \rangle|}.
שורה 91:
נשים לב שבגלל העיגול כלפי מעלה, ביטוי זה שואף מלמעלה למספר שלם חיובי כלשהו אליו הוא מגיע לאחר מספר סופי של צעדים.
כשעוצרת תוכנית <math>M_k</math>, נחליט האם לשייכה לעץ בעזרת רשימה של שלשות שנחזיק בצד המתארות את התוכניות שעצרו כבר. השלשה המתאימה לתוכנית ה-<math>j</math> שעצרה, מורכבת מ:
#
#
# הצומת שאליו <math>M</math> משוייכת, אם בכלל. את הצומת בעץ אפשר לתאר בעזרת מחרוזת של המסלול (לדוגמה, המחרוזת "01" מציינת הליכה שמאלה פעם אחת, ולאחריה הליכה למטה פעם אחת; המחרוזת "222" מציינת הליכה ימינה שלוש פעמים). לא כל תוכנית שהסתיימה משוייכת לצומת. נניח שיש סימון מיוחד, נניח "-", המציין שאין שיוך.
נחליט את שיוך <math>M_k</math> לצומת כך:
ונשייך את <math>M</math> אליו (ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.▼
[[File:KolmogorovTree 1.png|left|thumb|בניית העץ 1 - שיוך צומת ראשון לתכנית בעלת אורך תיאור 1]]
#נחפש ברשימה את האינדקסים בהם הופיעה המחרוזת בעבר: <math>J_k = \left\{j : x_j = x_k \right\}</math> (אם עדיין לא סיימה תוכנית המייצרת את <math>x_k</math>, זו סדרה ריקה).
#נבנה את סדרת ההערכות ללוגריתם: <math>n_j \;|\; j \in J_k</math>, ונחליט לשייך את התוכנית לצומת כלשהו רק אם <math>n_k</math> נמוך יותר מהערכים הקודמים (היות שמעגלים את הלוגריתם כלפי מעלה, לא בכל פעם בהכרח זה יקרה).
▲#אם החלטנו לשייך, נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה <math>n_k + 1</math>, ונשייך את <math>M</math> אליו (ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.
לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1" (נניח שהפלט שלה הוא "000111000"). בשלב זה, כל הצמתים בעץ פנויים. הצומת השמאלי ביותר ברמה
| |||