תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 243:
==יישום: אורך רצפים בסדרות בינאריות רנדומיות==
נניח מחרוזת בינרית <math>x</math> שאורכה הוא <math>n =|x|</math>. מה אורכי הרצפים של אפסים ואחדות שאפשר לצפות למצוא במחרוזת? נשתמש במשפט שראינו לעיל, לפיו רוב המחרוזות אינן דחיסות ביותר מ-<math>p</math> קבוע כלשהו, כדי לענות על כך. מספיק שנוכיח שתכונה נובעת מכך שמחרוזת איננה דחיסה ביותר מ-<math>p</math>, כדי שהדבר יהיה נכון לרוב המחרוזות. כזכור 99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים.
{{משפט|תוכן=
אם מחרוזת איננה דחיסה ביותר מ-<math>p</math> קבוע כלשהו, אז
<math>2 \log(n)</math>.
}}
שורה 263:
נקבל
<center><math> n - p \leq K(x) \leq n - 2 \log(n) + \log(n) + o(\log(n))
מה שמראה שהסדרה דווקא דחיסה.
}}
|