Recent Forum Posts
From categories:
page 1123...next »

in A and B, asking if the output will give a "shortest paths" tree - does it mean just the 𝛑 (parents array) or also the d (distance array)?

תרגיל 4 שאלה 4 by imb65imb65, 11 Dec 2018 23:02

פתרון נכון ומנומק ב-$O(n^4)$ יזכה במלוא הנקודות.

Re: תרגיל 4 שאלה 8 by tal_yanktal_yank, 10 Dec 2018 10:48

Right, infinite should be returned for such pairs.

Re: תרגיל 4 שאלה 7 by tal_yanktal_yank, 10 Dec 2018 10:47

האם יש להתייחס בשינוי האלגוריתם לאלגוריתם הפשוט, שרץ ב-$O(n^4)$
או ב'משופר' שרץ ב- $O(n^3 log(n))$?

תרגיל 4 שאלה 8 by kimasseokimasseo, 09 Dec 2018 17:01

hey,
should we assume there is always a directed path from u to v that contains x or y?
becaue can be a directed graph that each path from u to v doesn't conatin x nor y .
what should the algirthem return in this case? infinite ?

thanks

תרגיל 4 שאלה 7 by OrinLevyOrinLevy, 09 Dec 2018 15:46

מי שכבר הוריד את התרגיל שפורסם היום: נא להוריד מחדש (עודכן הניסוח של שאלה 3).

שאלה 3 עודכנה by tal_yanktal_yank, 06 Dec 2018 21:59

שלום,
תרגיל 4 עלה והוא להגשה ב-20 בדצמבר, 12:00 בצהריים.
עבודה נעימה לכולם.
ג׳אד

תרגיל 4 עלה by Jad SilbakJad Silbak, 06 Dec 2018 15:39

פולינומיאל

Re: תרגיל 3 שאלה 4 by Jad SilbakJad Silbak, 04 Dec 2018 16:51

כשכתוב מצא אלגוריתם יעיל, הכוונה היא בהכרח לאלגוריתם פולינומיאלי או רק "יעיל יחסית" ?

תרגיל 3 שאלה 4 by YuriKlYuriKl, 04 Dec 2018 12:20

שלום לכולם,

בשבוע הבא יתקיימו תרגולי השלמה (במקום התרגול שבוטל בתחילת הסמסטר).

התרגולים יהיו בנושא APSP ויתקיימו בשלושה מופעים:
שלישי 11.12 14:00-15:00 פיזיקה שנקר 204
שלישי 11.12 18:00-19:00 פיזיקה שנקר 104
שישי 14.12 11:00-12:00 פיזיקה שנקר 222

בברכה,
טל

היי,
התשובה הקצרה: צריכים להיות מנומקים; אין צורך להוכיח נכונות נוסחת רקורסיה בכלים פורמליים; אין צורך לתת פסאודו-קוד או להוכיח את נכונות החישוב באינדוקציה על סדר החישוב.

פירוט:

  1. כשכותבים נוסחת רקורסיה צריך לנמק, כלומר להסביר למה הנוסחא שנרשמה נכונה, אבל לא צריך להוכיח בכלים פורמליים. דוגמא לנימוק כזה משאלת המטבעות מהתרגול: $c[k]$ - מספר המטבעות המינימלי לחלוקת סכום $k$. אם בחלוקה מינימלית משתמשים במטבע ה-$i$ לפחות פעם אחת, אז מס' המטבעות שבה שווה ל- $1+c[k-a_i]$1. הסבר: חלוקה כזו תכלול את המטבע $a_i$ לפחות פעם אחת ומלבדו מטבעות נוספים שסכומם $k-a_i$. כיוון שזו חלוקה מינימלית מס' המטבעות הנוספים יהיה המס' המינימלי של מטבעות שדרוש כדי לחלק סכום $k-a_i$, כלומר $c[k-a_i]$.
  2. צריך לציין את סדר חישוב תתי הבעיות ולהסביר שבהנתן נוסחת הרקורסיה סדר זה מבטיח שתת בעיה תמיד תחושב לפני תת בעיה שתלויה בה.
  3. אם הפתרון מכיל שלבים אלגוריתמיים נוספים חוץ מהחלק שהוא "תכנון דינאמי", מקדימים או אוחרים, אז צריך להסביר אותם (כרגיל).
  4. תמיד צריך להגדיר תת בעיה באמצעות מילים (כלומר לא מספיק רק לתת נוסחת רקורסיה, מקרי בסיס, ולהגיד מה מחזירים בסוף).
  5. צריך כמובן לציין מה האלג' מחזיר \ מה הערך המבוקש (למשל "$c[k]$").

