Complexity Atlas
HE
Source-backed question

נגדיר את בעיית האופטימיזציה הבאה, WMAXSAT. קלט: נוסחה φ בצורת CNF שבה בכל הסגר מופיעים 3 משתנים שונים בדיוק. ו…

1Exams0Assignments0Lessons1Source documents
שאלה פתוחהq-40819eab12e9

נוסח השאלה

נגדיר את בעיית האופטימיזציה הבאה, WMAXSAT. קלט: נוסחה φφ בצורת CNF שבה בכל הסגר מופיעים 3 משתנים שונים בדיוק. ופונקציית משקל w המתאימה משקל חיובי לכל הסגר בנוסחה. מטרה: למצוא השמה המקיימת כי משקל ההסגרים המסופקים הוא מקסימלי. יהי φ,wφ, w קלט לבעיה, ונסמן ב W את סך כל המשקלים בגרף, כלומר,W=ΣC∈φw(C), W = Σ_{C\in φ} w(C). מהו הערך הגדול ביותר α∈[0,1]α \in [0,1] עבורו ידוע שקיימת השמה שבה משקל ההסגרים המסופקים הוא לפחות αWαW ! שימו לב כי עבור הערך שתבחרו יש להוכיח כי לכל קלט קיימת השמה קלט כדרוש, וגם קיים קלט עליו לא קיימת השמה המספקת משקל גדול יותר של הסגרים.

תמלול ראשון מתוך עמוד המקור ב־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

2025 C · moed B

shalon_131111_2025_s3_g06_moed2.pdf

Question 3Page 23Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111106 שנה 2025 סמסטר 3 מועד 2.pdf

View source scan — page 23Source page 23 from shalon_131111_2025_s3_g06_moed2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Lesson5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…Topically related — not a duplicateAssignmentבשאלה זו נוכיח כי בעיית Bin-Packing שראינו בשיעור היא NP-שלמה. הקלט הוא סדרת מספרים a 1,a 2, ,a n (0,1] ומספר טבעי k. השאלה היא האם ניתן לחלק את המספר…Topically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…Topically related — not a duplicateAssignmentקלט: קבוצה U, אוסף \F 1, ,F m\ של m תתי-קבוצות של U, שכל אחת מהן בגודל 3, ומספר טבעי k. שאלה: האם קיימת קבוצה S U, בגודל |S|=k, המקיימתTopically related — not a duplicateAssignment1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…Topically related — not a duplicateAssignment1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה. 1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסח…Topically related — not a duplicate

Near variants — not duplicates