תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ הגהה, מעבר ממ"ט לתוכניות |
←קידוד: הרחבה |
||
שורה 77:
===קידוד===
עבור מחרוזת <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>). נשים לב לשתי נקודות:
# <math>h</math> מוגדרת היטב.
# <math>h</math> איננה נתנת לחישוב.
נניח שיש לנו אוראקל, עם זאת, המגלה לנו את <math>h</math>. במקרה זה, נוכל לחזור על תהליך בניית העץ, ונעצור ברגע שמשוייכת תוכנית המייצרת את <math>x</math> לצומת בגובה <math>h</math>.
קידוד <math>x</math> יורכב מתיאור סכמת בניית עץ השיוך, ותיאור המסלול לאותו צומת בגובה <math>h</math>.
===פיענוח===
| |||