ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
שורה 161:
====התכנות בניית עץ השיוך====
 
נניח שבצעד <math>n</math> מסתיימת תוכנית <math>M</math>. ואיןהנחנו מקוםשיש צומת פנוי ברמה▼
<math>|\langle M \rangle| + 1</math>. מהיכן אנו יודעים שהדבר נכון?
 
{{הוכחה|תוכן=
▲נניח שבצעד <math>n</math> מסתיימת תוכנית <math>M</math> ואין מקום פנוי ברמה
ההוכחה היא באינדוקציה על מספר התוכניות שהסתיימו עד <math>n</math>, נניח <math>n'</math>.
<math>|\langle M \rangle|</math>.
<math>x</math>
 
בסיס האינדוקציה: אם <math>n' = 0</math>, אז <math>M</math> היא התוכנית הראשונה המסתיימת, ובודאי שיש לה מקום פנוי בעץ.
<math>
\sum_{x \;|\; \exists} | \Sigma |^{- |\langle M(x) \rangle|} \geq 1
</math>
 
מעבר האינדוקציה: נניח שהדבר נכון עד ל<math>n' - 1</math>, ונראה שהדבר ממשיך להיות נכון ל<math>n'</math>.
 
{{להשלים}}
\right)
\leq
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\sum_{M \;|\; M(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M \rangle \right|} }
\right)
=
\log_{\left| \Sigma \right|}
\left(
\frac{1}{ P_U(x) }
\right)
</math></center>
 
{{
 
סכמת הפענוח פשוטה מאד: בהנתן סכמת בניית עץ השיוך, ותיאור המסלול, מריצים את בניית עץ השיוך עד שהצומת המתאים משוייך למכונה <math>M</math>. מריצים את <math>M</math> עד לקבלת <math>x</math>.
<br />
 
==תער אוקאם==
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/סיבוכיות_קולמוגורוב/הסתברות_אוניברסאלית"