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


תרגום ביטויים מפורשים לסדרי גדילה

עריכה

שאלה

עריכה

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

 
 
כאשר  .

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


תשובה

עריכה

ראשית נראה ש .


הוכחה:  
 
 
 

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

 


כעת נראה כי  


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

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

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

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

 

שאלה בסיסית ביחסים

עריכה

שאלה

עריכה

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

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


 

שימו לב:

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

תשובה

עריכה

נכון.


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

 

נכון.


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

 

נכון.


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

 


לא נכון.


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

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

 

נכון.


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

 

הוכחת אדיטיביות

עריכה

שאלה

עריכה

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

 .

תשובה

עריכה

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


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

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

לכן:

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

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

 

הוכחת טרנזיטיבות

עריכה

שאלה

עריכה

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


לכל  ,

 .

תשובה

עריכה

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

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

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

לכן:

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

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

  • לכל  ,‏‏  .

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

עריכה

שאלה

עריכה

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

  1.  
  2.  
  3.  
  4.  
  5.  


 

כדאי לדעת:

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


תשובה

עריכה

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

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

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

כללים לגבי מקסימום

עריכה

שאלה

עריכה

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

  1.  
  2.  


תשובה

עריכה

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

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

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


כלל שלילי בגבולות

עריכה

שאלה

עריכה

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


תשובה

עריכה

הטענה נכונה.


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

 


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



משפט:

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

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


יחסים בין פולינומים

עריכה

שאלה

עריכה

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


תשובה

עריכה

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

  •  
  •  
  •  

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


הכוון השני לכללי הגבולות

עריכה

שאלה

עריכה

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


תשובה

עריכה

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

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


 

כדאי לדעת:

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

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

טור פולינומים

עריכה

שאלה

עריכה

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


תשובה

עריכה

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

טור כפול

עריכה

שאלה

עריכה

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

אנא הוכח  .


רמז

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

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


תשובה

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

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


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


הוכחה:  
.

 

כעת נראה כי  .


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

לכן נקבל

 .

 

שיטה ב'
עריכה

 .

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

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


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

  .


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

עריכה

שאלה

עריכה

אנא הוכח ש .


רמז

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


 

כדאי לדעת:

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

תשובה

עריכה

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

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

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


 

כדאי לדעת:

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