תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←בניית עץ השיוך: הרחבה |
|||
שורה 71:
כלשהו. במצב כזה, ננסה לשייך את התוכנית לצומת בעץ. נמצא את הצומת הפנוי הראשון (משמאל לימין) ברמה
<math>| \langle M \rangle | + 1</math>,
ונשייך את <math>M</math> אליו (בהמשך נוכיח שבהכרח תמיד יהיה צומת פנוי). הצומת הופך להיות משוייך. נמחק את כל הצאצאים של הצומת מהעץ, וכל צומת במסלול מהצומת לראש העץ (כולל ראש העץ) הופך להיות תפוס.
לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית הראשונה שהסתיימה היא התוכנית שתיאורה הוא "1", והפלט שלה הוא "000111000". בשלב זה, כל הצמתים בעץ פנויים. הצומת השמאלי ביותר ברמה
שורה 80:
[[File:KolmogorovTree 1.png|left|thumb|בניית העץ 1 - שיוך צומת ראשון לתכנית בעלת תיאור אורך 1]]
כעת נוסיף עוד כלל. אם הסתיימה ריצת תוכנית <math>M</math> המייצרת <math>x</math>, בעבר הסתיימה ריצת תוכנית <math>M'</math> שגם ייצרה <math>x</math>, ו-<math>|\langle M \rangle | = |\langle M' \rangle |</math>, אז לא משייכים את <math>M</math> לאף צומת. כך יוצא שלכל מחרוזת <math>x</math>, יש לכל היותר תוכנית אחת משוייכת בכל רמה בעץ.
לדוגמה (בתרשים "בניית העץ 1" המצוייר בצד שמאל), נניח שהתוכנית השניה שהסתיימה היא התוכנית שתיאורה הוא "2", והפלט שלה הוא "000111000". בעבר כבר הסתיימה התוכנית שתיאורה "1" עם אותו הפלט, ואורכי התיאורים שווים. לכן לא נשייך את התוכנית החדשה לצומת בעץ.
[[File:KolmogorovTree 2.png|left|thumb|בניית העץ 2 - שיוך צומת שני לתכנית בעלת תיאור אורך 0]]
נמשיך כך הלאה. לדוגמה (בתרשים "בניית העץ 2" המצוייר בצד שמאל), נניח שהתוכנית השלישית שהסתיימה היא התוכנית שתיאורה הוא "" (המחרוזת הריקה), והפלט שלה הוא "011". בשלב זה, הצומת השמאלי ביותר ברמה
<span dir = "ltr">
1 = |""| + 1
</span>
הוא תפוס. לכן נשייך את התוכנית לצומת השני משמאל ברמה 1.
[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]
| |||