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