תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 101:
#אם החלטנו לשייך, נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה <math>n_k + 1</math>, ונשייך את <math>M</math> אליו (ב[[#התכנות בניית עץ השיוך|התכנות בניית עץ השיוך]] נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.
 
לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1", (נניח שהפלטוהפלט שלה הוא "000111000"). בשלב זה, כל הצמתים בעץ פנויים. הצומת השמאלי ביותר ברמה
<center><math>
P_U^1(\text{"000111000"}) = |\Sigma|^{-|\text{"1"}|} = \frac{1}{3}
</math></center>
 
<center><math>
n_k =
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3}} \right)
\right\rceil
+1
</math></center>
 
לכן עלינו לבחור צומת ברמה 2. היותר ש
בשלב זה, כל הצמתים בעץ פנויים. הצומת השמאלי ביותר ברמה
<span dir = "ltr">
2 = |"1"| + 1
</span>
הופך להיות משוייך, והצמתים השמאליים ביותר ברמות 0 ו1 הופכים להיות תפוסים.
 
 
שורה 111 ⟵ 125:
[[File:KolmogorovTree 2.png|left|thumb|בניית העץ 2 - שיוך צומת שני לתכנית בעלת אורך תיאור 0]]
 
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), (והפלט שלה הוא "011"). בשלב זה, הצומת השמאלי ביותר ברמה
<span dir = "ltr">
1 = |""| + 1