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

נניח שהקלט ברדוקציה מ- SAT ל- 3-SAT שראינו בכיתה מכיל פסוקית אחת בלבד ופסוקית זו מכילה 6 ליטרלים ממשתנים שונים…

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

נוסח השאלה

נניח שהקלט ברדוקציה מ- SAT ל- 3-SAT שראינו בכיתה מכיל פסוקית אחת בלבד ופסוקית זו מכילה 6 ליטרלים ממשתנים שונים. נסמן ב−α- α את מספר הליטרלים הכולל בפלט הרדוקציה וב−β- β את מספר המשתנים הכולל בפלט הרדוקציה. מה הערכים הנכונים של αα ו−β-β?

  1. אβ=9, α=12.
  2. בβ=8, α=10.
  3. גβ=8, α=12.
  4. דβ=9, α=10.
  5. האו שמתקיים {10,12}∈α או שמתקיים {8,9}∈β (אבל לא שניהם).
  6. ו{10,12}∉α וגם {8,9}∉β.

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

ייחוס מדויק

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

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

בחינה

2024 א׳ · מועד א׳

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

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

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

מטלהיהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-A? לדוגמה, ב…דומה בנושא — לא כפילותמטלהמולטיגרף הוא גרף לא מכוון שעשויות להיות בו קשתות מקבילות ולולאות. הקלט לבעיית Max-Cut-Multi הוא מולטיגרף G=(V,E) ומספר טבעי k, והשאלה היא האם קיים חתך…דומה בנושא — לא כפילותמטלהבכל אחד מן הסעיפים הבאים מוצגות טענה ואלגוריתם. קבעו בכל סעיף האם האלגוריתם המוצג מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את טענותיכם. מ…דומה בנושא — לא כפילותמטלה1. נוסחה בוליאנית מצורת kCNF היא ספיקה במובן NAE ‏(Not\ All\ Equal) אם קיימת השמה שעבורה בכל פסוקית יש ליטרל שערכו True וליטרל שערכו False. תהא kNAE ש…דומה בנושא — לא כפילותמטלה1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…דומה בנושא — לא כפילותמטלהנגדיר את בעיית IS: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיימת ב-G קבוצה בלתי תלויה בגודל לפחות k? 1. נתונה הרדוקציה הבאה מ-SAT. לכל…דומה בנושא — לא כפילות