מציג תוצאות 1 עד 12 מתוך 12

אשכול: מבני נתונים - משפט האב

  1. #1
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל מבני נתונים - משפט האב

    שלום חברים.

    התחלנו ללמוד את משפט האב במבני נתונים, והאמת שדי הלכתי לאיבוד, במיוחד במשפט האב המלא.
    לא הכי הבנתי את המשמעות של המשפט הזה, על אילו אלגוריתמים הוא באמת רלוונטי, איך הוא לגמרי עובד.

    אני אשמח לעזרה דרך התרגיל הזה, אולי דרכו מישהו יוכל להסביר לי מה קורה טוב יותר.

    תודה רבה
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: png עלה.png‏ (116.1 ק"ב , 17 צפיות) Let T : N→ Rtand write an expression for the tightest upper asymptotic bound of T(n) you can find (i.e. afunction g:N +Rsuch that T(n) = O(g(n))) and prove its correctness by induction for the following cases.Assume for all of these T(1) = 1:2. T(n) = 2T (L ]) +n3. Explain the logic for the correctness of the bound, without a formal proof: T(n) = (Hint: use the fact that Di-o x converges for (x) < 1)


  2. #2
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    בשיטת האב מסתכלים על נוסחת נסיגה מהצורה:
    $$T(n)=a T\left( \frac{n}{b} \right) + f(n), ~ 1\leq a, ~ 1 < b$$
    בסעיף 2 מתקיים $a=b=2, ~ f(n)=n$. מתקיים $f(n)=n=\Theta (n^{\log_b a})=\Theta (n)$. לכן לפי שיטת האב (אחד המקרים):
    $$T(n)=\Theta(n^{\log_b a} \log n)=\Theta (n \log n)$$

    אין משהו מיוחד לדעת בשיטה הזו. צריך רק לראות שהמבנה של נוסחת הנסיגה תואם למבנה של שיטת האב, שהתנאים של אחד המקרים בשיטה מתקיימים ולפיו מתאימים את החסם.
    אהבתי Helpme אהב \ אהבו את התגובה
     

  3. #3
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי Yes צפה בהודעה
    בשיטת האב מסתכלים על נוסחת נסיגה מהצורה:
    $$T(n)=a T\left( \frac{n}{b} \right) + f(n), ~ 1\leq a, ~ 1 < b$$
    בסעיף 2 מתקיים $a=b=2, ~ f(n)=n$. מתקיים $f(n)=n=\Theta (n^{\log_b a})=\Theta (n)$. לכן לפי שיטת האב (אחד המקרים):
    $$T(n)=\Theta(n^{\log_b a} \log n)=\Theta (n \log n)$$

    אין משהו מיוחד לדעת בשיטה הזו. צריך רק לראות שהמבנה של נוסחת הנסיגה תואם למבנה של שיטת האב, שהתנאים של אחד המקרים בשיטה מתקיימים ולפיו מתאימים את החסם.
    טוב זה די רובוטי אבל שיהיה...
    מה לגבי הסעיף האחרון?


  4. #4
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    זה באמת רובוטי. זה היופי במשפטים (נכונים), אתה יכול להשתמש בהם כמו קופסה שחורה שהקלטים שלה זה ההנחות של המשפט והפלט הוא התוצאה של המשפט.

    לגבי הסעיף האחרון יש לך כבר רמז, אז אשאל - מה ניסית?
    אהבתי Helpme אהב \ אהבו את התגובה
     

  5. #5
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

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


  6. #6
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    עריכה: לא ראיתי שלמדת רק את השיטה הזו. אז חשבתי טיפה ובעצם כן אפשר להשתמש בשיטת האב. תחשוב איך אפשר להשתמש בעובדה שזה סכום לינארי כדי לחסום מלמעלה ולמטה בנפרד.
    נערך לאחרונה על ידי Yes, 22-03-2019 בשעה 23:15
    אהבתי Helpme אהב \ אהבו את התגובה
     

  7. #7
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

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


  8. #8
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    הכוונה שהרקורסיה היא צירוף לינארי. בכל אופן, אם נסמן $T_1(n)=5 T_1\left(\left\lfloor \frac{n}{5}\right\rfloor\right)+n$ ו-$T_2(n)=5 T_2\left(\left\lfloor \frac{n}{10}\right\rfloor\right)+n$, אז מתקיים:
    $$T_2(n) \leq T(n) \leq T_1(n)$$
    אהבתי Helpme אהב \ אהבו את התגובה
     

  9. #9
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי Yes צפה בהודעה
    הכוונה שהרקורסיה היא צירוף לינארי. בכל אופן, אם נסמן $T_1(n)=5 T_1\left(\left\lfloor \frac{n}{5}\right\rfloor\right)+n$ ו-$T_2(n)=5 T_2\left(\left\lfloor \frac{n}{10}\right\rfloor\right)+n$, אז מתקיים:
    $$T_2(n) \leq T(n) \leq T_1(n)$$
    אוקיי סבבה.
    אבל מה הפואנטה של השאלה בהקשר הזה?
    איך הסיפור הזה מסביר לנו את הלוגיקה של נכונות החסימות של הסיבוכיות הזאת?
    איזו מין תשובה הם מחפשים?

    מצטער שאני שואל יותר מדי שטויות, פשוט הסיפור מאוד זר לי.


  10. #10
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    אתה מוצא את החסם באמצעות שיטת האב, ואז מסביר אותה בדרך חלופית שנעזרת ברמז שהם נתנו.
    אני אתן לך עוד קצת כיוון אם הרמז לא הספיק - תנסה לפרק את הנוסחה בצורה רקורסיבית עוד ועוד ותראה מה מתקבל.
    אהבתי Helpme אהב \ אהבו את התגובה
     

  11. #11
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי Yes צפה בהודעה
    אתה מוצא את החסם באמצעות שיטת האב, ואז מסביר אותה בדרך חלופית שנעזרת ברמז שהם נתנו.
    אני אתן לך עוד קצת כיוון אם הרמז לא הספיק - תנסה לפרק את הנוסחה בצורה רקורסיבית עוד ועוד ותראה מה מתקבל.
    נראה כמו משפט הסנדוויץ'.
    אני צודק?


  12. #12
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    משהו כזה. מן הסתם זה לא משפט הסנדוויץ', אבל יש דימיון. אם תעלה את הניסיון שלך, אני אוכל להגיד אם אתה בכיוון הנכון.
    אהבתי Helpme אהב \ אהבו את התגובה
     

מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 3

הרשאות

  • אתה לא יכול לפרסם אשכולות חדשים
  • אתה לא יכול לפרסם תגובות
  • אתה לא יכול לצרף קבצים להודעותיך
  • אתה לא יכול לערוך את הודעותיך
  •  
אודות Emath
האתר Emath הינו יוזמה פרטית והוקם בתחילת שנת 2008 .
מטרתנו הינה למנף את הישגי התלמידים למתמטיקה ופיסיקה בארץ בכלל ובפרט בקרב תלמידי התיכון .
אנו מספקים מספר שירותים לתלמיד, ביניהם גישה למאות אלפי פתרונות איכותיים לתרגילים, פורום עזרה במתמטיקה ופיסיקה הגדול מסוגו בארץ, מאגר סיכומים, מרתונים בוידאו, פתרונות לבגרויות ועוד.
כלים אלו, מאפשרים לכל אחד, ללא תלות במיקומו, ללמוד, לתרגל ולהתמקצע על-מנת להתכונן בצורה מיטבית לבגרות במתמטיקה או פיסיקה .

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו