תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←בניית עץ השיוך: הרחבה |
|||
שורה 93:
כשעוצרת תוכנית <math>M_k</math>, נחליט האם לשייכה לעץ בעזרת רשימה של שלשות שנחזיק בצד המתארות את התוכניות שעצרו כבר. השלשה המתאימה לתוכנית ה-<math>j</math> שעצרה, מורכבת מ:
# המחרוזת, <math>x_j</math>
# אורך תיאור התוכנית, <math>l_j = l_j(x) = |\langle M_j \rangle|</math>
# הצומת שאליו <math>M</math> משוייכת, אם בכלל. את הצומת בעץ אפשר לתאר בעזרת מחרוזת של המסלול (לדוגמה, המחרוזת "01" מציינת הליכה שמאלה פעם אחת, ולאחריה הליכה למטה פעם אחת; המחרוזת "222" מציינת הליכה ימינה שלוש פעמים). לא כל תוכנית שהסתיימה משוייכת לצומת. נניח שיש סימון מיוחד, נניח "-", המציין שאין שיוך.
נחליט את שיוך <math>M_k</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 = n_j(x) \;|\; j \in J_k</math>, ונחליט לשייך את התוכנית לצומת כלשהו רק אם <math>n_k</math> נמוך יותר מהערכים הקודמים (היות שמעגלים את הלוגריתם כלפי מעלה, לא בכל פעם בהכרח זה יקרה).
#אם החלטנו לשייך, נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה <math>n_k + 1</math>, ונשייך את <math>M</math> אליו (ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.
לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1", והפלט שלה הוא "000111000". בשלב זה,
<center><math>
</math></center>
ולכן
<center><math>
n_k =
שורה 111:
\log_{3} \left( \frac{1}{\frac{1}{3}} \right)
\right\rceil
+1▼
</math></center>
לכן עלינו לבחור צומת ברמה <math>1 + 1 = 2</math>. היותר
<span dir = "ltr">
2 = |"1"| + 1
שורה 121 ⟵ 119:
הופך להיות משוייך, והצמתים השמאליים ביותר ברמות 0 ו1 הופכים להיות תפוסים.
נניח שהתוכנית השניהה שהסתיימה היא התוכנית שתיאורה הוא באורך מיליארד, והפלט שלה הוא שוב "000111000". בשלב זה,
<center><math>
P_U^k(x) = |\Sigma|^{-|\langle M_2 \rangle |} = 3^{-1,000,000,000}
</math></center>
ולכן
<center><math>
n_1(x) =
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3} + 3^{-1,000,000,000}} \right)
\right\rceil
▲+1
</math></center>
שהוא שוב 2. היות שברמה זו כבר יש צומת המשוייך לתוכנית המציירת מחרוזת זו, לא נשייך את התוכנית לצומת.
[[File:KolmogorovTree 2.png|left|thumb|בניית העץ 2 - שיוך צומת שני לתכנית בעלת אורך תיאור 0]]
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה,
<center><math>
|\Sigma|^{-|\langle M_3 \rangle |} = 3^{-0} = 1
</math></center>
ולכן
<center><math>
n_3(x) =
\left\lceil
\log_{3} \left( \frac{1}{1} \right)
\right\rceil
</math></center>
עלינו לשייך את התוכנית לצומת ברמה 1. היות שהצומת השמאלי ביותר ברמה זו תפוס, נשייך אותו לצומת השני משמאל ברמה 2.
[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]
| |||