דף 1 מתוך 1

עבודה 6- שאלות 5 ו-6

נשלח: 19:36 15/07/2009
על ידי yb
שלום,
בקשר לשאלה 5- רציתי לדעת האם יש הגבלה של שימוש בזיכרון נוסף? ואם כן, אז כמה?
בשאלה 6 יכול להיות שהיה צריך להיות סוגריים כן ש-C מוכפל ב-V וגם ב-E? כלומר שזמן הריצה הכולל יהיה CV+CE?
תודה

Re: עבודה 6- שאלות 5 ו-6

נשלח: 10:24 16/07/2009
על ידי TA_Guy
בשאלה חמש ניתן להשתמש בזיכרון נוסף בגודל הקלט (כך יש לנהוג תמיד אלא אם נאמר אחרת).
בשאלה שש, כפי שנכתב הזמן הנדרש הינוו C*V+E ולא V+C*E. פתרון בזמן V+C*E אפשרי ע"י רדוקציה ל-BFS כאשר אנו ממירים קשת במשקל W ל-W קשתות במשקל אחד. השאלה הנ"ל יותר קשה. רמז: רדוקציה.