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

1

1

נכון.

הוכחה: נבחר $\displaystyle c=1$‏ ו$\displaystyle n_{0}=100$‏,‏ ונוודא $\displaystyle \forall _{n\geq 100}80\leq 1\cdot 3\cdot n$.

2

נכון.

הוכחה: נבחר $\displaystyle c=2^{1008}$‏ ו$\displaystyle n_{0}=1$‏,‏ ונוודא $\displaystyle \forall _{n\geq 1}2^{n+1003}+30=2^{1003}\cdot 2^{n}+30\leq 2^{1008}\cdot 2^{n}$.

3

נכון.

הוכחה: נבחר $\displaystyle c=3$‏ ו$\displaystyle n_{0}=1$‏,‏ ונוודא $\displaystyle \forall _{n\geq 1}2\cdot n+7\leq 3\cdot (2\cdot n+3)=6\cdot n+9$.

4

לא נכון.

הוכחה: נניח בשלילה שהטענה נכונה, ולכן עבור $\displaystyle c>0$ ו$\displaystyle n_{0}>0$ כלשהם, $\displaystyle \forall _{n\geq n_{0}}3\cdot n\leq c\cdot 1$. אם נציב $\displaystyle n=n_{0}+\left\lceil c\right\rceil ,$ נקבל

$\displaystyle (3\cdot n)|^{n_{0}+\left\lceil c\right\rceil }=3\cdot n_{0}+3\cdot \left\lceil c\right\rceil \leq$
$\displaystyle (c\cdot 1)|^{n_{0}+\left\lceil c\right\rceil }=c,$
שאינו הגיוני.

5

נכון.

הוכחה: באופן כללי, $\displaystyle \log _{b}(a)=\log _{c}(a)/\log _{c}(b)$, ולכן הביטויים הם למעשה אותו ביטוי עד כדי הכפלה בקבוע.

2

ראשית נראה ש$\displaystyle f(n)=O(g(n))$.

הוכחה: $\displaystyle \lim _{n\rightarrow \infty }{\frac {f(n)}{g(n)}}=$
$\displaystyle \lim _{n\rightarrow \infty }{\frac {n+c_{1}n\log ^{2}(n)}{n+c_{2}n^{2}}}=$
$\displaystyle \lim _{n\rightarrow \infty }{\frac {{\frac {1}{n}}+c_{1}{\frac {1}{n}}\log ^{2}(n)}{{\frac {1}{n}}+c_{2}}}=$
$\displaystyle 0$

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

כעת נראה כי $\displaystyle g(n)\neq O(f(n))$

הוכחה: נניח בשלילה כי $\displaystyle g(n)=O(f(n))$. אז קיים $\displaystyle c>0$ כך שעבור ערכי $\displaystyle n$ גדולים מספיק, $\displaystyle g(n)\leq c\cdot f(n)$.

נחלק את שני האגפים ב$\displaystyle f(n)$ (נזכר שהוא חיובי), ונקבל $\displaystyle {\frac {g(n)}{f(n)}}\leq c$ עבור ערכי $\displaystyle n$ גדולים מספיק.

ניקח גבול של שני האגפים, ונקבל $\displaystyle \lim _{n\rightarrow \infty }{\frac {g(n)}{f(n)}}\leq \lim _{n\rightarrow \infty }c=c$.

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

3

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

1

הטענה נכונה.

ברור שזמן הריצה של Foo(n) לפחות גדול כמו זמן הריצה של Bar(n). לכן נקבל $\displaystyle f(n)\geq \Omega (n^{2}\log(n))\Rightarrow f(n)=\Omega (n^{2}\log(n))$. אבל $\displaystyle n^{2}\log(n))=\Omega (n)$, ולכן הטענה נובעת מטרנזיטיביות.

2

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

