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