לדלג לתוכן

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

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

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

[עריכה]

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


הפתרון

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


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

[עריכה]

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

הוכח שמתקיים

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


הפתרון

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

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


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

[עריכה]

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

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