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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 243:
==יישום: אורך רצפים בסדרות בינאריות רנדומיות==
 
נניח מחרוזת בינרית <math>x</math> שאורכה הוא <math>n =|x|</math>. מה אורכי הרצפים של אפסים ואחדות שאפשר לצפות למצוא במחרוזת? נשתמש במשפט שראינו לעיל, לפיו רוב המחרוזות אינן דחיסות ביותר מ-<math>p</math> קבוע כלשהו, כדי לענות על כך.
נניח סדרה בינרית
<math>x</math> שאורכה הוא
<math>n =|x|</math>.
 
{{טענהמשפט|תוכן=
אם סדרהמחרוזת איננה דחיסה ביותר מ-<math>p</math> קבוע כלשהו, אז אין לה רצף באורך
<math>n2 =|x|\log(n)</math>.
}}
 
{{הוכחה|1=
נניח בשלילה שיש רצף כזה, ובפרט שמחרוזת היא מהצורה
<math>x = u0^{2 \log(n)} v</math>.
נוכל לתאר את
<math>x</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> קבוע כלשהו, אז
מה שמראה שהסדרה דווקא דחיסה.
}}