תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←קידוד: הרחבה |
←קידוד: הרחבה |
||
שורה 76:
[[File:KolmogorovTree 3.png|left|thumb|בניית העץ 3 - שיוך עוד מספר צמתים]]
===קידוד ופענוח===
עבור מחרוזת <math>x</math> כלשהי, נניח ש-<math>M_1, M_2, \ldots</math> הן התוכניות שיסתיימו ויפלטו את <math>x</math>. נניח ש-<math>h</math> הוא הגובה הנמוך ביותר אליו יוחלט לשייך אחת מתוכניות אלו בעץ החיפוש (כלומר, מסתיימת תוכנית בעלת אורך <math>h - 1</math> המייצרת את <math>x</math>, ומשייכים תוכנית זו לצומת פנוי ברמה <math>h</math>). נשים לב לשתי נקודות:
שורה 85:
קידוד <math>x</math> יורכב מתיאור סכמת בניית עץ השיוך, ותיאור המסלול לאותו צומת בגובה <math>h</math>.
סכמת הפענוח פשוטה מאד: בהנתן סכמת בניית עץ השיוך, ותיאור המסלול, מריצים את בניית עץ השיוך עד שהצומת המתאים משוייך למכונה <math>M</math>. מריצים את <math>M</math> עד לקבלת <math>x</math>.
===פיענוח===
|