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

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

< מבני נתונים ואלגוריתמים - מחברת קורס

קפיצה אל: ניווט, חיפוש

תבנית:התנצלות לשון זכר

מבני נתונים ואלגוריתמים - מחברת קורס

תוכן עניינים

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

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

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה $\displaystyle m + n + 2$ צמתים:

צמתים $\displaystyle s_1, \ldots s_m$ , אחד לכל סטודנט
צמתים $\displaystyle t_1, \ldots t_n$ , אחד לכל חברה
צומת מקור $\displaystyle s$ וצומת בור $\displaystyle t$

נגדיר כ $\displaystyle w$ את Length(W).

בגרף יש $\displaystyle w + m + n$ קשתות:

קשת אחת לכל איבר בW בעלת קיבול 1
קשת מ $\displaystyle s$ לכל $\displaystyle s_i$ בעלת קיבול 1
קשת מכל $\displaystyle t_j$ ל $\displaystyle t$ בעלת קיבול $\displaystyle P[j]$

כעת נריץ את אלגוריתם Ford-Fulkerson. נחזיר כתשובה כל זוג $\displaystyle (s_i, t_j)$ שעבורו קיבלנו $\displaystyle f_{s_i, t_j} = 1$ .

משפט:

האלגוריתם מחזיר תשובה נכונה.

הוכחה: אנו יודעים שאלגוריתם Ford-Fulkerson משפר תמיד בגדלים שלמים (שהרי הקיבולים שלמים). קל מאד להוכיח (פורמלית, באינדוקציה), שבמקרה זה, חלק מהקשתות מ $\displaystyle s_i$ ל $\displaystyle t_j$ יזרימו 1, והשאר 0 (אלו האפשרויות היחידות). נצייר את הגרף המתקבל ממחיקת הקשתות שאינן מזרימות כלום:

נניח שיש קשת בין $\displaystyle s_i$ ל $\displaystyle t_j$ . בהכרח הקשת מזרימה 1. מצד שני, הקשת המזרימה מ $\displaystyle s$ ל $\displaystyle s_i$ מזרימה גם היא 1. משימור הזרם נובע אם כן שאין קשת אחרת היוצאת מ $\displaystyle s_i$ .טענה כמעט זהה מראה שאין קשת אחרת הנכנסת ל $\displaystyle t_j$ . ברור גם שקשת זו היתה שייכת לגרף המקורי. מכאן נובע שהמערך המוחזר W' אכן משייך אחת לאחת סטודנט לחברה, ואינו ממציא שיוכים שלא הופיעו במקור. קל גם לראות שכל חברה אינה מעסיקה יותר סטודנטים מיכולתה. קל לראות שאם יש התאמה גדולה יותר, אז אפשר להגיע לזרימה גדולה יותר מהמושגת כאן, וזאת בסתירה לנכונות Ford-Fulkerson.

משפט:

סיבוכיות האלגוריתם $\displaystyle O((m + n + w) \cdot \min\{ m, n, w \})$ .

הוכחה: אם משתמשים ברשימת שכנויות, אז בניית הגרף החדש היא $\displaystyle \Theta(m + n + w)$ .כבר ראינו בניתוח אלגוריתם Ford-Fulkerson, שסיבוכיותו לינארית במספר הקשתות כפול גודל הזרימה המירבית. מספר הקשתות כאן הוא $\displaystyle m + n + w$ , והזרימה המירבית היא $\displaystyle \min\{ m, n, w \}$

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

[עריכה] המבנה הרקורסיבי

נגדיר כ $\displaystyle m(i)$ את העלות הזולה ביותר לטיפול בקטע באורך $\displaystyle i$ .

משפט:

$\displaystyle m(i)$ נתונה על ידי נוסחת הנסיגה הבאה:

אם $\displaystyle i = 1$ ,‏ אז $\displaystyle f(1)$ .
אם $\displaystyle i > 1$ ,‏ אז $\displaystyle \min\left\{f(i), \min_{1 \le j < i} \left\{m(j) + k + m(i-j)\right\}\right\}$ .

הוכחה: נשים לב לנקודות הבאות:

