תרגיל

הפרדת מחלקות זמן דטרמיניסטיות

יישום משפט היררכיית הזמן עם תנאי בנייה ותקורת הלוגריתם.

מקורות מטלות

מטלות סמסטר א׳ 2026מטלה רשמיתexercise1.pdfQ2מסמך קורס סמכותי

מטלות סמסטר ב׳ 2026מטלה רשמיתassignment1.pdfQ2מסמך קורס סמכותי

הכנה איכותית למבחן ופתרונות קהילתיים — נוי 2025פתרון קהילתיפתרון מטלה 1 - סיבוכיות .pdfQ2הכנה איכותית ופתרון קהילתי — אינו מקור רשמי

הכנה איכותית למבחן ופתרונות קהילתיים — נוי 2025פתרון קהילתיפתרון מטלה 2 - סיבוכיות.pdfAssignment 2הכנה איכותית ופתרון קהילתי — אינו מקור רשמי

מופעים קשורים בבחינות ובמטלות

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

q-094cda9f78201. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:0 בחינות · 1 מטלות · שיעורים 1, 2, 3, 10, 14, 15, 16, 17, 18 q-34013fa0f4cfחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שהיא מובנת במלואה. השתמשו בה כדי להוכיח באופן מלא את משפט היררכיית הזמן. תהיינה f,g: N N. נניח…0 בחינות · 1 מטלות · שיעורים 1, 2, 3, 10, 17, 18 q-9294ff2ef2b4חזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שההוכחה מובנת לכם במלואה. השתמשו בכך כדי להוכיח באופן מלא את משפט היררכיית הזמן. **משפט:** תהיי…0 בחינות · 1 מטלות · שיעורים 1, 2, 3, 10, 14, 15, 16, 17, 18 q-fb073477e316תהי f פונקציה ניתנת לבניית זמן, ותהי g=o(f). נגדיר את שפת האלכסון המרופדת0 בחינות · 1 מטלות · שיעורים 1, 2, 3, 4, 5, 6, 7, 10, 17, 18

שאלה

השתמשו במשפט היררכיית הזמן הדטרמיניסטית כדי להוכיח

\mathrm{DTIME}(n^2)\subsetneq\mathrm{DTIME}(n^3).

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

דרישות קדם

נדרשת שליטה בהגדרות היחידה ובניתוח אורכי קידוד. יש להבחין בין טענה מותנית, רדוקציה ואלגוריתם.

רמז 1

השתמשו בתנאי $t_1(n)\log t_1(n)=o(t_2(n))$ .

רמז 2

פולינומים בחזקה שלמה לפחות אחת ניתנים לבנייה בזמן.

רמז 3

שעון עוצר סימולציה שאינה מסתיימת.

החסם המדומה t₁(n) = n²חסם מכונת האלכסון t₂(n) = n³

הריפוד גורם לכל מכונה לחזור

לאותה מכונה יש קלטים ארוכים כרצוננו, ולכן בסופו של דבר יש לשעון מקום

⟨M₃⟩10⁰⟨M₃⟩10¹⟨M₃⟩10²⟨M₃⟩10³…

טרם הורצה

פתרון מלא

נשתמש בנוסח הבא: אם $t_1,t_2$ ניתנות לבנייה בזמן, $t_2(n)\ge n$ , וגם

t_1(n)\log t_1(n)=o(t_2(n)),

אז $\mathrm{DTIME}(t_1)\subsetneq\mathrm{DTIME}(t_2)$ . גורם הלוגריתם משלם על סימולציה אוניברסלית וניהול השעון.

נבחר $t_1(n)=n^2$ ו- $t_2(n)=n^3$ . שתיהן ניתנות לבנייה בזמן באמצעות מונים מקוננים. נוסף לכך,

\frac{n^2\log(n^2)}{n^3}=\frac{2\log n}{n}\to0.

לכן המשפט נותן מיד הכלה ממש.

מנגנון ההוכחה הוא אלכסון על מנגנונים דטרמיניסטיים עם שעון. בקלט המקודד מכונה וריפוד, מכונה אוניברסלית מדמה את המכונה המקודדת על אותו קלט לכל היותר $t_1(n)$ צעדים והופכת את תשובתה. קלט פגום מטופל בהחלטה קבועה, והשעון מבטיח עצירה גם כשהמכונה המדומה אינה עוצרת. עלות הסימולציה היא $O(t_1\log t_1)$ ולכן נכנסת ב- $O(t_2)$ ; אורכים קצרים סופיים ניתנים לקידוד קשיח.

אילו שפת האלכסון הייתה ב- $\mathrm{DTIME}(t_1)$ , מכונה כלשהי ברשימה הייתה מכריעה אותה. על קידוד עצמי מרופד ארוך מספיק, מכונת האלכסון הייתה מקבלת אם ורק אם אותה מכונה דוחה, בסתירה לכך שהן מכריעות אותה שפה. מכאן קיימת שפה ב- $\mathrm{DTIME}(n^3)$ שאינה ב- $\mathrm{DTIME}(n^2)$ . ההכלה הלא־ממשית ברורה כי זמן $O(n^2)$ הוא גם $O(n^3)$ .

נקודות בדיקה

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

טעויות נפוצות

בדיקת $t_1=o(t_2)$ בלבד.
אלכסון על מכונות ללא שעון.
ייחוס ההפרדה לבעיה טבעית מסוימת.

מקורות ואימות

Merged summary, pp. 12-17 and p. 23
2026 transcripts 3-4
Sipser 3e, sec. 9.1
Arora-Barak draft, sec. 3.1
מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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

פתיחה בגלריית ההמחשות: אלכסון במשפט היררכיית הזמן