עבודה מספר 6
מנהל: TA_Isana
עבודה מספר 6
אפשר בבקשה לפרסם את העבודה בקובץ word רגיל??? (ולא 2007...)
תודה!
תודה!
Re: עבודה מספר 6
העבודה הועלתה גם בגירסת PDF ובגירסת DOC.
הערה מרכזית:
עבור כל שאלה בדף השאלות (פרט האחרונה) הוספנו מספר שורות ריקות שבהן יש לכתוב את פתרונכם. פתרונכם לא אמור להיות ארוך יותר מטווח השורות המוצע.
השאלות הן בפורמט של מבחן וברמה של מבחן, והן מהוות הכנה טובה לקראתו.
בהצלחה.
הערה מרכזית:
עבור כל שאלה בדף השאלות (פרט האחרונה) הוספנו מספר שורות ריקות שבהן יש לכתוב את פתרונכם. פתרונכם לא אמור להיות ארוך יותר מטווח השורות המוצע.
השאלות הן בפורמט של מבחן וברמה של מבחן, והן מהוות הכנה טובה לקראתו.
בהצלחה.
Re: עבודה מספר 6
בשאלה 1ב:
ניתן להתייחס לפונקציית מציאת החציון כאל פונקצייה
findMed(A,p,q ? כלומר כמקבלת גם שני פרמטרים: אינדקס התחלה ואינדקס סוף?
ניתן להתייחס לפונקציית מציאת החציון כאל פונקצייה
findMed(A,p,q ? כלומר כמקבלת גם שני פרמטרים: אינדקס התחלה ואינדקס סוף?
Re: עבודה מספר 6
כן. ניתן להתייחס לפונקציית מציאת החציון כאל פונקצייה המקבלת גם שני פרמטרים: אינדקס התחלה ואינדקס סוף.
Re: עבודה מספר 6
שאלה1ג, לגבי השאלה על שינוי המפתחות.
ניתן להתייחס למפתחות שאני מקבל, כלומר לקלט, כאל מספרים טבעיים בלבד?
או שמספר מסוים בקלט שלי יכול להיות כל מספר מהציר הממשי?
ניתן להתייחס למפתחות שאני מקבל, כלומר לקלט, כאל מספרים טבעיים בלבד?
או שמספר מסוים בקלט שלי יכול להיות כל מספר מהציר הממשי?
Re: עבודה מספר 6
בשאלה 4
הגרף מכוון או לא?
או שזה בכלל יצור אבסטרקטי שכזה?
הגרף מכוון או לא?
או שזה בכלל יצור אבסטרקטי שכזה?
-
- הודעות: 27
- הצטרף: 21:29 07/12/2008
Re: עבודה מספר 6
זה לא ממש משנה אני פתרתי את זה בצורה כזאת שזה יעבוד גם על גרף מכוון וגם על גרף לא מכוון
Re: עבודה מספר 6
כל עוד לא נכתב אחרת, עליך להניח כי טווח המפתחות הינו כל הציר הממשי.
Re: עבודה מספר 6
שאלה 3 סעיף ב'
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS
Re: עבודה מספר 6
אתה מוכן לומר בבקשה אז איך פתרת את זה לשני המקרים?ayalshimoni@walla.co.il כתב:זה לא ממש משנה אני פתרתי את זה בצורה כזאת שזה יעבוד גם על גרף מכוון וגם על גרף לא מכוון
-
- הודעות: 27
- הצטרף: 21:29 07/12/2008
Re: עבודה מספר 6
דרגת קודקוד זה כמה קשתות יוצאות ממנו. בגרף מכוון דרגת כניסה זה כמה קשתות מכוונות אליו ודרגת יציאה זה כמה קשתות יוצאות ממנו.shlomz כתב:שאלה 3 סעיף ב'
מהי דרגה של קודקוד ב BFS ודרגת כניסה.
לא זכור לי שהדברים האלה הוגדרו ב BFS
לגבי הזה שמעלי:
בהנחה שהקודקודים הם מספרים שלמים מ1 עד K כלשהו, תאתחל מטריצה M של |V|*|V| ש V זה מספר הקודקודים. המטריצה תספור את מספר המסלולים מקודקוד מסוים לקודקוד מסוים.
תעשה BFS על כל קודקוד בגרף. נניח שאתה מבצע BFS על קודקוד U מסוים אז כל פעם שאתה מגיע לקודקוד W תעשה M[w]=+1 . בנוסף ה BFS הוא לא סטנדרטי שנעצר שאתה מגיע לקודקוד אפור אלה נעצר רק שאתה מגיע לקודקוד שדרגת היציאות שלו היא 0 .
Re: עבודה מספר 6
זה נראה ממש המון זמן...
V*(V+E) a
וזה אכן לא משנה הכיוון. ואפשר לפתור ב- 2*(V+E)...
V*(V+E) a
וזה אכן לא משנה הכיוון. ואפשר לפתור ב- 2*(V+E)...
Re: עבודה מספר 6
לגבי 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 ולפי זה אתה אמור להחזיר כן.
אז איך אתה פותר את הבעיה הזו?
אתה עושה 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
לא הבנתי מה עשית...
האלגוריתם הוא כזה:
אני משתמש באלגוריתם מהתרגול שמשנה את BFS כך שיחזיר גם את מספר המסלולים הקצר ביותר.
נריץ אותו בפעם הראשונה באופן רגיל ונשמור את מספר המסלולים הקצרים מ-S ל-T.
נוציא את הצלע AB מהגרף ונריץ שוב את הBFS החדש ונבדוק את מס' המסלולים הקצרים ביותר מ-S ל-T.
אם מס המסלולים השתנה סימן ש-AB היתה על אחד המסלולים הקצרים ביותר
(אגב, באופן דומה ניתן לפתור גם את 4א רק עם הBFS הישן)
האלגוריתם הוא כזה:
אני משתמש באלגוריתם מהתרגול שמשנה את BFS כך שיחזיר גם את מספר המסלולים הקצר ביותר.
נריץ אותו בפעם הראשונה באופן רגיל ונשמור את מספר המסלולים הקצרים מ-S ל-T.
נוציא את הצלע AB מהגרף ונריץ שוב את הBFS החדש ונבדוק את מס' המסלולים הקצרים ביותר מ-S ל-T.
אם מס המסלולים השתנה סימן ש-AB היתה על אחד המסלולים הקצרים ביותר
(אגב, באופן דומה ניתן לפתור גם את 4א רק עם הBFS הישן)