אם $\displaystyle i = 1$ ,‏ אז אין מה לחתוך; ההובלה תעלה $\displaystyle f(1)$ .
אם $\displaystyle i > 1$ ,‏ אז או שלא חותכים את הקטע, או שכן. אם לא חותכים, עלות השבירה 0, ועלות ההובלה $\displaystyle f(i)$ . אם חותכים בנקודה $\displaystyle j$ , אז עלות הטיפול בחלק השמאלי תהיה , עפ"י ההגדרה, $\displaystyle m(j)$ ,‏ עלות השבירה היא כמובן $\displaystyle k$ ,‏ ועלות הטיפול בחלק הימני תהיה, עפ"י ההגדרה, $\displaystyle m(i - j)$ . נותר לקחת מינימום על פני $\displaystyle j$ , ולהחליט האם לחתוך או לא.

כדאי לדעת:

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

[עריכה] מימוש נאיבי

להלן פסוודו-קוד המממש את נוסחת הנסיגה.

Min-Cost(i)
1	if i == 1
2		return F(1)
 
3	guess-without = F(i)
 
4	guess-with = ∞
5	for j in [1, …, i - 1]
6		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
7			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
 
8	if guess-with < guess-without
9		return guess-with
10	else
11		return guess-without

[עריכה] שימוש בmemoization

נוסיף memoization.

Min-Cost(i)
1	if M[i] != Nil
2		return M[i]
 
1	if i == 1
2		M[1] = F(1)
3		return F(1)
 
4	guess-without = F(i)
 
5	guess-with = ∞
6	for j in [1, … i - 1]]
7		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
8			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
 
9	if guess-with M[i] < guess-without
10		M[i] = guess-with
11		return guess-with
12	else
13		M[i] = guess-without
14		return guess-without

(נניח שהמערך הגלובלי Mבאורך nמאותחל תחילה כולו לNil.)

[עריכה] הדפסת נקודות השבירה

נוסיף גם מספיק מידע לצורך הדפסת פרטי הפתרון.

Min-Cost(i)
1	if M[i] != Nil
2		return M[i]
 
1	if i == 1
2		M[1] = F(1)
3		Break[1] = Nil
4		return F(1)
 
5	guess-without = F(i)
 
6	guess-with = ∞
7	for j in [1, … i - 1]]
8		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
9			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
10			if guess-with 
11				Break[i] = j
 
12	if guess-with 
13		M[i] = guess-with
14		return guess-with
15	else
16		M[i] = guess-without	
17		return guess-without

המערך הגלובלי Break מכיל את ההחלטה שעשינו לגבי כל קטע. Break[i]הוא Nilאם החלטנו לא לחלק את הקטע, והוא $\displaystyle j$ אם החלטנו לשבור בנקודה j.

כעת נדפיס את העצירות, ע"י קריאה לPrint-Breaks(n, 0). הפונקציה מוגדרת להלן.

Print-Breaks(i, start)
1	if Break[i] == Nil
2		return
 
3	j = Break[i]
 
4	Print(j + start)
 
5	Print-Nums(j, start)
6	Print-Nums(i - j, start + j)

הפונקציה מקבלת שני ארגומנטים: אורך הקטע, i,‏ ותחילת הקטע, start.‏ נניח שהפונקציה נקראה עבור שני ערכים ספיציפיים כאלה. אם Break[i] == Nil, אז לא חתכנו את הקטע, ואין מה להדפיס. אם לא, וBreak[i] == j, אז יש להדפיס את הנקודה j(תוך זכירה שאנו נמצאים startמתחילת כל הגשר), את החלק השמאלי, ואת החלק הימני.

[עריכה] ניתוח סיבוכיות

