תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←התכנות בניית עץ השיוך: הרחבה |
|||
שורה 209:
====התכנות בניית עץ השיוך====
{{להשלים}}
{{בעבודה}}
ב[[#בניית עץ השיוך|בניית עץ השיוך]] הנחנו שאם אנו בונים את העץ לפי הכללים, אז בכל פעם שמסתיימת תוכנית <math>M_k</math>, אם <math>n_k</math> התעדכן כלפי מטה, אז יש צומת פנוי ברמה <math>n_k + 1</math>. מדוע זה נכון?
ראשית נוכיח את המשפט הבא:
{{משפט|תוכן=
עבור מחרוזת <math>x</math>, נניח ש-<math>J(x)</math> היא קבוצת האינדקסים בהם <math>n_j(x)</math> התעדכן כלפי מטה. אז
<center><math> \forall_x \sum_{j \;|\; j \in J(x)}|\Sigma|^{-n_j(x) + 1} \leq P_U(x) </math></center>
}}
{{הוכחה|תוכן=
גגג
}}
| |||