דף 1 מתוך 1

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

נשלח: 17:22 26/06/2010
על ידי orp
מישהו יכול בבקשה להסביר את סעיף א' ואת שאלה 1 בסעיף ב'?

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

נשלח: 21:41 16/07/2010
על ידי Golden
מצטרף לבקשה, 2009 מועד א', שאלה 4 סעיף א' וסעיף ב'1, תודה לכל העוזרים מראש.

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

נשלח: 21:55 16/07/2010
על ידי ronenhe
לגבי 2א: מקווה שאני לא מטעה אבל זאת דעתי..
שמכניסים איבר צריך לדאוג לכל מה שלמעלה..
במידה והוספנו את 7 קודקוד האב לא בנוי להוספה כי אם במקום של 7 היו כבר 3 איברים היה צורך בפיצול של קודקוד האב..
האלגוריתם שלנו מפצל מראש את כל קודקודי האב עד למקום שהיה צריך להוסיף..
ולכן 3 לא יכול להיות אחרי פיצול (בקודקוד הרב)
לגבי 2ב
1 : דוגמא נגדית:
\(f%28n%29=n^2,%20g%28n%29=n\\\Rightarrow%20log%28f%29=2log%28n%29,log%28g%29=log%28n%29\\\Rightarrow%20log%28f%29=O%28log%28g%29%29\\%20f%28n%29\neq%20O%28g%28n%29%29\)


לגבי 2 שימו לב לזה ש:
\((2n)!>n!(n+1)>>n!\)
ומאותה סיבה ש:
\(n^{2} \neq O(n)\)

מקווה שעזרתי..
בהצלחה..

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

נשלח: 21:59 16/07/2010
על ידי eliorar
סעיף א': לא יכול להיות.
אם הפעולה האחרונה הייתה הכנסה של 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 קבוע.

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

נשלח: 00:18 17/07/2010
על ידי Golden
תודה לשניכם, ועוד שאלות לסיכום כדי לראות אם הבנתי איך הולכת ההכנסה בעץ B.
1. כל צומת מלאה בנתיב ההכנסה מפוצלת?
2. במקרה שהעלה מלא מבצעים את ההכנסה לאחר פיצול העלה, ואז לפי צומת האב יודעים לאן להכניס את האיבר החדש?

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

נשלח: 00:32 17/07/2010
על ידי eliorar
לא בדיוק, בזמן שיורדים להכנסה, תוך כדי הירידה ולפני ההכנסה, מבצעים את הפיצול (לוקחים את האמצעי ומעלים אותו לאבא) רק אח"כ ממשיכים לרדת, עד שמגיעים לעלה ומכניסים את האיבר.

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