תרגיל 2 שאלה 5

תרגיל 2 שאלה 5

guest (guest) 22 Mar 2013 08:46

כתוב שלמדנו בכיתה אלג' שבודק האם קיים מסלול שעובר בכל קודקודי S
ויכול לעבור בקודקודים נוספים אך לא לחצות את אותה קשת יותר מפעם אחת.

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

האם הכוונה לאותו אלגוריתם ?

Re: תרגיל 2 שאלה 5

Shai V 22 Mar 2013 14:44

כן. זאת טעות בשאלה… תודה על ההערה - שיניתי את התרגיל והעלתי מחדש את הקובץ.

שי

guest (guest) 26 Mar 2013 09:41

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

Shai V 26 Mar 2013 11:42

Hi,
A counter-example is almost always the way to disprove something. So yes.

But regarding the second part of your question - I'm not sure what you mean exactly. The algorithm we saw in the recitation gives a yes/no reply to whether there is such a path. The algorithm doesn't know not to cross each edge only once - it doesn't even find the path. Question 5 asks whether the same algorithm also correctly gives a response for the question "is there a path that…. and doesn't cross any edge more than once?"

I hope that answers your question(s).

Happy Pesach,
Shai