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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 174:
 
====התכנות בניית עץ השיוך====
 
נניח שבשלב כלשהו מסתיימת תוכנית <math>M</math>. הנחנו שיש צומת פנוי ברמה
<math>|\langle M \rangle| + 1</math>. מהיכן אנו יודעים שהדבר נכון?
 
{{הוכחה|1=
נגדיר כ-<math>h</math> את אורך התוכנית הארוכה ביותר שהסתיימה בזמן ש-<math>M</math> הסתיימה (כולל <math>M</math> עצמה). נגדיר כ-<math>n</math> את מספר התוכניות שהסתיימו. קומבינטורית,
<math>
n
\leq
\frac
{
|\Sigma|^h - 1
}
{
|\Sigma| - 1
}
</math>
 
ולכן נניח <math>
n
=
\frac
{
|\Sigma|^h - 1
}
{
|\Sigma| - 1
}
</math>
 
{{להשלים}}