מפת הבחינות

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

1. 1
   3 מועדיםשאלות סגורות2025–2026התאמה מחושבת

   נסמן C 1= c 1DTime (n (2 c) ), C 2=DTime (2 (n 6) ), C 3= c 1DTime (n n c ). איזו מהטענות הבאות היא החזקה ביותר הידועה כנכונה.

   • 2026 סמסטר ב׳ מועד א׳שאלה 3נבדק
   • 2026 סמסטר ב׳ מועד ב׳שאלה 7תומלל1
   • 2025 סמסטר קיץ מועד ב׳שאלה 1תומלל1

   צילומי המקור (2)· מועד אחד ללא צילום

   2026 סמסטר ב׳ מועד ב׳ · עמוד 112025 סמסטר קיץ מועד ב׳ · עמוד 3

   זמן, מקום ומחלקותשיעורים 2, 3, 18
2. 2
   3 מועדיםשאלות סגורות2023–2026התאמה מחושבת

   עבור 0< <1 נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A * עבורן קיימת מכונת טיורינג דטרמיניסטית M וקיים פולינום p כך שלכל x *, M רצה על x בזמן לכל היותר p(|x|) וכמו כן לכל x *, אם x A אז r \0,1\ p(|x…

   • 2026 סמסטר ב׳ מועד א׳שאלה 6נבדק
   • 2026 סמסטר ב׳ מועד ב׳שאלה 5תומלל1
   • 2023 סמסטר ב׳ מועד א׳שאלה 4תומלל1

   צילומי המקור (2)· מועד אחד ללא צילום

   2026 סמסטר ב׳ מועד ב׳ · עמוד 72023 סמסטר ב׳ מועד א׳ · עמוד 5

   מכונות טיורינג ומודליםNP, מוודאים ואי-דטרמיניזםאקראיות והסתברותשיעורים 1, 2, 4, 5, 12, 13
3. 3
   2 מועדיםשאלות פתוחות2025–2026התאמה מחושבת

   תהאנה A,B Σ* שפות. רדוקציית זמן מעריכי מ A ל B היא מכונת טיורינג דטרמיניסטית M המקיימת את שתי התכונות הבאות. ● קיים c 1 כך שלכל x Σ* מתקיים timeM(x) O(2 |x| c). ● לכל x Σ* מתקיים x A אם ורק אם M(x) B. עבור כל אחת מהטענות…

   • 2026 סמסטר ב׳ מועד ב׳שאלה 2תומלל2
   • 2025 סמסטר קיץ מועד א׳שאלה 2תומלל1

   צילומי המקור (3)

   2026 סמסטר ב׳ מועד ב׳ · עמוד 232026 סמסטר ב׳ מועד ב׳ · עמוד 272025 סמסטר קיץ מועד א׳ · עמוד 17

   מכונות טיורינג ומודליםרדוקציות וקוק־לויןשיעורים 1, 2, 6, 7
4. 4
   2 מועדיםשאלות סגורות2026התאמה מחושבת

   נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A * עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים פולינום p כך שלכל x *, אם x A אז כל ריצה של M על x מקבלת ועוצרת אחרי לכל היותר p(|x|) צעדים, וגם אם x A…

   • 2026 סמסטר ב׳ מועד א׳שאלה 8נבדק
   • 2026 סמסטר ב׳ מועד ב׳שאלה 6תומלל1

   צילומי המקור (1)· מועד אחד ללא צילום

   2026 סמסטר ב׳ מועד ב׳ · עמוד 9

   מכונות טיורינג ומודליםNP, מוודאים ואי-דטרמיניזםשיעורים 1, 2, 4, 5
5. 5
   2 מועדיםשאלות סגורות2024–2025התאמה מחושבת

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

   • 2025 סמסטר א׳ מועד א׳שאלה 1תומלל1
   • 2024 סמסטר א׳ מועד א׳שאלה 2תומלל1

   צילומי המקור (2)

   2025 סמסטר א׳ מועד א׳ · עמוד 32024 סמסטר א׳ מועד א׳ · עמוד 3

   מכונות טיורינג ומודליםזמן, מקום ומחלקותרדוקציות וקוק־לויןשיעורים 1, 2, 3, 6, 7, 18
6. 6
   2 מועדיםשאלות סגורות2025התאמה מחושבת

   נתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיימים c 1 כך שלכל x Σ*, אם x A אז קיימת ריצת M על x העוצרת אחרי לכל היותר |x| c צעדים, וגם אם x A אז בכל רי…

   • 2025 סמסטר קיץ מועד א׳שאלה 7תומלל1
   • 2025 סמסטר קיץ מועד ב׳שאלה 4תומלל1

   צילומי המקור (2)

   2025 סמסטר קיץ מועד א׳ · עמוד 92025 סמסטר קיץ מועד ב׳ · עמוד 7

   מכונות טיורינג ומודליםזמן, מקום ומחלקותNP, מוודאים ואי-דטרמיניזםשיעורים 1, 2, 3, 4, 5, 18
7. 7
   2 מועדיםשאלות פתוחות2025התאמה מחושבת

   נגדיר את בעיית האופטימיזציה הבאה, WMAXSAT. קלט: נוסחה φ בצורת CNF שבה בכל הסגר מופיעים 3 משתנים שונים בדיוק. ופונקציית משקל w המתאימה משקל חיובי לכל הסגר בנוסחה. מטרה: למצוא השמה המקיימת כי משקל ההסגרים המסופקים הוא מקסי…

   • 2025 סמסטר קיץ מועד א׳שאלה 3תומלל1
   • 2025 סמסטר קיץ מועד ב׳שאלה 3תומלל1

   צילומי המקור (2)

   2025 סמסטר קיץ מועד א׳ · עמוד 212025 סמסטר קיץ מועד ב׳ · עמוד 23

   NP, מוודאים ואי-דטרמיניזםאלגוריתמי קירובשיעורים 4, 5, 9, 10, 11
8. 8
   2 מועדיםשאלות סגורות2025התאמה מחושבת

   עבור 1<α<0 נתונות מחלקות הסתביכויות הבאות. I. המחלקה C 1 היא כל השפות A Σ* עבורן קיימת מכונת טיורינג דטרמיניסטית M הרצה בזמן פולינומי בגודל הקלט x Σ*, כך שלכל אם x A אז Pr r 0,1 p(|x|) [M(x,r) accepts] α וגם אם x A אז Pr…

   • 2025 סמסטר קיץ מועד א׳שאלה 6תומלל1
   • 2025 סמסטר קיץ מועד ב׳שאלה 3תומלל1

   צילומי המקור (2)

   2025 סמסטר קיץ מועד א׳ · עמוד 72025 סמסטר קיץ מועד ב׳ · עמוד 5

   מכונות טיורינג ומודליםאקראיות והסתברותשיעורים 1, 2, 12, 13
9. 9
   2 מועדיםשאלות סגורות2023–2024התאמה מחושבת

   ע"י המחלקה NP CoNP", ניתן להתמקד, לשם פשטות, בפונקציות הצפנה f משמרות- אורך f:0,1 n 0,1 n, ומגדירים שפה מתאימה L. חיוני שהפונקציה f תהיה חח"ע כדי:

   • 2024 סמסטר קיץ מועד א׳שאלה 2תומלל1
   • 2023 סמסטר קיץ מועד א׳שאלה 5תומלל1

   צילומי המקור (2)

   2024 סמסטר קיץ מועד א׳ · עמוד 32023 סמסטר קיץ מועד א׳ · עמוד 5

   NP, מוודאים ואי-דטרמיניזםמקום לוגריתמי ו-NLשיעורים 4, 5, 14, 15, 16, 17
10. 10
    2 מועדיםשאלות סגורות2024התאמה מחושבת

    נתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נוסחה φ מצורת 3-CNF עם m הסנרים נחזיר גרף G ואת המספר m. הגרף G יונדר כל…

    • 2024 סמסטר א׳ מועד א׳שאלה 7תומלל1
    • 2024 סמסטר א׳ מועד ב׳שאלה 7תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 72024 סמסטר א׳ מועד ב׳ · עמוד 4

    NP, מוודאים ואי-דטרמיניזםרדוקציות וקוק־לויןבעיות NP-שלמותשיעורים 4, 5, 6, 7, 8
11. 11
    2 מועדיםשאלות סגורות2024התאמה מחושבת

    נסתכל על 3 הבעיות הבאות: בעיית ההכרעה של SAT: בהינתן נוסחה בוליאנית בצורת CNF – האם הנוסחה ספיקה. בעיית החיפוש של SAT: בהינתן נוסחה בוליאנית בצורת CNF – למצוא השמה מספקת אם יש כזו או להודיע "לא" אם אין לנוסחה השמה מספקת.…

    • 2024 סמסטר א׳ מועד א׳שאלה 9תומלל1
    • 2024 סמסטר א׳ מועד ב׳שאלה 9תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 72024 סמסטר א׳ מועד ב׳ · עמוד 5

    מכונות טיורינג ומודליםNP, מוודאים ואי-דטרמיניזםשיעורים 1, 2, 4, 5
12. 12
    2 מועדיםשאלות סגורות2024התאמה מחושבת

    בהוכחת משפט קוק-לוין שראינו בשיעור, ייצגנו ריצה של מכונה M על קלט (x,w) על ידי טבלה T M,x. במהלך ההוכחה, בנינו טבלאות אמת עבור תאים שונים בטבלה והמרנו אותן לצורת CNF. נניח שמספר המצבים ב- M הוא 10 ושמספר התוויים בא"ב העב…

    • 2024 סמסטר א׳ מועד א׳שאלה 6תומלל1
    • 2024 סמסטר א׳ מועד ב׳שאלה 6תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 52024 סמסטר א׳ מועד ב׳ · עמוד 4

    מכונות טיורינג ומודליםNP, מוודאים ואי-דטרמיניזםרדוקציות וקוק־לויןשיעורים 1, 2, 4, 5, 6, 7
13. 13
    2 מועדיםשאלות סגורות2024התאמה מחושבת

    נתונות שלוש מחלקות סיבוכיות: C 1 = DSpace(n 5) , C 2 = NSpace(n 3) , C 3 = EXP. איזו מבין הטענות שלהלן היא הטענה החזקה ביותר אשר ידוע שהיא נכונה? (שימו לב להבדל בין הכלה להכלה ממש ⊂ ).

    • 2024 סמסטר א׳ מועד א׳שאלה 13תומלל1
    • 2024 סמסטר א׳ מועד ב׳שאלה 13תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 112024 סמסטר א׳ מועד ב׳ · עמוד 6

    זמן, מקום ומחלקותשיעורים 2, 3, 18
14. 14
    2 מועדיםשאלות סגורות2023–2024התאמה מחושבת

    תהאנה A ו- B שפות כך ש- A L B. מה המסקנה היודעה נכונה:

    • 2024 סמסטר א׳ מועד א׳שאלה 14תומלל1
    • 2023 סמסטר ב׳ מועד א׳שאלה 14תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 112023 סמסטר ב׳ מועד א׳ · עמוד 13

    זמן, מקום ומחלקותNP, מוודאים ואי-דטרמיניזםשיעורים 2, 3, 4, 5, 18
15. 15
    2 מועדיםשאלות סגורות2024התאמה מחושבת

    ראינו בהרצאה רדוקציה מ- 3-SAT ל- Subset Sum. בהוכחת נכונות הרדוקציה התאמנו בין השמה שמספקת לנוסחה שבקלט לבין מספרים בפלט שסכומם הוא הסכום הנדרש. נניח שהקלט לרדוקציה הוא הנוסחה (x1 x2) (x1 x3) ונסתכל על ההשמה המספקת שנותנ…

    • 2024 סמסטר א׳ מועד א׳שאלה 8תומלל1
    • 2024 סמסטר א׳ מועד ב׳שאלה 8תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 72024 סמסטר א׳ מועד ב׳ · עמוד 4

    NP, מוודאים ואי-דטרמיניזםרדוקציות וקוק־לויןשיעורים 4, 5, 6, 7
16. 16
    2 מועדיםשאלות סגורות2024התאמה מחושבת

    נתונות הטענות הבאות? i. אם MAX-IS NP או P = NP. ii. אם IS P אם ורק אם MAX-IS P. iii. אם IS NP אם ורק אם MAX-IS NP. תזכורת: MAX-IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k ואין בו קבוצה ב…

    • 2024 סמסטר א׳ מועד א׳שאלה 12תומלל1
    • 2024 סמסטר א׳ מועד ב׳שאלה 12תומלל1

    צילומי המקור (2)

    2024 סמסטר א׳ מועד א׳ · עמוד 112024 סמסטר א׳ מועד ב׳ · עמוד 6

    NP, מוודאים ואי-דטרמיניזםבעיות NP-שלמותשיעורים 4, 5, 8
17. 17
    2 מועדיםשאלות פתוחות2021–2023התאמה מחושבת

    3. נגדיר את בעיית המקסימיזציהC כלהלן. קלט: נוסחה בוליאנית 𝜑 מצורת2CNF שבכל הסגר שלה מופיעים שני משתנים שונים (בחיוב או בשלילה). מטרה: למצוא השמה אשר מספקת במובן NAE (Not All Equal )מספר מירבי של הסגרים בנוסחה 𝜑 . קבעו…

    • 2023 סמסטר א׳ מועד א׳שאלה 3שכבת טקסט
    • 2021 סמסטר א׳ מועד א׳שאלה 3שכבת טקסט

    זמן, מקום ומחלקותNP, מוודאים ואי-דטרמיניזםאלגוריתמי קירובמקום לוגריתמי ו-NLשיעורים 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15, 16, 17, 18, 20
18. 18
    2 מועדיםשאלות סגורות2022–2023התאמה מחושבת

    5. תהא C1 מחלקת השפותA ⊆ Σ∗ עבורן קיימים פולינום𝑝 ומכונת טיורינג דטרמיניסטיתM עם זמן ריצה פולינומיאלי כך שלכל 𝑥 ∈ Σ∗ מתקיים • אם 𝑥 ∈ A אז Pr𝑟[M(𝑥, 𝑟) = T] = 1, • ואם 𝑥 ∉ A אז Pr𝑟[M(𝑥, 𝑟) = T] < 2−𝑝(|𝑥|), כאשר…

    • 2023 סמסטר א׳ מועד ב׳שאלה 8שכבת טקסט
    • 2022 סמסטר א׳ מועד א׳שאלה 5שכבת טקסט

    מכונות טיורינג ומודליםזמן, מקום ומחלקותNP, מוודאים ואי-דטרמיניזםאקראיות והסתברותשיעורים 1, 2, 3, 4, 5, 6, 7, 10, 12, 13, 14, 18
19. 19
    2 מועדיםשאלות פתוחות2023התאמה מחושבת

    1. קבעו האם הטענה שלהלן נכונה, אינה נכונה, אושקולה לשאלה פתוחה. הוכיחו קביעתכם. אין להשתמש בטענות או בתרגילים מהקורס מבלי להוכיח אותם. טענה: לכל שתי שפות A ∈ P , B ∈ coRP, מתקיים A ∪ B ∈ coRP. הטענה נכונה / אינה נכונה /…

    • 2023 סמסטר א׳ מועד א׳שאלה 1שכבת טקסט
    • 2023 סמסטר א׳ מועד ב׳שאלה 1שכבת טקסט

    NP, מוודאים ואי-דטרמיניזםאקראיות והסתברותשיעורים 4, 5, 6, 7, 12, 13, 14
20. 20
    2 מועדיםשאלות סגורות2023התאמה מחושבת

    3. נתונות שלוש מחלקות סיבוכיות .D1 = ⋃ DTime(2(𝑛𝑐)) 𝑐≥1 , D2 = ⋃ DTime(2(𝑐𝑛)) 𝑐≥1 , D3 = ⋃ DTime(𝑐(2𝑛)) 𝑐≥1 איזו מהטענות שלהלן נכונה (שימו לב: הסימון ⊊ מציין "הכלה ממש א. D1 = D2 = D3 ב. D1 = D2 ⊊ D3 ג. D1 ⊊ D2…

    • 2023 סמסטר א׳ מועד א׳שאלה 3שכבת טקסט
    • 2023 סמסטר א׳ מועד ב׳שאלה 4שכבת טקסט

    זמן, מקום ומחלקותמשפטי היררכיה ולכסוןשיעורים 1, 2, 3, 10, 18
21. 21
    2 מועדיםשאלות פתוחות2020התאמה מחושבת

    3. תהאsuperNP מחלקת השפות A ⊆ Σ∗ עבורן קיימת מכונת טיורינג (דטרמיניסטית) M עם זמן ריצה פולינומיאלי כך שלכל 𝑥 ∈ Σ∗ מתקיים𝑥 ∈ A ⟺ ∃𝑤 ∈ 0,1∗. M(𝑥, 𝑤) = True. א. במה שונה הגדרת המחלקה superNP מהגדרת המחלקה NP (המבוססת ע…

    • 2020 סמסטר ב׳ מועד א׳שאלה 3שכבת טקסט
    • 2020 סמסטר ב׳ מועד מיוחדשאלה 3שכבת טקסט

    מכונות טיורינג ומודליםזמן, מקום ומחלקותNP, מוודאים ואי-דטרמיניזםשיעורים 1, 2, 3, 4, 5, 6, 7, 10, 18
22. 22
    2 מועדיםשאלות פתוחות2020התאמה מחושבת

    2. עבור שפהA נגדיר את בעיית ההכרעה Odd-A כלהלן קלט: מספר טבעי 𝑘 (בייצוג בינאריואוסף מחרוזות 𝑥1, 𝑥2, … , 𝑥𝑘. שאלה: האם מספר המחרוזות 𝑥𝑖 (1 ≤ 𝑖 ≤ 𝑘) שמקיימות𝑥𝑖 ∈ A הואאי-זוגי? קבעו האם הטענה שלהלן נכונה, אינה נכ…

    • 2020 סמסטר ב׳ מועד ב׳שאלה 2שכבת טקסט
    • 2020 סמסטר ב׳ מועד מיוחדשאלה 2שכבת טקסט

    מקום לוגריתמי ו-NLשיעורים 14, 15, 16, 17, 18, 20
23. 23
    2 מועדיםשאלות סגורות2020התאמה מחושבת

    3. נגדיר את בעיית ההכרעהA שלהלן קלט: ייצוג ⟨M⟩ של מכונת טיורינגM עםא"ב עבודה Σ = 0,1,2,3, B. שאלה האם M מקבלת את ⟨M⟩ וגם𝑠𝑝𝑎𝑐𝑒M(⟨M⟩) ≤ |⟨M⟩|3 ? איזו מבין מחלקות הסיבוכיות שלהלן היא הקטנה ביותרביחס להכלה אליה ידוע שהש…

    • 2020 סמסטר ב׳ מועד ב׳שאלה 2טופס 011/022/033/044שכבת טקסט
    • 2020 סמסטר ב׳ מועד מיוחדשאלה 3שכבת טקסט

    מכונות טיורינג ומודליםזמן, מקום ומחלקותNP, מוודאים ואי-דטרמיניזםרדוקציות וקוק־לויןאלגוריתמי קירובשיעורים 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 18