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

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