לדלג לתוכן

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

נוסחת נסיגה עם שורש

[עריכה]

שאלה

[עריכה]

בנוסחת הנסיגה ,‏ מתארת את זמן הריצה של אלגוריתם כלשהו. אנא פתור את הנוסחה.


תשובה

[עריכה]

נשתמש בפרישה.בעץ המתאים לנוסחה:

  1. צומת הראש מציין את , והרמה הראשונה תורמת .
  2. ברמה הבאה, הצומת מציין את , והרמה תורמת .
  3. ברמה הבאה אחריה, הצומת מציין את , והרמה תורמת .

החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה (כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את , והרמה תורמת .

כדי למצוא את גובה העץ, , נפתור :




כאמור, הרמה ה תורמת . נותר, לכן, לסכם את :




נוסחת נסיגה לבעיית "דג הסלמון"

[עריכה]

שאלה

[עריכה]

מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם אז .


כדאי לדעת:

נצטרך את פתרונה של נוסחת נסיגה זו בבעיית "דג הסלמון".


תשובה

[עריכה]

הוכחה: נוכיח באינדוקציה שקיים כך ש.

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





אם ניקח ,‏ אז הביטוי האחרון גדול מ.


(בסיס האינדוקציה) היות ש,‏ אז ,‏ עבור כלשהו. נפתור ,‏ ונקבל .‏

האינדוקציה, לכן, נכונה עבור , החל מ.


נוסחת נסיגה לאיחוד קבוצות זרות על פי גודל

[עריכה]

שאלה

[עריכה]

אנא הוכחה את המשפט הבא:



משפט:

פתרון
הוא
.


כדאי לדעת:

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

תשובה

[עריכה]

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

(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,



עבור קבוע כלשהו.

נגזור את הביטוי שבתוך ה, ונקבל

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

כאשר, אז




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

נוסחות נסיגה פשוטות

[עריכה]

שאלה

[עריכה]

מתארת את זמן הריצה של אלגוריתם כלשהו.

  1. אנא הוכח שפתרון נוסחת הנסיגה הוא .
  2. אנא הוכח שפתרון נוסחת הנסיגה הוא .


הנחיות

להלן הנחיות לסעיף הראשון:

  1. אנא הסבר מדוע מותר לקבוע ש עבור קבוע כלשהו.
  2. נניח שקיים קבוע כך שלכל מתקיים ‎. אנא הסבר מדוע בהכרח . אנא מצא תנאי על כך שבהכרח נובע מכך כי .
  3. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח .
  4. נניח שקיים קבוע כך שלכל מתקיים ‎. אנא הסבר מדוע בהכרח . אנא הסבר מה התנאי על כך שינבע מכך כי .
  5. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח .
  6. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח .

תשובה

[עריכה]

כרגיל, מותר לנו לקבוע ש עבור קבוע כלשהו, וזאת משום ש מתארת את זמן הריצה של אלגוריתם.


נוכיח ש‎‎. ליתר דיוק, נוכיח באינדוקציה שקיים כך ש .


הוכחה: (בסיס האינדוקציה) עבור , נקבל , כלומר כל שצריך הוא לבחור המקיים .

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


לסיכום, עבור , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

נוכיח ש‎‎. ליתר דיוק, נוכיח באינדוקציה שקיים כך ש .


הוכחה: (בסיס האינדוקציה) עבור , נקבל , כלומר כל שצריך הוא לבחור המקיים .

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


לסיכום, עבור , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

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

חסמים עליונים ותחתונים למספר נוסחאות נסיגה

[עריכה]

שאלה

[עריכה]

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

  1. .‏
  2. .‏
  3. , כאשר הוא קבוע כלשהו.‏

תשובה

[עריכה]

, עפ"י מקרה 1 של משפט המאסטר.

נפרוש את הנוסחה:






(את המעבר האחרון ראינו בטורים שימושיים.)

נגדיר . בלי הגבלת הכלליות, נניח ש. להלן עץ הפרישה המתקבל:

עץ הפרישה.
עץ הפרישה.

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

קל לראות שכל רמה מלאה בעץ תורמת .‏ הרמה הראשונה תורמת ;‏ הרמה השניה תורמת ,‏ הרמה השלישית תורמת ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש חסומה מלמטה ע"י , וחסומה מלמעלה ע"י . אבל היות ש וכן , אז .

נוסחת נסיגה שאיננה מתאימה למשפט המאסטר

[עריכה]

שאלה

[עריכה]

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

תשובה

[עריכה]

נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם . ברמה השניה יש צמתים, וכל אחד מהם תורם . ברמה ה (בהנחה שהרמה הראשונה היא ב), יש צמתים, וכל אחד מהם תורם . אנו יודעים שגובה העץ הוא . נפשט:






נשים לב שעפ"י חסמי האינטגרלים לטורים,‏ .

נוסחת נסיגה קלה

[עריכה]

שאלה

[עריכה]

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה קלה/שאלה

תשובה

[עריכה]

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה קלה/תשובה

נוסחת נסיגה מנחוסה

[עריכה]

שאלה

[עריכה]

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה מנחוסה/שאלה

תשובה

[עריכה]

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה מנחוסה/תשובה