דף 1 מתוך 1

עבודה מספר 6

נשלח: 16:02 06/07/2009
על ידי sabagn
אפשר בבקשה לפרסם את העבודה בקובץ word רגיל??? (ולא 2007...)
תודה!

Re: עבודה מספר 6

נשלח: 09:21 07/07/2009
על ידי TA_Guy
העבודה הועלתה גם בגירסת PDF ובגירסת DOC.
הערה מרכזית:
עבור כל שאלה בדף השאלות (פרט האחרונה) הוספנו מספר שורות ריקות שבהן יש לכתוב את פתרונכם. פתרונכם לא אמור להיות ארוך יותר מטווח השורות המוצע.
השאלות הן בפורמט של מבחן וברמה של מבחן, והן מהוות הכנה טובה לקראתו.
בהצלחה.

Re: עבודה מספר 6

נשלח: 19:25 07/07/2009
על ידי shlomz
בשאלה 1ב:
ניתן להתייחס לפונקציית מציאת החציון כאל פונקצייה
findMed(A,p,q ? כלומר כמקבלת גם שני פרמטרים: אינדקס התחלה ואינדקס סוף?

Re: עבודה מספר 6

נשלח: 11:38 08/07/2009
על ידי TA_Guy
כן. ניתן להתייחס לפונקציית מציאת החציון כאל פונקצייה המקבלת גם שני פרמטרים: אינדקס התחלה ואינדקס סוף.

Re: עבודה מספר 6

נשלח: 14:24 09/07/2009
על ידי shlomz
שאלה1ג, לגבי השאלה על שינוי המפתחות.
ניתן להתייחס למפתחות שאני מקבל, כלומר לקלט, כאל מספרים טבעיים בלבד?
או שמספר מסוים בקלט שלי יכול להיות כל מספר מהציר הממשי?

Re: עבודה מספר 6

נשלח: 19:09 09/07/2009
על ידי gata
בשאלה 4
הגרף מכוון או לא?
או שזה בכלל יצור אבסטרקטי שכזה?

Re: עבודה מספר 6

נשלח: 21:26 09/07/2009
על ידי ayalshimoni@walla.co.il
זה לא ממש משנה אני פתרתי את זה בצורה כזאת שזה יעבוד גם על גרף מכוון וגם על גרף לא מכוון

Re: עבודה מספר 6

נשלח: 10:39 12/07/2009
על ידי TA_Guy
כל עוד לא נכתב אחרת, עליך להניח כי טווח המפתחות הינו כל הציר הממשי.

Re: עבודה מספר 6

נשלח: 16:45 12/07/2009
על ידי shlomz
שאלה 3 סעיף ב'
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS

Re: עבודה מספר 6

נשלח: 18:21 12/07/2009
על ידי shlomz
ayalshimoni@walla.co.il כתב:זה לא ממש משנה אני פתרתי את זה בצורה כזאת שזה יעבוד גם על גרף מכוון וגם על גרף לא מכוון
אתה מוכן לומר בבקשה אז איך פתרת את זה לשני המקרים?

Re: עבודה מספר 6

נשלח: 21:49 12/07/2009
על ידי ayalshimoni@walla.co.il
shlomz כתב:שאלה 3 סעיף ב'
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS
דרגת קודקוד זה כמה קשתות יוצאות ממנו. בגרף מכוון דרגת כניסה זה כמה קשתות מכוונות אליו ודרגת יציאה זה כמה קשתות יוצאות ממנו.


לגבי הזה שמעלי:
בהנחה שהקודקודים הם מספרים שלמים מ1 עד K כלשהו, תאתחל מטריצה M של |V|*|V| ש V זה מספר הקודקודים. המטריצה תספור את מספר המסלולים מקודקוד מסוים לקודקוד מסוים.
תעשה BFS על כל קודקוד בגרף. נניח שאתה מבצע BFS על קודקוד U מסוים אז כל פעם שאתה מגיע לקודקוד W תעשה M[w]=+1 . בנוסף ה BFS הוא לא סטנדרטי שנעצר שאתה מגיע לקודקוד אפור אלה נעצר רק שאתה מגיע לקודקוד שדרגת היציאות שלו היא 0 .

Re: עבודה מספר 6

נשלח: 17:18 15/07/2009
על ידי shaharco
זה נראה ממש המון זמן...
V*(V+E) a
וזה אכן לא משנה הכיוון. ואפשר לפתור ב- 2*(V+E)...

Re: עבודה מספר 6

נשלח: 15:01 16/07/2009
על ידי shlomz
לגבי 4ב' הבנתי איך אתה עושה את זה ב 2*(V+E)
אתה עושה BFS על S ועל B ובודק אם
d(s,a) + d(b,t) + 1 = d(s,t כאשר d(s,a מייצגת את המרחק הקטן ביותר בין s ל a בגרף. אם המשוואה נכונה אז תחזיר כן.
אבל יתכן והמרחק בין s לבין b קטן מהמרחק בין s ל a. ובגרף לא מכוון אין הבדל בין הקשת a,b ל b,a. וייתכן והחזרת לא, כי המשוואה שהראיתי פה לא נכונה לגרף אך כן מתקיים: d(s,b) + d(a,t) = d(s,t ולפי זה אתה אמור להחזיר כן.
אז איך אתה פותר את הבעיה הזו?

Re: עבודה מספר 6

נשלח: 10:56 17/07/2009
על ידי shaharco
לא הבנתי מה עשית...
האלגוריתם הוא כזה:
אני משתמש באלגוריתם מהתרגול שמשנה את BFS כך שיחזיר גם את מספר המסלולים הקצר ביותר.
נריץ אותו בפעם הראשונה באופן רגיל ונשמור את מספר המסלולים הקצרים מ-S ל-T.
נוציא את הצלע AB מהגרף ונריץ שוב את הBFS החדש ונבדוק את מס' המסלולים הקצרים ביותר מ-S ל-T.
אם מס המסלולים השתנה סימן ש-AB היתה על אחד המסלולים הקצרים ביותר
(אגב, באופן דומה ניתן לפתור גם את 4א רק עם הBFS הישן)