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

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

שימו לב: *נא להגיש רק את שאלות 1-5. שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1

הפונקציה $\displaystyle T(n)$ נתונה על ידי הנוסחה. $\displaystyle T(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]$.

אנא הוכח $\displaystyle T(n)=\Theta (n^{3})$.

רמז נסה להוכיח זאת באותו אופן בו הוכחנו $\displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))$. כלומר: הוכח בנפרד חסמי $\displaystyle O$ ו$\displaystyle \Omega$. ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).

2

א'

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

1. $\displaystyle T(n)=3\cdot T(n/2)+n\cdot \log(n)$.‏
2. $\displaystyle T(n)=T(n-1)+\log(n)$.‏
3. $\displaystyle T(n)=T(\alpha \cdot n)+T((1-\alpha )\cdot n)+\Theta (n)$, כאשר $\displaystyle 0<\alpha <1$ הוא קבוע כלשהו.‏

ב'

בנוסחת הנסיגה $\displaystyle T(n)=T({\sqrt {n}})+\log(n)$,‏ $\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו. אנא פתור את הנוסחה.

3

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם $\displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)$ אז $\displaystyle T(n)=\Omega (1.5^{n})$.

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

4

להלן פסוודו-קוד לפונקציה Foo, המקבלת מספר שלם לא-שלילי ומחזירה מספר שלם:

Foo(n)
1	if n == 0
2		return 0

3	return n % 2 + Foo( ⌊n / 2⌋ )

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

5

A[1, ..., n] הוא מערך של מספרים שונים זה מזה. נאמר ש$\displaystyle (i,j)$ הוא היפוך אם $\displaystyle i<j$ אך A[i] > A[j].

1. במערך [2, 3, 8, 6, 1] יש 5 היפוכים. אנא רשום אותם.
2. אנא מצא אלגוריתם יעיל למציאת מספר ההיפוכים במערך.

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

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

6

הפונקציה Alg מוגדרת כך:

Alg(A, i, j)
1	if j <= i + 1
2		return
	
3	q = Sqrt(j - i + 1) # q = ⌊(j - i + 1)^(1/2)⌋
4	for k in [0, ..., q - 1]
5		Alg(A, i + k * q, i + (k + 1) * (q - 1))

6	Proc(A, i, j)

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

1. הפונקציה Sqrt(n) מחזירה את השורש הריבועי של $\displaystyle n$ מעוגל כלפי מטה. היא פועלת בזמן $\displaystyle O(1)$.
2. הפונקציה Proc היא פונקציה כלשהי המקיימת שזמן ריצת Proc(A, i, j) הוא $\displaystyle \Theta (j-i)$.

מהו זמן הריצה של Alg(A, 1, n)?

7

נתונה מטריצה בת $\displaystyle n$ עמודות ו$\displaystyle m=2^{n}-1$ שורות. כל כניסה במטריצה היא 0 או 1, ולכן כל שורה מתארת מספר בינרי בעל $\displaystyle n$ ביטים. השורות אינן מסודרות בסדר ידוע, אך ידוע שאין שתי שורות זהות. מכאן נובע שחסרה שורה להשלמת כל $\displaystyle 2^{n}$ המספרים האפשריים בעלי $\displaystyle n$ ביטים.

דוגמה: עבור $\displaystyle n=2$, ייתכן שהשורה הראשונה היא המערך [0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).

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

רמז נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.

8

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

משפט: פתרון $\displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]$ הוא $\displaystyle O\left(n\cdot \log(n)\right)$ .

9

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו, והיא פתרונה של נוסחת הנסיגה $\displaystyle T(n)=a\cdot T\left({\frac {n}{b}}\right)+f(n)$.‏ בנוסחה זו, $\displaystyle a$ מספר שלם גדול ממש מ1, $\displaystyle b$ מספר גדול ממש מ1, ו$\displaystyle f(n)$ היא פונקציה המקיימת $\displaystyle f(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k}(n)\right)$, עבור $\displaystyle k$ שלם גדול ממש מ1. אנא הוכח $\displaystyle T(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k+1}(n)\right)$.