עבודה מספר 6

[sabagn]

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

[TA_Guy]

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

[shlomz]

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

[TA_Guy]

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

[shlomz]

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

[gata]

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

[ayalshimoni@walla.co.il]

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

[TA_Guy]

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

[shlomz]

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

[shlomz]

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

אתה מוכן לומר בבקשה אז איך פתרת את זה לשני המקרים?

[ayalshimoni@walla.co.il]

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

דרגת קודקוד זה כמה קשתות יוצאות ממנו. בגרף מכוון דרגת כניסה זה כמה קשתות מכוונות אליו ודרגת יציאה זה כמה קשתות יוצאות ממנו.


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

[shaharco]

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

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

[shaharco]

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