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

נזכר בדרדוקציה SAT P dHP שהראינו בכיתה. נניח שהנוסחה שבקלט יש 100 פסוקיות שכל אחת מהן מכילה 3 ליטרלים ממשתנים…

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

נוסח השאלה

נזכר בדרדוקציה SAT≤PdHPSAT \le_P dHP שהראינו בכיתה. נניח שהנוסחה שבקלט יש 100 פסוקיות שכל אחת מהן מכילה 3 ליטרלים ממשתנים שונים (אך כמובן שפסוקיות שונות עשויות להכיל ליטרלים מאותם משתנים). נניח גם שהנוסחה ספיקה במובן Not All Equal (NAE). נסמן ב- M את מספר מסלולי ההמילטון בפלט הרדוקציה. מה הטענה החזקה ביותר הידועה נכונה?

  1. אM≥2^32.
  2. בM≥2^2.
  3. גM≥2^4.
  4. דM≥2^8.
  5. הM≥2^16.
  6. וM≥2^64.

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

ייחוס מדויק

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

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

בחינה

2023 ב׳ · מועד א׳

נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.pdf

שאלה 12עמוד 11קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 1.pdf

הצגת צילום המקור — עמוד 11עמוד מקור 11 מתוך נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.pdf פתיחה בגודל מלא
תרגול המשך

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

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