מפת הסיבוכיות
EN
שאלה מבוססת מקור

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

0בחינות1מטלות0שיעורים1מסמכי מקור
שאלה פתוחהq-1c59e42247ce

נוסח השאלה

בהינתן a1,…,ana_1,\ldots,a_n, האלגוריתם עובר על המספרים לפי סדרם; במידת האפשר הוא מכניס כל מספר לתא האחרון שנעשה בו שימוש, ואחרת פותח תא חדש.

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

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

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

מטלה

2024

2024_03_תרגיל_3.md

שאלה 3עמוד 1נבדק אנושית

העמודים שמהם זה נכתב

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

בחינהבגרף לא מכוון, שלושה קודקודים שונים מהווים משולש אם כל שניים מהם מחוברים בקשת. אוסף משולשים בגרף ייקרא זר בקשתות אם כל קשת של הגרף נמצאת על לכל היותר…דומה בנושא — לא כפילותבחינהנעדכן את אלגוריתם הקירוב הקירוב שהראינו בשיעור לבעיית הכיסוי בצמתים באופן הבא. בכל איטרציה של הלולאה המרכזית באלגוריתם, כאשר האלגוריתם בוחר קשת x,y הו…דומה בנושא — לא כפילותבחינהבאלגוריתם First Fit לאריזה בהרצאה שראינו מתאים בהריזה על איברי הקלט, עוברים לפי הסדר ומכניסים את a 1, ..., a n את aj (1 i n) לתא הראשון שקיים לו סכום…דומה בנושא — לא כפילותבחינהנזכיר את בעיית האריזה בתאים. קלט: n-ייה של מספרים a 1, ,a n (0,1] ומספר טבעי k . שאלה: האם קיימת חלוקה של a 1,a 2, ,a n ל-k תאים כך שסכום המספרים בכל…דומה בנושא — לא כפילותבחינהנתאר את בעיית האופטימיזציה הבאה: קלט: גרף (פשוט) מכוון G = (V, E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף G' = (V, E') חסר מעגלים. נתבונן באל…דומה בנושא — לא כפילותבחינהתת-הסכום (Subset-Sum). כזכור, הקלט מורכב מרשימת טבעיים 1 x 1,...,x n B יחד עם דרישת קירוב ε>0. כזכור, A % j הינה הרשימה המדוללת שהאלגוריתם מחשב באיטרצ…דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות