מפת הסיבוכיות
EN
שאלה מבוססת מקור

שפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n 2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה…

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלת רב־ברירהq-32ebb6dcc978

נוסח השאלה

שפה A ניתנת להכרעה ע"י מכונת טיורינג דטרמיניסטית שמשתמשת במקום O(n2)O(n^2) לקלט באורך n. שפה B ניתנת לרדוקציה לשפה A ע"י מ"ט דטרמיניסטית בזמן O(n3)O(n^3) לקלט באורך n. מהי המחלקה הקטנה ביותר ביחס להכלה שאליה ידוע שהכלה שאלייה שייכת שייכת?

  1. אDTime(2^{n^{10}}).
  2. בDTime(n^2).
  3. גDTime(n^6).
  4. דDTime(n^{12}).
  5. הDTime(2^{n^2}).
  6. וDTime(2^{n^5}).

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2024 א׳ · מועד א׳

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf

שאלה 2עמוד 3קריאה חזותית
הצגת צילום המקור — עמוד 3עמוד מקור 3 מתוך נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf פתיחה בגודל מלא
תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלה1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:דומה בנושא — לא כפילותמטלהיהי אלפבית, תהיינה f,g: * * פונקציות, ותהיינה M f,M g מכונות טיורינג המחשבות את f,g, בהתאמה. תהא h: * * פונקציית ההרכבהדומה בנושא — לא כפילותמטלהעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…דומה בנושא — לא כפילותמטלהתהיינה M f,M g מכונות טיורינג אשר מחשבות את הפונקציותדומה בנושא — לא כפילותמטלהנגדיר TISP(f,g) כמחלקת השפות הניתנות להכרעה על ידי מכונת טיורינג סטנדרטית בעלת סרט יחיד בזמן O(f(n)) ובזיכרון O(g(n)). 1. קבעו איזו מן המחלקותדומה בנושא — לא כפילותמטלהחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שהיא מובנת במלואה. השתמשו בה כדי להוכיח באופן מלא את משפט היררכיית הזמן. תהיינה f,g: N N. נניח…דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות