עבודה מספר 6

מנהל: TA_Isana

שלח תגובה
sabagn
הודעות: 34
הצטרף: 16:51 19/11/2008

עבודה מספר 6

שליחה על ידי sabagn » 16:02 06/07/2009

אפשר בבקשה לפרסם את העבודה בקובץ word רגיל??? (ולא 2007...)
תודה!

TA_Guy
הודעות: 21
הצטרף: 09:03 07/07/2009

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

שליחה על ידי TA_Guy » 09:21 07/07/2009

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

shlomz
הודעות: 28
הצטרף: 16:44 12/12/2008

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

שליחה על ידי shlomz » 19:25 07/07/2009

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

TA_Guy
הודעות: 21
הצטרף: 09:03 07/07/2009

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

שליחה על ידי TA_Guy » 11:38 08/07/2009

כן. ניתן להתייחס לפונקציית מציאת החציון כאל פונקצייה המקבלת גם שני פרמטרים: אינדקס התחלה ואינדקס סוף.

shlomz
הודעות: 28
הצטרף: 16:44 12/12/2008

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

שליחה על ידי shlomz » 14:24 09/07/2009

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

gata
הודעות: 88
הצטרף: 17:25 10/11/2007

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

שליחה על ידי gata » 19:09 09/07/2009

בשאלה 4
הגרף מכוון או לא?
או שזה בכלל יצור אבסטרקטי שכזה?

ayalshimoni@walla.co.il
הודעות: 27
הצטרף: 21:29 07/12/2008

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

שליחה על ידי ayalshimoni@walla.co.il » 21:26 09/07/2009

זה לא ממש משנה אני פתרתי את זה בצורה כזאת שזה יעבוד גם על גרף מכוון וגם על גרף לא מכוון

TA_Guy
הודעות: 21
הצטרף: 09:03 07/07/2009

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

שליחה על ידי TA_Guy » 10:39 12/07/2009

כל עוד לא נכתב אחרת, עליך להניח כי טווח המפתחות הינו כל הציר הממשי.

shlomz
הודעות: 28
הצטרף: 16:44 12/12/2008

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

שליחה על ידי shlomz » 16:45 12/07/2009

שאלה 3 סעיף ב'
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS

shlomz
הודעות: 28
הצטרף: 16:44 12/12/2008

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

שליחה על ידי shlomz » 18:21 12/07/2009

ayalshimoni@walla.co.il כתב:זה לא ממש משנה אני פתרתי את זה בצורה כזאת שזה יעבוד גם על גרף מכוון וגם על גרף לא מכוון
אתה מוכן לומר בבקשה אז איך פתרת את זה לשני המקרים?

ayalshimoni@walla.co.il
הודעות: 27
הצטרף: 21:29 07/12/2008

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

שליחה על ידי ayalshimoni@walla.co.il » 21:49 12/07/2009

shlomz כתב:שאלה 3 סעיף ב'
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS
דרגת קודקוד זה כמה קשתות יוצאות ממנו. בגרף מכוון דרגת כניסה זה כמה קשתות מכוונות אליו ודרגת יציאה זה כמה קשתות יוצאות ממנו.


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

shaharco
הודעות: 19
הצטרף: 12:39 25/04/2009

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

שליחה על ידי shaharco » 17:18 15/07/2009

זה נראה ממש המון זמן...
V*(V+E) a
וזה אכן לא משנה הכיוון. ואפשר לפתור ב- 2*(V+E)...

shlomz
הודעות: 28
הצטרף: 16:44 12/12/2008

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

שליחה על ידי shlomz » 15:01 16/07/2009

לגבי 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 ולפי זה אתה אמור להחזיר כן.
אז איך אתה פותר את הבעיה הזו?

shaharco
הודעות: 19
הצטרף: 12:39 25/04/2009

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

שליחה על ידי shaharco » 10:56 17/07/2009

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

שלח תגובה

חזור אל “- מבני נתונים”