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

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


תרגום ביטויים מפורשים לסדרי גדילה[עריכה]

שאלה[עריכה]

נתונות שתי פונקציות:



כאשר .

  1. האם ?
  2. האם ?


תשובה[עריכה]

ראשית נראה ש.


הוכחה:


הטענה נובעת, לכן, מכלל הגבולות בסדרי גדילה.

מש"ל.PNG


כעת נראה כי


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

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

ניקח גבול של שני האגפים, ונקבל .

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

מש"ל.PNG

שאלה בסיסית ביחסים[עריכה]

שאלה[עריכה]

אנא הוכח או הפרך את הטענות הבאות:

  1. .
  2. .
  3. .
  4. .
  5. .


שימו לב:

הכוונה בסעיף הראשון לפונקציה הקבועה ,‏ ולא לקבוע 80.

תשובה[עריכה]

1[עריכה]

נכון.


הוכחה: נבחר ‏ ו‏,‏ ונוודא .

מש"ל.PNG

2[עריכה]

נכון.


הוכחה: נבחר ‏ ו‏,‏ ונוודא .

מש"ל.PNG

3[עריכה]

נכון.


הוכחה: נבחר ‏ ו‏,‏ ונוודא .

מש"ל.PNG


4[עריכה]

לא נכון.


הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור ו כלשהם, . אם נציב נקבל



שאינו הגיוני.

מש"ל.PNG

5[עריכה]

נכון.


הוכחה: באופן כללי, , ולכן הביטויים הם למעשה אותו ביטוי עד כדי הכפלה בקבוע.

מש"ל.PNG

הוכחת אדיטיביות[עריכה]

שאלה[עריכה]

אנא הוכח את כלל האדיטיביות ל: לכל ,‏

.

תשובה[עריכה]

ההוכחה דומה למדי להוכחת האדיטיביות שראינו בהרצאה:


הוכחה: (1) עפ"י ההגדרה:

  • משמעו שלכל ,‏ ,‏ עבור כלשהם.
  • משמעו שלכל,‏ ,‏ עבור כלשהם.

לכן:

  • לכל ,‏ .
  • לכל ,‏ .

מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.

מש"ל.PNG

הוכחת טרנזיטיבות[עריכה]

שאלה[עריכה]

אנא הוכח את טרנזיטיביות ל:


לכל ,

.

תשובה[עריכה]

ההוכחה דומה למדי להוכחת הטרנזיטיביות שראינו:

(1) עפ"י ההגדרה:

  • משמעו שלכל ,‏ ,‏ עבור כלשהם.
  • משמעו שלכל,‏ ,‏ עבור כלשהם.

לכן:

  • לכל ,‏ .
  • לכל ,‏ .

מקבלים את התוצאה ע"י הצבת שני האי-שוויונים האחרונים אחד בשני:

  • לכל ,‏‏ .

עוד כללים בסדרי גדילה[עריכה]

שאלה[עריכה]

הן פונקציות חיוביות ממש. אנא הוכח או הפרך כ"א מהכללים הבאים:


כדאי לדעת:

משמעות הביטוי בצד שמאל של סעיף 4 הוא הפונקציה פלוס פונקציה כלשהי ששייכת ל.


תשובה[עריכה]

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

  1. לא נכון. נפריך ע"י .
  2. לא נכון. נפריך ע"י .
  3. לא נכון. נפריך ע"י .
  4. לכל פונקציה מתקיים ש, עבור כלשהם, החל מ כלשהו. לכן, החל מאותו ,‏‏
    ‏ מה שמוכיח את הטענה.
  5. (לפי כללים פשוטים מחדו"א),

ולכן עפ"י כללי הגבולות שראינו, הטענה נכונה.

כללים לגבי מקסימום[עריכה]

שאלה[עריכה]

אנא הוכח או הפרך כ"א מהכללים הבאים:


תשובה[עריכה]

1[עריכה]

נשים לב שתמיד מתקיים:

,
.
הטענה, לכן, נכונה.

2[עריכה]

ניקח , ו. קל לראות ש:‏ הוכחנו בכיתה ש, ובאותו אופן בדיוק אפשר להראות ש . הטענה, לכן, איננה נכונה.


כלל שלילי בגבולות[עריכה]

שאלה[עריכה]

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


תשובה[עריכה]

הטענה נכונה.


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

מש"ל.PNG


באופן דומה למדי, נוכל להוכיח את המשפט הבא:



משפט:

ו הן פונקציות חיוביות ממש, והגבול קיים ושווה ל.

  1. אם אז .
  2. אם אז .


יחסים בין פולינומים[עריכה]

שאלה[עריכה]

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


תשובה[עריכה]

נניח ש פולינום מדרגה , ו פולינום מדרגה . אז:

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


הכוון השני לכללי הגבולות[עריכה]

שאלה[עריכה]

היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה כך שמתקיים אבל הגבול אינו קיים.


תשובה[עריכה]

נבנה את הפונקציה כך:

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


כדאי לדעת:

לכאורה אפשר לבנות פונקציה פשוטה הרבה יותר מהמוצגת כאן, לדוגמה:
  1. אם זוגי.
  2. אם אי זוגי.

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

טור פולינומים[עריכה]

שאלה[עריכה]

הם שני קבועים שלמים גדולים ממש מ1. אנא הוכח שמתקיים .


תשובה[עריכה]

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

טור כפול[עריכה]

שאלה[עריכה]

הפונקציה נתונה על ידי הנוסחה. .

אנא הוכח .


רמז

נסה להוכיח זאת באותו אופן בו הוכחנו . כלומר:

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


תשובה[עריכה]

שיטה א'[עריכה]

נשתמש באותו הרעיון בו השתמשתנו כדי לנתח טור של לוגריתמים.


ראשית נראה כי .


הוכחה:
.

מש"ל.PNG

כעת נראה כי .


הוכחה: .
נשים לב שכאשר בתחום ו בתחום , אז .

לכן נקבל

.

מש"ל.PNG

שיטה ב'[עריכה]

.

נשים לב שעבור ערך כלשהו, נוכל לבצע את החלפת המשתנים , ונקבל .

נציב זאת חזרה בסכום הכפול: .


נבצע החלפת משתנים , ונקבל:

.


חסם על טור לבניית ערימה בינרית ממערך[עריכה]

שאלה[עריכה]

אנא הוכח ש.


רמז

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


כדאי לדעת:

נצטרך חסם זה כשננתח את סיבוכיות בניית ערימה בינרית ממערך.

תשובה[עריכה]

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

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

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


כדאי לדעת:

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