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