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

{{תורת החישוביות}}
==רוב המחרוזות אינן דחיסות במיוחד==

הוכח את [[תורת החישוביות/סיבוכיות קולמוגורוב#אי-דחיסות מחרוזות|משפט: אי-דחיסות משמעותית של רוב המחרוזות]]

{{מוסתר|ta2 = right|הפתרון|2=
מספר המחרוזות באורך <math>|x|</math> הוא
<math>\left| \Sigma \right|^{|x|}</math>.
מספר מ"ט שתיאורן קצר מאשר
<math>|x| - p</math>
הוא
<math>
\sum_{i = 0}^{|x| - p - 1} \left| \Sigma \right|^i = 
\frac
{
	\left| \Sigma \right|^{|x| - p} -1
}
{
	\left| \Sigma \right| - 1
}
</math>.
המשפט מתקבל ע"י חיסור שני ביטויים אלה עם מעט פישוטים.
}}

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

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

הוכח שמתקיים 
<center><math>K(n, x) \leq 2 \log(\log(n)) + \log(n) + O(1) + K(x)</math></center>
רמז: הכפל כל תו בחקל מתיאור <math>n</math>.

{{מוסתר|ta2 = right|הפתרון|2=
נתאר את השרשור באופן הבא:
# נקח את הייצוג בא"ב של <math>n</math>, ונרשום כל תו פעמיים - זה יצריך <math>2 \log(\log(n)) + O(1)</math> תווים.
# נשתמש ברצף שני התווים <math>01</math> כדי לסמן שכאן נגמר תיאור אורך המספר - זה מצריך <math>O(1)</math> תווים.
# נתאר את המספר - זה מצריך <math>\log(n)</math> תווים.
# נתאר את <math>x</math> - זה מצריך <math>K(x)</math> תווים. 
# נתאר את הסכמה בעזרת <math>O)1(</math>  תווים.
}}

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

הראה שלכל שתי מחרוזות <math>x</math> ו-<math>y</math>, [[תורת החישוביות/סיבוכיות קולמוגורוב#כלל השרשרת לסיבוכיות|סיבוכיות השרשור הנתן-להפרדה]] מקיים:
#<math>K(x,y) \leq 2 \cdot K(x) + O(1) + K(y)</math> 
#<math>K(x,y) \leq K(x) + K(y) + \Theta\left( \log(\min(K(x), K(y)) \right)</math>

רמז: השתמש ברעיונות מתוך[[#סיבוכיות מספרים טבעיים|תרגיל: סיבוכיות מספרים טבעיים]].
[[קטגוריה:תורת החישוביות]]