נניח שזמן הריצה של Bar-1(n) הוא $\displaystyle 10n^{4}$, זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2n^{2}$, וזמן הריצה של Bar-3(n) הוא $\displaystyle n$. (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, $\displaystyle f(n)=10n^{4}+1.2n^{2}+n=\Theta (n^{4})$. הטענה בבירור מתקיימת.

לחלופין, נניח שזמן הריצה של Bar-1(n) הוא $\displaystyle 10n^{2}\log(n)$, זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2n^{2}$, וזמן הריצה של Bar-3(n) הוא $\displaystyle n$. (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, $\displaystyle f(n)=10n^{2}\log(n)+1.2n^{2}+n=\Theta (n^{2}\log(n))$. קל להראות (באופן דומה לזה שראינו בתרגילים קודמים) שלא ייתכן שבמקרה זה $\displaystyle f(n)=\Omega (n^{3})$.

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 (אורך התחום). נקרא לכך $\displaystyle n$.

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

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

נוכיח שהסיבוכיות היא $\displaystyle \Theta (\log(n))$.

הוכחה: קל לראות שנוסחת הנסיגה של הפונקציה היא $\displaystyle T(n)=T(n/2)+O(1)$. המשך ההוכחה דומה לאחת הדוגמות שראינו בפרישה.

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

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, אז כל האיברים גדולים מ$\displaystyle b$.
2. אם אינו 0, אז כל איבר שמימינו (אם יש) גדול מ$\displaystyle b$ או שווה לו, וכל איבר שמשמאלו קטן ממש מ$\displaystyle b$.

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

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

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

קל לראות שהסיבוכיות היא $\displaystyle \Theta (\log(n))$, משום שהאלגוריתמים מורכב משתי קריאות לפונקציית העזר שבנינו.

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

5

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

קל מאד לראות שהלולאה רצה בדיוק $\displaystyle |L|+|R|$ פעמים. בנוסף, כל איטרציה רצה בזמן $\displaystyle O(1)$ - בלי קשר לשאלה איזה רצף של if / else if / else מתבצע, זמן הריצה של איטרציה בודדת עולה לכל הפחות קבוע כלשהו, ולכל היותר קבוע כלשהו. דברים אלה מוכיחים הן את הסופיות והן את ניתוח הסיבוכיות.

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

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

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

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

6

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

1. היות ש$\displaystyle f(n)$ מונוטונית לא יורדת, אז:
   • $\displaystyle \int _{m-1}^{n}f(x)dx=\sum _{i=m-1}^{n-1}\int _{i}^{i+1}f(x)dx\leq \sum _{i=m-1}^{n-1}\int _{i}^{i+1}f(i+1)dx=\sum _{i=m}^{n}[f(i)]$
   • $\displaystyle \int _{m}^{n+1}f(x)dx=\sum _{i=m}^{n}\int _{i}^{i+1}f(x)dx\geq \sum _{i=m}^{n}\int _{i}^{i+1}f(i)dx=\sum _{i=m}^{n}[f(i)]$
2. כפי שנכתב בשאלה, המקרה שבו $\displaystyle f(n)$ מונוטונית יורדת דומה מאד.

7

הטענה נכונה.

הוכחה: נניח בשלילה שהטענה מוטעית, ואכן $\displaystyle f(n)=\Theta (g(n))$. עפ"י ההגדרה, לכן, קיימים שני קבועים $\displaystyle c''>0$ ו$\displaystyle c'>0$ כך שלערכי $\displaystyle n$ גדולים מספיק, $\displaystyle c''\cdot g(n)\leq f(n)\leq c'\cdot g(n)$. נחלק ב$\displaystyle g(n)$ (שימו לב שאין צורך להפוך את סימני $\displaystyle \leq$), ונקבל $\displaystyle c''\leq f(n)/g(n)\leq c'$. מכללים ידועים בחדו"א, הוכחנו כעת שגבול המנה (אם הוא קיים) חסום בין $\displaystyle c''$ ל$\displaystyle c'$, בסתירה לנתון בשאלה.

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

משפט: $\displaystyle f(n)$ ו$\displaystyle g(n)$ הן פונקציות חיוביות ממש, והגבול $\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]$ קיים ושווה ל$\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=c$. אם $\displaystyle c=0$ אז $\displaystyle f(n)\neq \Omega (g(n))$. אם $\displaystyle c=\infty$ אז $\displaystyle f(n)\neq O(g(n))$.

8

1

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

$\displaystyle f(n)+g(n)\geq \max\{f(n),g(n)\}$,
$\displaystyle f(n)+g(n)\leq 2\cdot \max\{f(n),g(n)\}$.
הטענה, לכן, נכונה.

2

ניקח $\displaystyle f(n)=n+1$, ו$\displaystyle g(n)=n$. קל לראות ש$\displaystyle f(n)-g(n)=1\neq \Theta (n)=\Theta (\max\{f(n),g(n)\})$:‏ הוכחנו בכיתה ש$\displaystyle n^{2}\neq O(n)$, ובאותו אופן בדיוק אפשר להראות ש $\displaystyle 1\neq \Omega (n)$. הטענה, לכן, איננה נכונה.

9

נבנה את הפונקציה $\displaystyle g(n)$ כך:

1. ראשית נקבע צמדים של נקודות.
   1. נקבע $\displaystyle n_{0}=1$,‏ ו$\displaystyle n_{1}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{1})\geq 2\cdot f(n_{0})$ ‏(חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏‏.
   2. נקבע $\displaystyle n_{2}=n_{1}+1$,‏ ו$\displaystyle n_{3}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{3})\geq 2\cdot f(n_{2})$ (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏.
   3. נמשיך כך הלאה: נקבע $\displaystyle n_{4}=n_{3}+1$,‏ ו$\displaystyle n_{5}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{5})\geq 2\cdot f(n_{4}$) (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏, וכולי.
2. כעת נגדיר את $\displaystyle g(n)$ בעזרת הזוגות:
   1. עבור $\displaystyle n_{0}\leq n<n_{1}$,‏ $\displaystyle g(n)=f(n_{0})$;‏ $\displaystyle g(n_{1})=f(n_{1})/2$.
   2. עבור $\displaystyle n_{2}\leq n<n_{3}$,‏ $\displaystyle g(n)=f(n_{2})$;‏ $\displaystyle g(n_{3})=f(n_{3})/2$.
   3. עבור $\displaystyle n_{4}\leq n<n_{5}$,‏ $\displaystyle g(n)=f(n_{4})$;‏ $\displaystyle g(n_{5})=f(n_{5})/2$. נמשיך כך הלאה והלאה.מהבניה קל לראות את הדברים הבאים:
   4. $\displaystyle g(n)$ פונקציה מונוטונית עולה.
   5. בכל נקודה ונקודה, $\displaystyle g(n)$ נמצאת בין $\displaystyle f(n)$ ל$\displaystyle f(n)/2$. לכן $\displaystyle g(n)=\Theta (f(n))$ בהכרח.
   6. יש אינסוף נקודות בהן $\displaystyle f(n)=g(n)$, אבל גם אינסוף נקודות בהן $\displaystyle g(n)=f(n)/2$, ולכן לא ייתכן שהגבול $\displaystyle f(n)/g(n)$ קיים.

כדאי לדעת: לכאורה אפשר לבנות פונקציה $\displaystyle g_{1}(n)$ פשוטה הרבה יותר מהמוצגת כאן, לדוגמה: $\displaystyle g_{1}(n)=f(n)$ אם $\displaystyle n$ זוגי. $\displaystyle g_{1}(n)=f(n)/2$ אם $\displaystyle n$ אי זוגי. עם זאת, אמרנו בתחילת הדף על סדרי גדילה שנתמקד בקורס בפונקציות מונוטוניות לא יורדות, והפונקציה $\displaystyle g(n)$ שנבנתה כאן אכן מונוטונית לא יורדת.