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

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


זיהוי פלינדרומים[עריכה]

  1. תאר מ"ט בעלת שני סרטים המזהה פלינדרומים.
  2. תאר מ"ט בעלת סרט אחד המזהה פלינדרום.
  3. מה זמן הריצה של כ"א מהפתרונות שהצעת?

חסם לסיבוכיות זמן הריצה של מ"ט בעלת סרט יחיד[עריכה]

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


- תרגילים -