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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
←‏בניית עץ השיוך: עריכה, הגהה
שורה 107:
ולכן
<center><math>
n_kn_1(x) =
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3}} \right)
\right\rceil
=
1
</math></center>
 
לכן עלינו לבחור צומת ברמה <math>1 + 1 = 2</math>. היותר שבשלב זה כל הצמתים בעץ פנויים, הצומת השמאלי ביותר ברמה 2
<span dir = "ltr">
2 = |"1"| + 1
</span>
הופך להיות משוייך, והצמתים השמאליים ביותר ברמות 0 ו1 הופכים להיות תפוסים.
 
 
 
נניח שהתוכנית השניהההשניה שהסתיימה היא התוכנית שתיאורה הוא באורך מיליארד, והפלט שלה הוא שוב "000111000". בשלב זה,
<center><math>
P_U^k2(x) = |\Sigma|^{-|\langle M_2 \rangle |} = 3^{-1,000,000,000}
</math></center>
ולכן
<center><math>
n_1n_2(x) =
\left\lceil
\log_{3} \left( \frac{1}{\frac{1}{3} + 3^{-1,000,000,000}} \right)
\right\rceil
+= 1
</math></center>
 
שהוא(ולכן שובהוא 2לא השתנה). אמנם הרמה המתאימה היא 2, אך היות שברמה זו כבר יש צומת המשוייך לתוכנית המציירת מחרוזת זו, לא נשייך את התוכנית לצומת.
 
 
שורה 141 ⟵ 140:
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה,
<center><math>
P_U^3(x) = |\Sigma|^{-|\langle M_3 \rangle |} = 3^{-0} = 1
</math></center>
ולכן
שורה 149 ⟵ 148:
\log_{3} \left( \frac{1}{1} \right)
\right\rceil
=
0
</math></center>
עלינו לשייך את התוכנית לצומת ברמה <math>0 + 1 = 1</math>. היות שהצומת השמאלי ביותר ברמה זו תפוס, נשייך אותו לצומת השני משמאל ברמה 21.
 
[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]