[-] הבהרות - שאלה 1 +2
by lekhtser - Tuesday, 27 March 2012 19:58:05
כמה דברים שלא ברורים מניסוח העבודה..
שאלה 1: רשום להשתמש ברדוקציה לבעיית מסלול המילטון אבל בהוראות רשום שפיתרון מעריכי לא יתקבל - אפשר פשוט לפתור באמצעות אוילר?

שאלה 2: אם לא פספסתי פרט כלשהו, אפשר לבצע רדוקציה בשאלה לבעיית מציאת חציון ולמדנו במבנה נתונים אלגוריתם סלקט "משופר" הפותר את את הבעיה בזמן לינארי. האם אני מפספסת משהו, כי ביקשתי לפתור את הבעיה בזמן:
o(nlogn)

תודה!
thread
[-] Re: הבהרות - שאלה 1 +2
by alexla - Thursday, 29 March 2012 00:10:42
בקשר לשאלה הראשונה אז תשימי לב שמבקשים להסיק מסקנה כלשהי במקרה של המילטון. מה המסקנה בהינתן תנאי העבודה?

בקשר לשאלה השניה שלך אז כן את יכולה. רק תגידי במפורש באיזה אלגוריתם מדובר ומה הרעיון המרכזי שלו  (בלי לפרט יותר מידי)
thread
[-] Re: הבהרות - שאלה 1 +2
by eladgoo - Friday, 30 March 2012 16:38:29
כלומר בסעיף א שרשום שהאלגורתים אינו מתקבל לפי התנאים שהגדרתם זאת אומרת שלא צריך להתחשב בנכונות ובזמן ריצה של הכרעה האם קיים מסלול הימלטון ופשוט להניח שקיים האלגורתים נכון בזמן לינארי ?,
thread
[-] Re: הבהרות - שאלה 1 +2
by alexla - Sunday, 1 April 2012 13:27:40
Not exactly. Actually the reverse of what you said.
You have to reach a conclusion based on the available algorithm and the constraints.
thread
Re: הבהרות - שאלה 1 +2
by eladgoo - Sunday, 1 April 2012 14:27:55
אי אפשר להשתמש בהימלטון ועדין להיות בזמן לינארי, החלק הזה ברור ואין בעיה לרשום אותו במסקנה, הבעיה היא האם בגלל שאי אפשר אנחנו צריכים לנסות לפתור ולהראות שאי אפשר או ישר לרשום את המסקנה ?
thread