מבחן 2008 מועד ב' שאלה 2

מנהל: TA_Isana

שלח תגובה
michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

מבחן 2008 מועד ב' שאלה 2

שליחה על ידי michal cohen » 20:07 23/06/2010

סעיף א'- איך יכול להיות שבסריקת DFS הקדקוד d ייסרק ומיד אחריו ייסרק הקדקוד c?
הרי DFS סורק עד שאין לו יותר מסלול... ז"א ב-DFS הסריקה היתה אמורה להמשיך אחרי d ל-u ומשם לאחד הילדים של u.
סעיף ב'- למה התשובה היא o(n ולא O(|V|+|E?
סעיף ג'- למה זה ככה? איך מגיעים לזה בכלל?
וסעיף ד' - זה משהו שלמדנו בכלל?

Raz.A
הודעות: 64
הצטרף: 22:00 26/10/2009

Re: מבחן 2008 מועד ב' שאלה 2

שליחה על ידי Raz.A » 10:18 24/06/2010

לגבי סעיף א', אני חושב שהפיתרון שהם נתנו, כלומר הסריקה של הקודקודים היא מימין לשמאל:d,c,u,b,a
קודם כל a נסרק, ולא היה לאן להתקדם
ואז b נסרק, ואז u ואז c ובסוף d.. כך הגיע מצב שעבור כל קודקוד, מוצו האפשרויות לאחר הסריקה שלו עצמו, ובפרט עבור u, החיפוש מוצה כבר עבור שני בניו וצבעם שחור.
זה אפשרי כי החיפוש בDFS מתחיל מקודקוד שרירותי ולכן אפשר לשחק עם זה.

לגבי סעיף ב': מדובר בעץ בינארי(ספציפית, לכל גרף אחר ברור שאת צודקת) ,בעץ n קודקודים וn-1 צלעות, לכן במקרה הגרוע נעבור על כל איברי העץ אכן בזמן O(|v|+|e|) אבל נתון: n צמתים, לכן במקרה הגרוע נעבור על כולם.

לגבי סעיף ג': מה שעשיתי היה להסתכל על עץ הB, יש לו 2 רמות, בשורש יש t-1 מפתחות ולכן יש לו t בנים, כל אחד עם t-1 מפתחות. אנחנו רוצים מספר מינימאלי של הכנסות אז אפשרות אחת היא להכניס t מפתחות, כך שכולם יכנסו לבן השמאלי של המפתח השמאלי של השורש(רמה 0), אחרי ההכנסה בקודקוד זה (שנמצא ברמה ה1) 2t-1 מפתחות. נכניס עוד מפתח לשם, ואז יהיה צורך לפצל את הקודקוד, מפתח אחד יעלה אל השורש, ויווצרו 2 בנים עם t-1 מפתחות כל אחד (שניהם ברמה 1).
עכשיו נכניס מפתחות בצורה כך שיכנסו לקודקוד נוסף ברמה התחתונה שיש לו t-1 מפתחות. אפשר איזה שרוצים כי אחרי t+1 הכנסות, שוב יהיה פיצול של הקודקוד ומפתח יעלה למעלה.
נעשה זאת עד שבשורש יש 2t-1 מפתחות (אחרי t הכנסות של t מפתחות כל אחד- סה"כ t^2). ואז נכניס מפתח נוסף לעץ, נגענו בשורש והשורש מלא ב2t-1 מפתחות, יהיה צורך לפצל אותו ואז נוצרת רמה חדשה.

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: מבחן 2008 מועד ב' שאלה 2

שליחה על ידי michal cohen » 21:39 25/06/2010

וסעיף ד'? למדנו?

rubichi
הודעות: 77
הצטרף: 18:50 22/10/2009

Re: מבחן 2008 מועד ב' שאלה 2

שליחה על ידי rubichi » 13:06 26/06/2010

למדנו, זה ייצוג union-find בעזרת עצים.
union by rank - בעיקרון זה אומר שאם עושים איחוד של שתי קבוצות, אז הקבוצה שגובה העץ שלה נמוך יותר תתחבר לשורש קל הקבוצה הגבוהה יותר.
path compression - הפיכת כל הקודקודים במסלול מ x לשורש לבנים ישירים של השורש במהלך פעולת findset(x)

שלח תגובה

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