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

מנהל: TA_Isana

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

הודעהעל ידי michal cohen » 19:07 23/06/2010

סעיף א'- איך יכול להיות שבסריקת DFS הקדקוד d ייסרק ומיד אחריו ייסרק הקדקוד c?
הרי DFS סורק עד שאין לו יותר מסלול... ז"א ב-DFS הסריקה היתה אמורה להמשיך אחרי d ל-u ומשם לאחד הילדים של u.
סעיף ב'- למה התשובה היא o(n ולא O(|V|+|E?
סעיף ג'- למה זה ככה? איך מגיעים לזה בכלל?
וסעיף ד' - זה משהו שלמדנו בכלל?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

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

הודעהעל ידי Raz.A » 09: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 מפתחות, יהיה צורך לפצל אותו ואז נוצרת רמה חדשה.
Raz.A
 
הודעות: 64
הצטרף: 22:00 26/10/2009

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

הודעהעל ידי michal cohen » 20:39 25/06/2010

וסעיף ד'? למדנו?
michal cohen
 
הודעות: 87
הצטרף: 19:04 11/11/2009

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

הודעהעל ידי rubichi » 12:06 26/06/2010

למדנו, זה ייצוג union-find בעזרת עצים.
union by rank - בעיקרון זה אומר שאם עושים איחוד של שתי קבוצות, אז הקבוצה שגובה העץ שלה נמוך יותר תתחבר לשורש קל הקבוצה הגבוהה יותר.
path compression - הפיכת כל הקודקודים במסלול מ x לשורש לבנים ישירים של השורש במהלך פעולת findset(x)
rubichi
 
הודעות: 77
הצטרף: 18:50 22/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד