Complexity Atlas
HE
Source-backed question

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

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירה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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Exam

2024 A · moed A

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

Question 8Page 7Visual reading
View source scan — page 7Source page 7 from נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

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

Near variants — not duplicates