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

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

רוב המחרוזות אינן דחיסות במיוחד[עריכה]

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



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

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

הוכח שמתקיים

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



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

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

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