תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←שימוש להוכחת חסם תחתון על סיבוכיות מציאת פלינדרום: קישורים פנימיים |
|||
שורה 243:
==יישום: אורך רצפים בסדרות בינאריות רנדומיות==
נניח מחרוזת בינרית <math>x</math> שאורכה הוא <math>n =|x|</math>. מה אורכי הרצפים של אפסים ואחדות שאפשר לצפות למצוא במחרוזת? נשתמש במשפט שראינו לעיל, לפיו רוב המחרוזות אינן דחיסות ביותר מ-<math>p</math> קבוע כלשהו, כדי לענות על כך.
<math>x</math> שאורכה הוא▼
<math>n =|x|</math>.▼
}}
{{הוכחה|1=
נניח בשלילה שיש רצף כזה, ובפרט שמחרוזת היא מהצורה
<math>x = u0^{2 \log(n)} v</math>.
נוכל לתאר את
באופן הבא:
# תיאור אורך <math>u</math> -
# תיאור <math>u</math> -
# תיאור <math>v</math> (נשים לב שאנו יודעים היכן <math>u</math> מסתיימת) -
# תיאור איבר הרצף, כלומר "0" או "1" -
# תיאור מ"ט הכותבת את <math>u</math>, את הרצף, ולאחריה את <math>v</math> -
נקבל
▲{{טענה|תוכן=
<center><math> K(x) \leq n - 2 \log(n) + \log(n) + o(\log(n)) \leq n - p</math></center>
▲אם סדרה איננה דחיסה ביותר מ-<math>p</math> קבוע כלשהו, אז
מה שמראה שהסדרה דווקא דחיסה.
}}
|