נגדיר את זמן הריצה של Min-Time(i) בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$ כ $\displaystyle T'(i)$ . קל לראות ש $\displaystyle T'(i) = \Theta(i)$ . זמן הריצה חסום מלמעלה על ידי $\displaystyle \sum_{i = 1}^n[T'(i)] = \sum_{i = 1}^n[ \Theta(i) ] = \Theta(n^2)$ .

גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין $\displaystyle O(n^2)$ .

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

שימו לב:

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

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

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\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, v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל $\displaystyle u$ ב $\displaystyle A$ לצומת המתאים ל $\displaystyle v$ ב $\displaystyle A$ .
במקום כל קשת $\displaystyle (u, v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל $\displaystyle u$ ב $\displaystyle B$ לצומת המתאים ל $\displaystyle v$ ב $\displaystyle B$ .
במקום הקשת השלילית $\displaystyle (x, y)$ (בגרף המקורי), נמתח קשת מהצומת המתאים ל $\displaystyle x$ ב $\displaystyle A$ לצומת המתאים ל $\displaystyle y$ ב $\displaystyle B$ במחיר 0. התרשים הבא מראה זאת.

נניח שלקשת השלילית היה מחיר $\displaystyle -z$ . בנוסף נמתח עוד שני סוגי קשתות:

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

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

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

משפט:

מחיר המסלול הזול ביותר מ $\displaystyle s$ ל $\displaystyle u$ בגרף המקורי, קטן בדיוק ב $\displaystyle z$ ממחיר המסלול הזול ביותר מ $\displaystyle s$ ל $\displaystyle 2 \cdot |V| + u$ ב $\displaystyle C$ בגרף החדש.

הוכחה: בגרף המקורי, ייתכן שהמסלול הזול ביותר מ $\displaystyle s$ ל $\displaystyle u$ לא השתמש בקשת השלילילת, וייתכן שהשתשמש בו. במקרה הראשון, תהיה קפיצה מ $\displaystyle A$ ישירות ל $\displaystyle C$ , ובמקרה השני, תהיה קפיצה מ $\displaystyle A$ ל $\displaystyle B$ ומ $\displaystyle B$ ל $\displaystyle C$ . הקפיצה מ $\displaystyle A$ ישירות ל $\displaystyle C$ עולה $\displaystyle z$ יותר מאשר המסלול המקורי. הקפיצות מ $\displaystyle A$ ל $\displaystyle B$ ומ $\displaystyle B$ ל $\displaystyle C$ גם כן עולות $\displaystyle z$ יותר מאשר המסלול המקורי, שכן עלות כל אחת משתי הקשתות היא 0, והנוסע לא קיבל את התשלום $\displaystyle z$ מהחברה.

כעת כל הקשתות אינן שליליות, ומותר להריץ את Dijkstra.

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

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

הטענה נכונה. נניח שבערימה יש $\displaystyle s$ איברים. האיבר האחרון בערימה הוא באינדקס $\displaystyle s$ , ואביו (אם יש לו) בהכרח יושב ב $\displaystyle \left\lfloor \frac{s}{2} \right\rfloor$ . לכן, למרות שהלולאה אינה עוברת על כל האיברים, היא מדלגת רק על ערימות בעלי איבר יחיד, שהן, עפ"י תכונת הערימה, תקינות. הלולאה תתקן כל ערימה שדורשת תיקון, בדיוק מהסיבה שראינו בהרצאה. הסיבוכיות היא $\displaystyle \Theta(n)$ . אפשר לראות שהלולאה עוברת על חצי מהאיברים, ולכן היא $\displaystyle \Omega(n)$ . מצד שני, היא עושה פחות מBuild-Heap, וזו היתה $\displaystyle O(n)$ , ולכן גם לולאה זו $\displaystyle O(n)$ .
הטענה נכונה. אם ילדו השמאלי של איבר במקום $\displaystyle i$ נמצא באינדקס $\displaystyle 2 \cdot i$ , וילדו הימני נמצא באינדקס $\displaystyle 2 \cdot i + 1$ , אז כל מסלול מהשורש לעלה עובר על סדרת אינדקסים מונוטונית עולה. לכן, אם המערך ממויין, כל מסלול מהשורש לעלה יעבור על סדרת ערכים מונוטונית לא-יורדת. הסיבוכיות הנה מיון מיזוג, כלומר $\displaystyle \Theta\left(n \cdot \log(n)\right)$ .
הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [3, 4, 2, 1]$ . הסיבוכיות הנה $\displaystyle \Theta(n)$ , בדיוק מהניתוח שכבר ראינו לגבי הפתרון מההרצאה.
הטענה נכונה. היות ש Bubble-Up(bh, i) אינו יכול להשפיע על איברים באינדקס מעל $\displaystyle i$ , הקוד שקול לסדרת פעולות Insert. מאותה סיבה, הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta\left( n \cdot \log(n)\right)$ .
הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [4, 1, 2, 3]$ . הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta\left( n \cdot \log(n)\right)$ .