מבני נתונים ואלגוריתמים - מחברת קורס/מבחן סופי מועד א' סמסטר ב' 2007 - תשובות

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

שאלה 1

הפתרון דומה מאד להוכחת הטענה שעצים אדומים-שחורים הם לוגריתמיים. נניח שגובה העץ הוא $\displaystyle h$. מה מספר המפתחות הקטן ביותר היכול להיות בעץ? קל לראות שזה המספר המתקבל כאשר כל אחד מהצמתים הוא מסוג Bar. במצב זה, היות שעל פי הנתונים כל המסלולים משורש לעלה הם בעלי אותו אורך, נקבל שמספר המפתחות הוא לכל הפחות $\displaystyle \sum _{i=1}^{h}\left[2^{i-1}\right]=2^{h}-1$. הפתרון, לכן, מתקבל על ידי פתירת אי-השוויון $\displaystyle n\geq 2^{h}-1$:

$\displaystyle n\geq 2^{h}-1\Rightarrow$
$\displaystyle n\geq 2^{h}/2\Rightarrow$
$\displaystyle \log(n)\geq h-1\Rightarrow$
$\displaystyle h=O\left(\log(n)\right)$

שאלה 2

נניח שזהו הגרף המקורי:

הגרף המקורי.

נבנה גרף חדש כך. ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏$\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

צמתי הגרף המשוכפל.

כעת נוסיף גם קשתות:

1. כל קשת בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין $\displaystyle u$ ב$\displaystyle A$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
2. כל קשת בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.התרשים הבא מראה זאת (רק חלק מהקשתות מצויירות).

(חלק) מקשתות הגרף המשוכפל.

בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle 1$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle x+1$ בין $\displaystyle |V|+u$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], אז סיבוכיות הבניה היא$\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי (כולל הקנס, אם יש), קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש, מורכב משני חלקים:

1. מסלול זהה לחלוטין למסלול מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי.
2. מסלול בעלות 1 ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$, אם החלק הראשון זוגי, ומסלול בעלות $\displaystyle x+1$, אם החלק הראשון אי-זוגי.

לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.

שאלה 3

כבר ראינו את נוסחת הנסיגה $\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]$. נשתמש בזאת כדי להוכיח את הטענה בשאלה באינדוקציה. נראה שקיים $\displaystyle c>0$ כך שתמיד $\displaystyle T(n)\geq c\cdot 2^{n}$.

הוכחה: (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונראה שהיא נכונה גם ל$\displaystyle n$.

$\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]\geq$
$\displaystyle \sum _{i=0}^{n-1}[c\cdot 2^{i}\cdot c\cdot 2^{n-i-1}]=$
$\displaystyle {\frac {c^{2}}{2}}\sum _{i=0}^{n-1}[2^{n}]=$
$\displaystyle {\frac {n\cdot c}{2}}c\cdot 2^{n}$

נפתור $\displaystyle {\frac {n\cdot c}{2}}\geq 1$, ונקבל $\displaystyle c\geq {\frac {2}{n}}$. עבור $\displaystyle n\geq 5$, נקבל שמספיק שיתקיים $\displaystyle c\geq {\frac {2}{5}}$.

מבדיקת מספר העצים השונים, עולה שקיים $\displaystyle c$ מתאים גם לבסיס האינדוקציה (המקרים $\displaystyle n\leq 4$).

שאלה 4

ראשית נניח שהמערך Mממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות $\displaystyle \Theta (n\cdot \log(n))$.

נגדיר כ$\displaystyle mp(i)$ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך $\displaystyle i$הבתים הראשונים.

משפט: לפי הגדרת $\displaystyle mp(i)$: הפתרון הטוב ביותר הוא בעל רווח $\displaystyle mp(n)$. הפונקציה נתונה על ידי נוסחת הנסיגה: $\displaystyle mp(1)=p_{1}$ לכל $\displaystyle i>1$,‏ $\displaystyle mp(i)=\max \left\{p_{i}+\max _{j|m_{i}-m_{j}>k}mp(j),mp(i-1)\right\}$ $\displaystyle mp(i)$ מונוטונית לא-יורדת ב$\displaystyle i$.

הוכחה: (2) אם $\displaystyle i=1$, אז ברור שהפתרון הרווחי ביותר הוא זה שבו בוחרים את הבית הראשון (והיחידי האפשרי לבחירה). אם $\displaystyle i>1$, אז או שבוחרים את בית $\displaystyle i$, או שלא. במקרה הראשון, מרוויחים $\displaystyle p_{i}$ מהבחירה בבית, אך לפניו אסור לבחור באף בית בעל מיקום שהפרשו מ$\displaystyle m_{i}$קטן מ$\displaystyle k$. במקרה השני, הרווח הוא בדיוק הרווח כשמותר לבחור מבין $\displaystyle i-1$הבתים הראשונים.

להלן פסוודו-קוד המממש נוסחה זו.

Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if i == 1
4		return P[1]
		
5	guess-without = Max-Profit(i - 1)
6	guess-with = P[i]
		
7	if m[i] > k
8		j = Find-Index(M, M[i] - k)
9		guess-with = guess-with + Max-Profit(M, P, k, j)
			
10	if guess-with > guess-without
11		return guess-with
12	else
13		return guess-without

חשוב רק לשים לב לקריאה לפונקציה Find-Index ב8. פונקציה זו מוצאת את האינדקס הגדול ביותר בMשקטן מM[i] - k. היות שMממויין, נוכל לעשות זאת על ידי שינוי קטן בחיפוש בינרי. נוסיף גם Memoization:

