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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
←‏קידוד: הרחבה
Atavory (שיחה | תרומות)
←‏קידוד: הרחבה
שורה 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>.
 
===פיענוח===