היי,
לא ברור לי האם יש להוכיח נכונות באופן פורמאלי בשאלות תכנות דינאמי.
זה לא מופיע בשלבי פתרון הבעיה בתרגול וגם זה נובע באופן ישיר מהגדרת תתי הבעיות והקשר בינן לפתרון ולכן אני מניחה שלא צריך,
אבל אשמח לתשובה ודאית.
בתודה מראש
אורין

Hi Noa,
There is still some time until the deadline, but here is a clue.
Think of a way to sort the trays such that, a tray of a higher order can't be placed on a tray of a lower order.
Then for every "sub-problem" you solve, you should be able to trace the trays that compose it.

Re: תרגיל 3 שאלה 6 by Jad SilbakJad Silbak, 30 Nov 2018 09:58

בטוח שרוצים שנפיק ממש את *הערימה עצמה* ולא רק את מספר המגשים בערימה הכי גבוהה האפשרית בהנתן סט המגשים הנתון? אם כן, אולי אפשר לתת איזשהו רמז לגבי זה?

תרגיל 3 שאלה 6 by Noa LNoa L, 29 Nov 2018 18:48

היי,
אני כותב כאן הכוונה בלבן על לבן - מי שרוצה לראות צריך לסמן את הטקסט.



הטענה נכונה כמובן.
הדרכה להוכחה:
1. להניח בשלילה שיש $G,T,T'$ שלא מקיימים את הטענה.
2. להסתכל על ה-$i$ הראשון עבורו מתקיים $w_i>w'_i$.
3. להסתכל על הקשתות של $T$ במשקל קטן-שווה $w'_i$ (כמה יש כאלה?) ועל הקשתות של $T'$ במשקל קטן-שווה $w'_i$ (כמה יש כאלה?).
4. לטעון שבהכרח יש זוג צמתים $u,v$ שהמסלול ביניהם ב-$T'$ מכיל רק קשתות במשקל קטן-שווה $w'_i$ ואילו המסלול ביניהם ב-$T$ מכיל לפחות קשת אחת במשקל גדול מ-$w'_i$.
5. להסביר מדוע לא ייתכן ש-$T$ עפ"מ.
טענה שימושית: ביער עם $k$ קשתות ו-$n$ צמתים יש $n-k$ רכיבי קשירות.


טל

Re: תרגיל 3 שאלה 3 by tal_yanktal_yank, 29 Nov 2018 11:19

היי
האם אפשר לקבל הכוונה לפתרון שאלה 3? נראה שכשמנסים להוכיח באופן דומה לשאלה 2 בתרגול מגיעים למבוי סתום.
בתודה מראש

תרגיל 3 שאלה 3 by OrinLevyOrinLevy, 29 Nov 2018 06:52

היי,
שאלה טובה, ואכן כן - העלות היא לבניית כביש דו סיטרי.
טל

Re: תרגיל 3 שאלה 2 by tal_yanktal_yank, 27 Nov 2018 11:58

היי,
האם העלות לבניית כביש מעיר אחת לעיר אחרת היא עלות לבניית כביש דו סיטרי- כלומר דו כיווני בין שני הערים , או שזו העלות לבניית כביש מעיר א לעיר ב והעלות של בניית כביש מעיר ב לעיר א היא שונה ?

בתודה מראש

תרגיל 3 שאלה 2 by OrinLevyOrinLevy, 25 Nov 2018 16:19

היי,
אם נעשתה טעות בבדיקה ניתן לפנות אלינו במייל (ולהסביר איפה בדיוק הטעות).
טל

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

תודה

page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License