Complexity Atlas
HE
Source-backed question

נזכיר את בעיית האריזה בתאים. קלט: n-ייה של מספרים a 1, ,a n (0,1] ומספר טבעי k . שאלה: האם קיימת חלוקה של a 1,…

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

נוסח השאלה

נזכיר את בעיית האריזה בתאים.

קלט: nn-ייה של מספרים a1,…,an∈(0,1]a_1,\ldots,a_n\in(0,1] ומספר טבעי k∈Nk\in\mathbb{N}.

שאלה: האם קיימת חלוקה של a1,a2,…,ana_1,a_2,\ldots,a_n ל-kk תאים כך שסכום המספרים בכל תא לכל היותר 1.

א. הוכיחו כי בעיית האריזה בתאים היא NPNP קשה. ב. נסחו את בעיית האופטימיזציה המתאימה לבעיית האריזה בתאים, והוכיחו כי אם קיים אלגוריתם קירוב פולינומי לבעיית האריזה בתאים עם יחס קירוב 1.49 אז P=NPP=NP.

נוסח מטלה שנבדק אנושית.

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

2026 B · moed A

מ-2026 סמסטר ב מועד א (טופס נבחן)

Question 1Page 1Human reviewed

This question has no source scan. The only surviving copy is a marked personal exam script — it carries an identity number on every page, over a student's answers and a grader's red corrections. Only the printed question text was taken from it; the handwriting, the marks and the grades are not part of the question and are not shown.

Further practice

These are topic and lesson matches, not identical appearances.

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