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

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

תוכן עניינים

1 שאלה 1
2 שאלה 2
3 שאלה 3
4 שאלה 4
5 שאלה 5

[עריכה] שאלה 1

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

$\displaystyle n \ge 2^h - 1 \Rightarrow$
$\displaystyle n \ge 2^h / 2 \Rightarrow$
$\displaystyle \log(n) \ge 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$ .‏ התרשים הבא מראה זאת.

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

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

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

לכל צומת $\displaystyle u$ ב $\displaystyle A$ , נמתח קשת במחיר $\displaystyle 1$ בין $\displaystyle u$ ב $\displaystyle A$ לבין $\displaystyle 2 \cdot |V| + u$ ‏ ב $\displaystyle C$ .
לכל צומת $\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$ בגרף החדש, מורכב משני חלקים:

מסלול זהה לחלוטין למסלול מ $\displaystyle s$ ל $\displaystyle u$ בגרף המקורי.
מסלול בעלות 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) \ge c \cdot 2^n$ .

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

$\displaystyle T(n) = \sum_{i = 0}^{n - 1}[T(i) \cdot T(n - i - 1)] \ge$
$\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} \ge 1$ , ונקבל $\displaystyle c \ge \frac{2}{n}$ . עבור $\displaystyle n \ge 5$ , נקבל שמספיק שיתקיים $\displaystyle c \ge \frac{2}{5}$ .

מבדיקת מספר העצים השונים, עולה שקיים $\displaystyle c$ מתאים גם לבסיס האינדוקציה (המקרים $\displaystyle n \le 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 &amp;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$ . לפי הגדרות אלו:

בתחילה, אף קשת אינה שמחה. ( $\displaystyle \forall_{u \in U}|H(u)| = \emptyset$ .)
אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם $\displaystyle \forall_{u \in U}|H(u)| \ge \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$ .