1	MP = Make-Array(n)
	
2	for i in [1, ..., n]
3		MP[i] = Nil


Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if MP[i] != Nil
4		return MP[i]
		
5	if i == 1
6		MP[1] = P[1]
7		return P[1]
		
8		guess-without = Max-Profit(i - 1)
9		guess-with = P[i]
		
10	if m[i] > k
11		j = Find-Index(M, M[i] - k)
12		guess-with = guess-with + Max-Profit(M, P, k, j)
			
13	if guess-with > guess-without
14		MP[i] = guess-with
15		return guess-with
16	else
17		MP[i] = guess-without
18		return guess-without

כעת נוסיף גם את הדפסת האיברים:

1	MP = Make-Array(n)
2	Used = Make-Array(n)
	
3	for i in [1, ..., n]
4		MP[i] = Nil


Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if MP[i] != Nil		
4		return MP[i]
		
5	if i == 1
6		MP[1] = P[1]
7		Used[1] = True
8		return P[1]
		
9		guess-without = Max-Profit(i - 1)
10		guess-with = P[i]
		
11	if m[i] > k
12		j = Find-Index(M, M[i] - k)
13		guess-with = guess-with + Max-Profit(M, P, k, j)
			
14	if guess-with > guess-without
15		MP[i] = guess-with
16		Used[i] = True
17		return guess-with
18	else
19		MP[i] = guess-without
20		Used[i] = False
21		return guess-without

המערך Used מתאר האם השתמשנו באיבר ה$\displaystyle i$או לא. נשתמש בו ע"י קריאה לPrint-Nums(k, n), כאשר Print-Nums מוגדרת כך:

Print-Nums(k, i)
1	if i &lt 1
2		return
		
3	if Used[i]
4		j = Find-Index(M, M[i] - k)
5		Print-Nums(k, j)
6	else
7		Print-Nums(k, i - 1)
			
8	if Used[i]
9		Print(i)

נותר רק לנתח את הסיבוכיות.

השורה j ← Find-Index(M, M[i] - k)אורכת $\displaystyle O(\log(n))$. אם נגדיר כ$\displaystyle T'(i)$ את זמן הקריאה לMax-Profit(M, P, k, i)בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$, אז $\displaystyle T'(i)=O(\log(n))$, והסיבוכיות היא $\displaystyle O(n\cdot \log(n))$. מצד שני, מיון המערך הוא $\displaystyle \Omega (n\cdot \log(n))$, ולכן נקבל $\displaystyle \Theta (n\cdot \log(n))$.

שאלה 5

ניצור שתי קבוצות. הקבוצה השמאלית, $\displaystyle L$ תכיל בתחילה את כל הצמתים (כלומר $\displaystyle L=V$); הקבוצה הימנית, $\displaystyle R$, תהיה ריקה בתחילה (כלומר $\displaystyle R=\emptyset$).

נאמר שקשת כלשהי $\displaystyle e=(u,v)$ שמחה אם $\displaystyle u$ ו$\displaystyle v$ שייכות לשתי קבוצות שונות. נגדיר כ $\displaystyle E(u)$ את קבוצת הקשתות היוצאות מ$\displaystyle u$, ונגדיר כ$\displaystyle H(u)$ את קבוצת הקשתות השמחות היוצאות מ$\displaystyle u$. לפי הגדרות אלו:

1. בתחילה, אף קשת אינה שמחה. ($\displaystyle \forall _{u\in U}|H(u)|=\emptyset$.)
2. אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם $\displaystyle \forall _{u\in U}|H(u)|\geq {\frac {|E(u)|}{2}}$, אז פתרנו את הבעיה.)

כעת, כל עוד לא פתרנו את הבעיה, נפעל כדלהלן. נבחר שרירותית צומת כלשהו $\displaystyle u$ מבין הצמתים שרוב קשתותיהם אינו שמח. נעביר את $\displaystyle u$ לקבוצה השניה.

דוגמה: בתרשים הבא, $\displaystyle |H(u)|=2<{\frac {|E(u)|}{2}}={\frac {5}{2}}$. לכן נעביר את $\displaystyle u$ ל$\displaystyle R$. העברת צומת והשפעתה.

המשפט הבא מראה שהתהליך הוא סופי.

משפט: בכל פעם שמעבירים צומת כלשהו $\displaystyle u$ כמתואר לעיל, עולה מספר הקשתות השמחות.

לפני הוכחת משפט זה, הבה נבין מדוע הוא מראה שהתהליך סופי. המשפט טוען שכל עוד קיים צומת כלשהו $\displaystyle u$ שרוב קשתותיו אינו שמח - העברת $\displaystyle u$ לקבוצה השניה תגדיל את מספר הקשתות השמחות. מספר הקשתות השמחות מתחיל ב0, ויכול להגיע לכל היותר ל$\displaystyle |E|$.

כעת נוכיח את המשפט.

הוכחה: נניח שהשכנים של $\displaystyle u$ בקבוצה שלו הם $\displaystyle u_{1},\ldots ,u_{i}$, ושכניו בקבוצה השניה הם $\displaystyle v_{1},\ldots ,v_{j}$. נשים לב שבהכרח $\displaystyle i>j$.

לאחר העברת $\displaystyle u$, מספר הקשתות השמחות גדל ב$\displaystyle i-j\geq 1$.