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

מנהל: TA_Isana

שלח תגובה
orp
הודעות: 7
הצטרף: 10:26 06/11/2009

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

שליחה על ידי orp » 17:22 26/06/2010

מישהו יכול בבקשה להסביר את סעיף א' ואת שאלה 1 בסעיף ב'?

Golden
הודעות: 12
הצטרף: 01:18 11/11/2009

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

שליחה על ידי Golden » 21:41 16/07/2010

מצטרף לבקשה, 2009 מועד א', שאלה 4 סעיף א' וסעיף ב'1, תודה לכל העוזרים מראש.

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

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

שליחה על ידי ronenhe » 21:55 16/07/2010

לגבי 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)\)

מקווה שעזרתי..
בהצלחה..
נערך לאחרונה על ידי ronenhe ב 21:59 16/07/2010, נערך פעם 1 בסך הכל.

eliorar
הודעות: 35
הצטרף: 19:43 11/11/2009

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

שליחה על ידי eliorar » 21: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 קבוע.

Golden
הודעות: 12
הצטרף: 01:18 11/11/2009

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

שליחה על ידי Golden » 00:18 17/07/2010

תודה לשניכם, ועוד שאלות לסיכום כדי לראות אם הבנתי איך הולכת ההכנסה בעץ B.
1. כל צומת מלאה בנתיב ההכנסה מפוצלת?
2. במקרה שהעלה מלא מבצעים את ההכנסה לאחר פיצול העלה, ואז לפי צומת האב יודעים לאן להכניס את האיבר החדש?

eliorar
הודעות: 35
הצטרף: 19:43 11/11/2009

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

שליחה על ידי eliorar » 00:32 17/07/2010

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

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

שלח תגובה

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