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