2009 מועד א שאלה 4 סעיפים א' ב'

מנהל: TA_Isana

2009 מועד א שאלה 4 סעיפים א' ב'

הודעהעל ידי orp » 16:22 26/06/2010

מישהו יכול בבקשה להסביר את סעיף א' ואת שאלה 1 בסעיף ב'?
orp
 
הודעות: 7
הצטרף: 10:26 06/11/2009

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

הודעהעל ידי Golden » 20:41 16/07/2010

מצטרף לבקשה, 2009 מועד א', שאלה 4 סעיף א' וסעיף ב'1, תודה לכל העוזרים מראש.
Golden
 
הודעות: 12
הצטרף: 01:18 11/11/2009

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

הודעהעל ידי ronenhe » 20:55 16/07/2010

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



לגבי 2 שימו לב לזה ש:

ומאותה סיבה ש:


מקווה שעזרתי..
בהצלחה..
נערך לאחרונה על ידי ronenhe בתאריך 20:59 16/07/2010, נערך פעם אחת בסך הכל.
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

הודעהעל ידי eliorar » 20:59 16/07/2010

סעיף א': לא יכול להיות.
אם הפעולה האחרונה הייתה הכנסה של 7 אז הצומת שמעליו (3,8,2) היה צריך להתפצל כי יש לו 2t-1 כלומר 3. כפי שרואים הוא לא מפוצל לכן פעולה זו לא יכלה להתקיים.

סעיף ב':
1. לא נכון:
log f(n) ≤ c • log g(n) => log f(n) ≤ log ( g(n)^c) => f(n) ≤ g(n)^c

וזה בהחלט לא גורר ש
f(n)≤c • g(n)

לדוגמא:7≤3^2 אבל 7≥2•3
2. לא נכון:
(2n)! = n! • (n+1)(n+2)...(2n)

n! • (n+1)(n+2)...(2n)≤ c• n!

נחלק ב n!:
(n+1)(n+2)...(2n) ≤ c

וזה לעולם לא יקרה כי c קבוע.
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

הודעהעל ידי Golden » 23:18 16/07/2010

תודה לשניכם, ועוד שאלות לסיכום כדי לראות אם הבנתי איך הולכת ההכנסה בעץ B.
1. כל צומת מלאה בנתיב ההכנסה מפוצלת?
2. במקרה שהעלה מלא מבצעים את ההכנסה לאחר פיצול העלה, ואז לפי צומת האב יודעים לאן להכניס את האיבר החדש?
Golden
 
הודעות: 12
הצטרף: 01:18 11/11/2009

Re: 2009 מועד א שאלה 4 סעיפים א' ב'

הודעהעל ידי eliorar » 23:32 16/07/2010

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

כנס לאתר הזה: http://www.cse.ohio-state.edu/~bondhugu ... ndex.shtml
יש שם הדגמה טובה של עץ B-Tree
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009


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

מי מחובר

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

cron