תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←קידוד ופענוח: עריכה |
←התכנות בניית עץ השיוך: הרחבה |
||
שורה 188:
עבור מחרוזת <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>
}}
{{הוכחה|
עפ"י ההגדרה,
<center><math>
min_{j \in J} |\Sigma|^{-(n_j(x) + 1)} = |\Sigma|^{-(P_U(x) + 1)}
</math></center>
היות שאף תוכנית איננה מופיעה פעמיים באותה רמה בעץ, אז כל ה-<math>n_j</math> נפרדים. לכן נקבל:
<center><math>
\forall_x \sum_{j \;|\; j \in J(x)}|\Sigma|^{-(n_j(x) + 1)}
\leq
\sum_{j = 0, 1, 2, \ldots}|\Sigma|^{-(P_U(x) + j + 1)}</math></center>
נפשט את הטור האינסופי:
<center><math>
\sum_{j = 0, 1, 2, \ldots}|\Sigma|^{-(P_U(x) + j + 1)}
=
|\Sigma|^{-(P_U(x) + 1)} \sum_{j = 0, 1, 2, \ldots}|\Sigma|^{-j}
=
\frac{|\Sigma|}{|\Sigma| - 1} |\Sigma|^{-(P_U(x) + 1)}
\leq
|\Sigma|^{-P_U(x)}
.
</math></center>
}}
| |||