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

במסגרת תרגיל הבית עלתה שאלה תיאורטית לגבי אלגוריתם דייקסטרא כפי שלמדנו אותו: נניח יש לי צומת v שאני עכשיו מוציא אותה מ-Q, ועושה פעולת relax על כל השכנים שלה. נניח u שכן של v, ונניח שכאשר הוצאנו את v מ-Q אז u נמצא כבר ב-S (כלומר, הוצאנו כבר את u מ-Q קודם לכן).

בכזה מקרה, אם כל הקשתות חיוביות, אז נובע מכל הלמות שלמדנו ש-u.d = delta(s,u), ואז אין משמעות ללעשות רילקס לקשת שמחברת את v ל-u. אבל אם נניח אחת הקשתות בגרף שלילית (כמו למשל בשאלה 4ב') אז עשויה להיות משמעות ללבצע רילקס לקשת הנ"ל. השאלה אם בכל מקרה נעשה relax, או שהיות ש-u כבר ב-S אז לא נעשה רילקס לקשת הזו?
(בוויקידפיה למשל אומרים שאם קודקוד לא נמצא ב-Q אז לא עושים רילקס לקשתות שמתחברות אליו, אבל באלגוריתם כפי שנכתב בכיתה זה לא ברור כל כך)

תודה רבה ושבת שלום :)

אלגוריתם דייקסטרא - שאלת הבהרה by Tomer Solomon (guest), 27 May 2017 09:41

בשאלה 3, האם פלט האלגוריתם צריך להיות קבוצה של מעגלים (כי לכל צומת v יהיה את המעגל הרלוונטי) או שהאלגוריתם מקבל צומת s וצומת v, ואז צריך למצוא את המעגל הקל ביותר רק ביחס ל-2 הצמתים הנ"ל?
כאילו מה בדיוק הקלט ומה בדיוק הפלט של האלגוריתם?

תודה רבה ושבת שלום :)

שאלה 3 - הבהרת ניסוח by Tomer Solomon (guest), 27 May 2017 07:04
Tomer Solomon (guest) 26 May 2017 19:02
in discussion Discussions / Q&A, Spring 2017 » תרגיל 4 שאלה 4

גם לגבי שאלה 4 - רק רוצה לוודא - אפשרי מעגל מצומת לעצמו? (אני מניח שלא, אבל רוצה לוודא)

תודה ושבת שלום :)

by Tomer Solomon (guest), 26 May 2017 19:02
תרגיל 4 שאלה 4
Nataly (guest) 26 May 2017 15:12
in discussion Discussions / Q&A, Spring 2017 » תרגיל 4 שאלה 4

היי,
בסעיף ב', מצאתי דוגמא שבה האלגוריתם לא בהכרח מעדכן בצורה נכונה את המרחקים של כל צומת מצומת המקור, אבל העץ עצמו שנוצר באלגוריתם הוא עץ נכון. האם זה מספיק לצורך דוגמא נגדית?
כי נניח שהקשת השלילית היא (u,v). כשהאלגוריתם יגיע לקודקוד u הוא בהכרח יבצע relax ויגדיר את u כאבא של v.

תודה

תרגיל 4 שאלה 4 by Nataly (guest), 26 May 2017 15:12

נפרסם הסברים מקוצרים בהמשך.

מה הבנת מהשאלה? מה לא הבנת מהשאלה? אנא בקש הבהרה על ניסוח לא מובן ספציפי.

Re: תרגיל 4 שאלה 5 by alonedenaloneden, 21 May 2017 10:54

האם יש אפשרות לפרסם פתרונות לתרגילי בית ?

פרסום פתרונות לתרגילי בית by David (guest), 21 May 2017 10:21
תרגיל 4 שאלה 5
תומר נייר (guest) 20 May 2017 14:31
in discussion Discussions / Q&A, Spring 2017 » תרגיל 4 שאלה 5

שאלה 5 בתרגיל הרביעי ממש לא ברורה.
אשמח לקבל הסבר מה הכוונה של השואל.
תודה!

תרגיל 4 שאלה 5 by תומר נייר (guest), 20 May 2017 14:31

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

by alonedenaloneden, 18 May 2017 11:52

אלא אם מצויין אחרת, אפשר להניח שהגרף פשוט (ללא קשתות מקבילות ולולאות).

Re: שאלה כללית by alonedenaloneden, 18 May 2017 11:50

נוספו קשתות מקודקוד חדש, אז לא נוספו קשתות מקבילות. מספר הקשתות הוא בין 0 לגודל V.

Re: תרגיל 3 שאלה 1 by alonedenaloneden, 18 May 2017 07:06

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

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

Re: Q7,Q8
alonedenaloneden 18 May 2017 06:59
in discussion Discussions / Q&A, Spring 2017 » Q7,Q8

7 - המספרים לא יכולים להיות שליליים ומותר לחזור על מספרים.
8 - אפשר להניח.

Re: Q7,Q8 by alonedenaloneden, 18 May 2017 06:59
תרגיל 3 שאלה 1
Guy (guest) 17 May 2017 17:29
in discussion Discussions / Q&A, Spring 2017 » תרגיל 3 שאלה 1

אהלן,

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

תודה רבה!

תרגיל 3 שאלה 1 by Guy (guest), 17 May 2017 17:29
Tomer Solomon (guest) 16 May 2017 10:48
in discussion Discussions / Q&A, Spring 2017 » תכנות דינמי - הוכחת נכונות

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

תודה :)

by Tomer Solomon (guest), 16 May 2017 10:48

בשאלה 7 הגעתי לאלגוריתם שהסיבוכיות שלו היא O(m^3), האם זה הסיבוכיות הרצויה?
ובכללי - איך אני יודע (בפרט בתכנון דינמי) אם זה הסיבוכיות "הכי טובה"? יש איזשהו כלל אצבע או חוקיות כלשהי?

תודה :)

שאלה כללית
שיר (guest) 16 May 2017 08:07
in discussion Discussions / Q&A, Spring 2017 » שאלה כללית

היי,
באופן כללי, כשמנתחים סיבוכיות, אפשר לצאת מנקודת הנחה שאין קשתות מקבילות (כלומר שני קודקודים שיש שתי קשתות העוברות ביניהם)?
כלומר שלצומת יש O(|V|) קשתות היוצאות ממנו…

תודה!

שאלה כללית by שיר (guest), 16 May 2017 08:07
Q7,Q8
Hani (guest) 15 May 2017 14:35
in discussion Discussions / Q&A, Spring 2017 » Q7,Q8

1)?והאם מותר לחזור על מספרים,m שאלה 7 האם המספרים יכולים להיות רק מ0 עד
2) יכול k שאלה 8: האם מותר לי להניח כי
להיות רק עד v-1?

Q7,Q8 by Hani (guest), 15 May 2017 14:35

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

היתה טעות בדוגמא, עדכנו את התרגיל:
http://tau-algorithms.wdfiles.com/local--files/exercises/Ex32017.pdf

הערך של המשחק הוא 7.

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