Complexity Atlas
HE
Source-backed question

נגדיר אלגוריתם לבעיית האופטימיזציה Bin-Packing: בהינתן a 1, ,a n, האלגוריתם עובר על המספרים לפי הסדר; אם אפשר…

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-a3d826e93293

נוסח השאלה

נגדיר אלגוריתם לבעיית האופטימיזציה Bin-PackingBin\text{-}Packing: בהינתן a1,…,ana_1,\ldots,a_n, האלגוריתם עובר על המספרים לפי הסדר; אם אפשר הוא מכניס את המספר לתא האחרון שנעשה בו שימוש, ואחרת מכניס אותו לתא חדש.

  1. הוכיחו כי בכל חלוקה שמחשב האלגוריתם, סכום האיברים בשני תאים סמוכים גדול מ-11.
  2. הוכיחו כי האלגוריתם משיג יחס קירוב 22.

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

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.

Assignment

2026 B

2026ב_03_תרגיל_בית_3.md

Question 6Page 1Human reviewed

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Further practice

These are topic and lesson matches, not identical appearances.

Examבגרף לא מכוון, שלושה קודקודים שונים מהווים משולש אם כל שניים מהם מחוברים בקשת. אוסף משולשים בגרף ייקרא זר בקשתות אם כל קשת של הגרף נמצאת על לכל היותר…Topically related — not a duplicateExamנעדכן את אלגוריתם הקירוב הקירוב שהראינו בשיעור לבעיית הכיסוי בצמתים באופן הבא. בכל איטרציה של הלולאה המרכזית באלגוריתם, כאשר האלגוריתם בוחר קשת x,y הו…Topically related — not a duplicateExamנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…Topically related — not a duplicateExamבאלגוריתם First Fit לאריזה בהרצאה שראינו מתאים בהריזה על איברי הקלט, עוברים לפי הסדר ומכניסים את a 1, ..., a n את aj (1 i n) לתא הראשון שקיים לו סכום…Topically related — not a duplicateExamנזכיר את בעיית האריזה בתאים. קלט: n-ייה של מספרים a 1, ,a n (0,1] ומספר טבעי k . שאלה: האם קיימת חלוקה של a 1,a 2, ,a n ל-k תאים כך שסכום המספרים בכל…Topically related — not a duplicateExamנתאר את בעיית האופטימיזציה הבאה: קלט: גרף (פשוט) מכוון G = (V, E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף G' = (V, E') חסר מעגלים. נתבונן באל…Topically related — not a duplicate

Near variants — not duplicates