תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים
רוב המחרוזות אינן דחיסות במיוחד
עריכההוכח את משפט: אי-דחיסות משמעותית של רוב המחרוזות
הפתרון
מספר המחרוזות באורך הוא . מספר מ"ט שתיאורן קצר מאשר הוא . המשפט מתקבל ע"י חיסור שני ביטויים אלה עם מעט פישוטים.
סיבוכיות מספרים טבעיים
עריכההוא מספר טבעי כלשהו, ו היא מחרוזת. רוצים לתאר את , כלומר לתאר הן את המספר, והן את המחרוזת, כך שברור היכן המספר מסתיים והמחרוזת מתחילה.
הוכח שמתקיים
רמז: הכפל כל תו בחקל מתיאור .
הפתרון
נתאר את השרשור באופן הבא:
- נקח את הייצוג בא"ב של , ונרשום כל תו פעמיים - זה יצריך תווים.
- נשתמש ברצף שני התווים כדי לסמן שכאן נגמר תיאור אורך המספר - זה מצריך תווים.
- נתאר את המספר - זה מצריך תווים.
- נתאר את - זה מצריך תווים.
- נתאר את הסכמה בעזרת תווים.
סיבוכיות שרשרור נתן להפרדה בעזרת רכיבי הסיבוכיות הבסיסיים
עריכההראה שלכל שתי מחרוזות ו- , סיבוכיות השרשור הנתן-להפרדה מקיים:
רמז: השתמש ברעיונות מתוךתרגיל: סיבוכיות מספרים טבעיים.