שאלת רב־ברירהq-60616f088ccf
נוסח השאלה
להזכירכם מהכרטיע לקלט הבעיה Subset-Sum הוא S קבוצת מספרים ו-t סכום יעד (כולל בייצוג בינארי) והשאלה היא האם קיימת תמית קבוצה חלקית S' של S שסכומה t. לפניכם תיאור של פונקציה החשיבה בזמן פולינומי. מהו הם ערכי x ו-y כך שהפונקציה תהיה רדוקציה מ-3SAT ל-Subset Sum? תיאור הפונקציה: על קלט נוסחת 3CNF בצורה חנ"ל עם n משתנים ו-m פסוקיות הרדוקציה פולטת קבוצת מספרים S ומספר t סוף ck: מספר הספרות בכל אחד מהמספרים ב-S וגם במספר t הוא m+n. עבור כל אחד מ-2n הליטרלים השונים האפשריות מעל המשתנה של הנוסחה יש מספר ב-S. למספר יש ספרה עבור כל משתנה ופרה עבור כל פסוקית. ספרת המשתנה היא 1 אם הליטרל נוצר מהמשתנה. אחרת ספרת המשתנה היא 0. ספרת הפסוקית היא 3 אם הליטרל מופיע בפסוקה. אחרת ספרת הפסוקית היא 0. לכל פסוקית y ש מספרים x עם ספרה 1 במקום הפסוקית ושאר הספרות הוא 0. ולבסוף: במספר t יש הספרה 1 בכל מקום של משתנה וספרות המשתנה בכל מקום y הספרה.
תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.
ייחוס מדויק
מופעים לפי מסמך מקור
כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.
בחינה
2023 ב׳ · מועד ב׳
נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf
שאלה 11עמוד 6קריאה חזותית
עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf
הצגת צילום המקור — עמוד 6
פתיחה בגודל מלא