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

ראינו בכיתה רדוקציה מ- 3-SAT ל- Subset Sum. בהוכחת נכונות הרדוקציה התאמנו בין השמה מספקת לנוסחה שבקלט לבין מספ…

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

נוסח השאלה

ראינו בכיתה רדוקציה מ- 3-SAT ל- Subset Sum. בהוכחת נכונות הרדוקציה התאמנו בין השמה מספקת לנוסחה שבקלט לבין מספרים בפלט שסכומם הוא הסכום הנדרש. נניח שהקלט לרדוקציה הוא הנוסחה (x1∨x4)∧(x1∨x2∨x3)(x1\vee x4)\wedge(x1\vee x2\vee x3) ונסתכל על ההשמה המספקת שנותנת ערך True לכל ארבעת המשתנים. ההוכחה מתאימה את ההשמה הזו לקבוצת מספרים שסכומם הוא הסכום הנדרש. מה מספר המספרים בקבוצה בקבוצה זו?

  1. א5.
  2. ב3.
  3. ג4.
  4. ד6.
  5. ה7.
  6. ו8.

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

ייחוס מדויק

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

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

בחינה

2024 א׳ · מועד א׳

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

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

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

מטלהבשאלה זו נוכיח כי בעיית Bin-Packing שראינו בשיעור היא NP-שלמה. הקלט הוא סדרת מספרים a 1,a 2, ,a n (0,1] ומספר טבעי k. השאלה היא האם ניתן לחלק את המספר…דומה בנושא — לא כפילותמטלהבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…דומה בנושא — לא כפילותמטלהיהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-A? לדוגמה, ב…דומה בנושא — לא כפילותמטלהנגדיר את בעיית IS: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיימת ב-G קבוצה בלתי תלויה בגודל לפחות k? 1. נתונה הרדוקציה הבאה מ-SAT. לכל…דומה בנושא — לא כפילותמטלהמולטיגרף הוא גרף לא מכוון שעשויות להיות בו קשתות מקבילות ולולאות. הקלט לבעיית Max-Cut-Multi הוא מולטיגרף G=(V,E) ומספר טבעי k, והשאלה היא האם קיים חתך…דומה בנושא — לא כפילותמטלהבכל אחד מן הסעיפים הבאים מוצגות טענה ואלגוריתם. קבעו בכל סעיף האם האלגוריתם המוצג מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את טענותיכם. מ…דומה בנושא — לא כפילות

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