לדלג לתוכן

תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

רוב המחרוזות אינן דחיסות במיוחד

[עריכה]

הוכח את משפט: אי-דחיסות משמעותית של רוב המחרוזות


הפתרון

מספר המחרוזות באורך |x| הוא |Σ||x|. מספר מ"ט שתיאורן קצר מאשר |x|−p הוא ∑i=0|x|−p−1|Σ|i=|Σ||x|−p−1|Σ|−1. המשפט מתקבל ע"י חיסור שני ביטויים אלה עם מעט פישוטים.


סיבוכיות מספרים טבעיים

[עריכה]

n הוא מספר טבעי כלשהו, וx היא מחרוזת. רוצים לתאר את n,x, כלומר לתאר הן את המספר, והן את המחרוזת, כך שברור היכן המספר מסתיים והמחרוזת מתחילה.

הוכח שמתקיים

K(n,x)≤2log⁡(log⁡(n))+log⁡(n)+O(1)+K(x)

רמז: הכפל כל תו בחקל מתיאור n.


הפתרון

נתאר את השרשור באופן הבא:

  1. נקח את הייצוג בא"ב של n, ונרשום כל תו פעמיים - זה יצריך 2log⁡(log⁡(n))+O(1) תווים.
  2. נשתמש ברצף שני התווים 01 כדי לסמן שכאן נגמר תיאור אורך המספר - זה מצריך O(1) תווים.
  3. נתאר את המספר - זה מצריך log⁡(n) תווים.
  4. נתאר את x - זה מצריך K(x) תווים.
  5. נתאר את הסכמה בעזרת O)1( תווים.


סיבוכיות שרשרור נתן להפרדה בעזרת רכיבי הסיבוכיות הבסיסיים

[עריכה]

הראה שלכל שתי מחרוזות x ו-y, סיבוכיות השרשור הנתן-להפרדה מקיים:

  1. K(x,y)≤2⋅K(x)+O(1)+K(y)
  2. K(x,y)≤K(x)+K(y)+Θ(log⁡(min⁡(K(x),K(y)))

רמז: השתמש ברעיונות מתוךתרגיל: סיבוכיות מספרים טבעיים.