שאלת רב־ברירה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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.
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
2023 B · moed B
נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf
Question 11Page 6Visual reading
Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf
View source scan — page 6
Open full size