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

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


1[עריכה]

1[עריכה]

נכון.


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

מש"ל.PNG

2[עריכה]

נכון.


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

מש"ל.PNG

3[עריכה]

נכון.


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

מש"ל.PNG


4[עריכה]

לא נכון.


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



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

מש"ל.PNG

5[עריכה]

נכון.


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

מש"ל.PNG

2[עריכה]

ראשית נראה ש.


הוכחה:


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

מש"ל.PNG


כעת נראה כי


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

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

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

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

מש"ל.PNG

3[עריכה]

נקרא לזמן הריצה של Foo(n) .

1[עריכה]

הטענה נכונה.

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

2[עריכה]

אי אפשר לקבוע אם הטענה נכונה או לא.

נניח שזמן הריצה של Bar-1(n) הוא , זמן הריצה של Bar-2(n) הוא , וזמן הריצה של Bar-3(n) הוא . (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, . הטענה בבירור מתקיימת.


לחלופין, נניח שזמן הריצה של Bar-1(n) הוא , זמן הריצה של Bar-2(n) הוא , וזמן הריצה של Bar-3(n) הוא . (קל לראות שנתוני השאלה מסופקים.)

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

3[עריכה]

אי אפשר לקבוע האם הטענה נכונה או לא.

שני המקרים מהסעיף הקודם מראים זאת.

4[עריכה]

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

# Takes an array (Values) and a value (v).
# Returns the position of the largest value less than v.
# Note that the array (Values) must be sorted.
Less-Than-Pos(Values, v)
1	return Less-Than-Pos'(Values, v, 1, Length(Values))


# Takes an array (Values), a value (v), and two boundaries (left and right).
# Returns the position of the largest value less than v.
# Note that the array (Values) must be sorted.
Less-Than-Pos'(Values, v, left, right)
1	if left > right
2		return right
		
3	mid = (left + right) / 2
		
4	if v <= Values[mid]
5		return Less-Than-Pos'(Values, v, left, mid - 1)

6	if v > Values[mid]
7		return Less-Than-Pos'(Values, v, mid + 1, right)

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


הוכחה: האינדוקציה היא על right - left + 1 (אורך התחום). נקרא לכך .

(בסיס האינדוקציה) אם האורך הוא 0 או 1, אז מהתבוננות בקוד, הטענה נכונה.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל . אם 4 מתקיימת, אז v קטן מValues[mid] (או שווה לו); מספיק לכן לבדוק את האינדקס מבין האיברים בתחום השמאלי. עפ"י הנחת האינדוקציה, נקבל את התשובה הנכונה. באופן דומה, אם 6 מתקיימת, אז נקבל את התשובה הנכונה.

מש"ל.PNG

נוכיח שהסיבוכיות היא .


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

מש"ל.PNG


נממש את הפונקציה המבוקשת בעזרת פונקציית העזר:

Find-Num-In-Range(A, a, b)
1	return Less-Than-Pos(A, b) - Less-Than-Pos(A, a + 1)

נוכיח נכונות.


הוכחה: נתבונן בLess-Than-Pos(A, b).

  1. אם האינדקס הוא 0, אז כל האיברים גדולים מ.
  2. אם אינו 0, אז כל איבר שמימינו (אם יש) גדול מ או שווה לו, וכל איבר שמשמאלו קטן ממש מ.

נתבונן בLess-Than-Pos(A, a + 1).

  1. אם האינדקס הוא Length(A) + 1, אז כל האיברים קטנים מ או שווים לו.
  2. אם אינו 0, אז כל איבר שמשמאלו הוא לכל היותר , וכל איבר בו או מימינו (אם יש) גדול ממש מ.

ההוכחה מתקבלת לאחר מחשבה על כל אחד מארבעת המקרים האפשריים (צירוף שני המקרים הראשונים והאחרונים).

מש"ל.PNG

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


שימו לב:

אנא מצא מימוש הפועל בזמן לוגריתמי באורך המערך.

5[עריכה]

הפונקציה Merge עובדת בסיבוכיות , כאשר = Length(L), ו = Length(R).

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


כעת נוכיח את הנכונות באינדוקציה.


הוכחה: נוכיח באינדוקציה שבאיטרציה ה של הלולאה 3-11, מוכנס לMerged האיבר ה הקטן ביותר.

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

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

מש"ל.PNG

6[עריכה]

זו למעשה שאלה מחדו"א:

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

7[עריכה]

הטענה נכונה.


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

מש"ל.PNG


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



משפט:

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

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

8[עריכה]

1[עריכה]

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

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

2[עריכה]

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

9[עריכה]

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

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


כדאי לדעת:

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

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