Complexity Atlas
HE
Source-backed question

בהינתן a 1, ,a n, האלגוריתם עובר על המספרים לפי סדרם; במידת האפשר הוא מכניס כל מספר לתא האחרון שנעשה בו שימוש,…

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

נוסח השאלה

בהינתן 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

2024

2024_03_תרגיל_3.md

Question 3Page 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באלגוריתם 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 duplicateExamתת-הסכום (Subset-Sum). כזכור, הקלט מורכב מרשימת טבעיים 1 x 1,...,x n B יחד עם דרישת קירוב ε>0. כזכור, A % j הינה הרשימה המדוללת שהאלגוריתם מחשב באיטרצ…Topically related — not a duplicate

Near variants — not duplicates