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

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

עריכה

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


הפתרון

מספר המחרוזות באורך   הוא  . מספר מ"ט שתיאורן קצר מאשר   הוא  . המשפט מתקבל ע"י חיסור שני ביטויים אלה עם מעט פישוטים.


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

עריכה

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

הוכח שמתקיים

 

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


הפתרון

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

  1. נקח את הייצוג בא"ב של  , ונרשום כל תו פעמיים - זה יצריך   תווים.
  2. נשתמש ברצף שני התווים   כדי לסמן שכאן נגמר תיאור אורך המספר - זה מצריך   תווים.
  3. נתאר את המספר - זה מצריך   תווים.
  4. נתאר את   - זה מצריך   תווים.
  5. נתאר את הסכמה בעזרת   תווים.


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

עריכה

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

  1.  
  2.  

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