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

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

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

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

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

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

תוכן עניינים

1 שאלה 1
- 1.1 פתרון מלמטה למעלה
- 1.2 פתרון מלמעלה למטה
2 שאלה 2
3 שאלה 3
4 שאלה 4
5 שאלה 5

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

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

נפתור את הבעיה בשני אופנים: מלמטה למעלה, ומלמעלה למטה.

[עריכה] פתרון מלמטה למעלה

Subset-Sum(A, t)
1	Sum = Make-Array(t)
 
2	for j in [t … 1]
3		Sum[j] = False
 
4	n = Length(A)
 
5	for i in [1, … n]
6		for j in [t … 1]
7			if t == A[j]
8				Sum[j] = True
9			if t > A[i] and Sum[t - A[i]] == True
10				Sum[j] = True
 
11	return Sum[t] == True

1-3 מייצרות מערך Sum באורך $\displaystyle t$ , ומאתחלות את כל איבריו לFalse. הלולאה 5-10 עוברת על כל איברי A. לכל איבר כזה, 6-10 מעדכנת לTrue כל תא בSum שברור שניתן להגיע אליו מסכום האיברים שנבדקו עד כה. כל שנותר ב11 הוא להחזיר האם ניתן להגיע לסכום t.

שימו לב:

חשוב שהלולאה ב6 תהיה בסדר יורד. אותה הלולאה בסדר עולה תניב פתרונות שגויים.

קל לראות שהסיבוכיות היא $\displaystyle \Theta(n \cdot t)$ .

[עריכה] פתרון מלמעלה למטה

Subset-Sum(A, i, t')
1	if t == 0
2		return True
 
3	if i == 0
4		return False
 
5	if SS[i, t'] != Nil
6		return SS[i, t']
 
7	if Subset-Sum(A, i - 1, t') == True
8		SS[i, t'] = True
9		return True
 
10	if  t' ≥ A[i] and Subset-Sum(A, i - 1, t' - A[i]) == True
11		SS[i, t'] = True
12		return True
 
13	SS[i, t'] = False
14	return False

(נניח שSS היא מטריצה בעלת $\displaystyle n$ שורות ו $\displaystyle t$ עמודות, המאותחלת כולה לNil. בנייתה תארך $\displaystyle \Theta\left(n \cdot t\right)$ .)

סיבוכיות הפתרון שוב פעם $\displaystyle \Theta\left(n \cdot t\right)$ : אתחול המטריצה עולה $\displaystyle \Theta\left(n \cdot t\right)$ . כמו כן, נגדיר כ $\displaystyle T'(i, t')$ את זמן הריצה של Subset-Sum(i, t') בהנחה שכל קריאה רקורסיבית אורכת $\displaystyle O(1)$ . קל לראות ש $\displaystyle T'(i, t') = O(1)$ .‏ הסיבוכיות הכוללת של הקריאות היא $\displaystyle \sum_{i = 1}^n \sum_{t'= 1}^t \left[ T'(i, t') \right] = \sum_{i = 1}^n \sum_{t'= 1}^t \left[O(1)\right] = \Theta\left(n \cdot t\right)$ .

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

[עריכה] תשובה שגויה ע"י שימוש באלגוריתם Kruskal

כדאי לדעת:

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

להלן הוכחה שגויה לקיום עפ"מ יחידי:

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

תשובה זו אינה נכונה, מפני שהיא מתייחסת לאלגוריתם Kruskal בלבד. אפשר עדיין לטעון, לדוגמה, שאלגוריתם Prim יחזיר עפ"מ שונה במקרה זה (בהמשך נראה שזה בלתי אפשרי, אלא שאי אפשר להסיק זאת מהטענה שהוצגה עד עתה).

[עריכה] תשובה שגויה ע"י שימוש לא נכון באינדוקציה

להלן הוכחה שגויה באינדוקציה:

הוכחה: האינדוקציה היא על מספר הצמתים, $\displaystyle \vert V \vert$ .

(בסיס האינדוקציה) כאשר $\displaystyle \vert V \vert = 1$ אז יש צומת יחיד והעפ"מ בוודאי יחידי.

(מעבר האינדוקציה), ניקח צומת כלשהו $\displaystyle u$ , ונמצא את העפ"מ $\displaystyle T_1$ של הצמתים $\displaystyle V \setminus u$ . קבוצה זו קטנה ב1 מ $\displaystyle \vert V \vert$ , ולכן יש לה עפ"מ יחידי. נותר לחבר את $\displaystyle u$ ל $\displaystyle T_1$ , וברור שנעשה זאת דרך הקשת הזולה ביותר בין $\displaystyle u$ לבין צומת ב $\displaystyle T_1$ .

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

כדאי לדעת:

חדי העין יזהו שאין הבדל ממשי בין הטעות כאן לבין הטעות הקודמת. האינדוקציה כאן היא למעשה הפעלת אלגוריתם Prim תחת הנחות שגויות שמקבלת תוצאה כללית לגבי כל העפ"מים האפשריים.

[עריכה] תשובה ע"י שיקול הקשת הזולה ביותר בגרף

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

משפט:

נניח ש $\displaystyle G = (V, E)$ הוא גרף, $\displaystyle u, v \in V$ הם שני צמתים, ו $\displaystyle e = (u, v) \in E$ היא קשת.

נגדיר כעת את הגרף $\displaystyle G' = (V', E')$ כגרף המתקבל מ"כיווץ" $\displaystyle u$ ו $\displaystyle v$ לצומת יחיד, $\displaystyle uv$ .

נגדיר כ $\displaystyle T'$ את קשתות העפ"מ ב $\displaystyle G'$ . אז קשתות עפ"מ זה יחד עם $\displaystyle (u, v)$ ,‏ כלומר $\displaystyle 'T \bigcup {(u, v)}$ ,‏ הם בהכרח קשתות העץ הזול ביותר הפורס את $\displaystyle G$ מבין העצים הפורשים שמשתמשים ב $\displaystyle e=(u, v)$ .

הוכחה: ראשית ברור שהתוצאה היא עץ. נניח ש $\displaystyle x$ ו $\displaystyle y$ הם שני צמתים. קל לראות שאם יש מסלול מ $\displaystyle x$ ל $\displaystyle y$ ב $\displaystyle G'$ המשתמש בקשתות $\displaystyle T'$ בלבד , אז יש מסלול מ $\displaystyle x$ ל $\displaystyle y$ ב $\displaystyle G'$ המשתמש בקשתות $\displaystyle T' \bigcup {(u, v)}$ בלבד. קל לראות שאם $\displaystyle T' \bigcup {(u, v)}$ מכיל מעגל, אז גם $\displaystyle T'$ מכיל מעגל.

כעת ברור גם שמדובר בעץ הזול ביותר. נניח שיש עץ פורש זול יותר $\displaystyle T'' \bigcup {(u, v)}$ . אז גם $\displaystyle T''$ עץ פורש זול יותר ב $\displaystyle G'$ , דבר שסותר את הנחתנו ש $\displaystyle T'$ היא קבוצת קשתות עפ"מ.

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

הוכחה: האינדוקציה היא על מספר הצמתים, $\displaystyle |V|$ .

(בסיס האינדוקציה) כאשר $\displaystyle |V|=1$ אז יש צומת יחיד והעפ"מ בוודאי יחידי.

(מעבר האינדוקציה) ניקח את הקשת הקלה ביותר בגרף $\displaystyle e = (u,v)$ . כבר הוכחנו שקשת זו היא חלק מכל עפ"מ. כעת "נכווץ" את הגרף ע"י הפיכת שני הצמתים, $\displaystyle u$ ו $\displaystyle v$ , לצומת יחיד. מהנחת האינדוקציה נובע שקיים כעת עפ"מ יחיד (שהרי מספר הצמתים ירד ב1). המשפט הקודם אומר שקשתות כל עפ"מ שהתקבל בגרף המכווץ, יחד עם $\displaystyle e$ , הן בדיוק קשתות העפ"מ בגרף המקורי. נובע לכן שיש עפ"מ יחיד.

[עריכה] תשובה ע"י שיקול הקשת היקרה ביותר במעגל

נניח בשלילה שיש שני עפ"מים שונים: $\displaystyle T_1$ ו $\displaystyle T_2$ . היות שהעפ"מים שונים אך מספר קשתותיהם שווה, קיימת בהכרח קשת $\displaystyle e$ השייכת ל $\displaystyle T_2$ אך לא ל $\displaystyle T_1$ . הוספת קשת זו ל $\displaystyle T_1$ בהכרח תיצור מעגל. נגדיר כ $\displaystyle e'$ את הקשת הכבדה ביותר על פני המעגל, וניזכר שקשת זו איננה חלק מאף עפ"מ. כעת אם $\displaystyle e' = e$ , אז $\displaystyle T_2$ אינה עפ"מ; מצד שני, אם $\displaystyle e' \ne e$ , אז $\displaystyle T_1$ אינה עפ"מ. בכל מקרה, לא ייתכן מעגל כזה, ולכן בהכרח אין שני עפ"מים שונים.

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

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

הספרה החסרה בעמודה זו היא 1.
עלינו להתמקד רק בשורות בהן הספרה בעמודה זו היא 1 (קומבינטורית, לא ייתכן אחרת).כעת נתחיל את הבעיה מחדש, תוך התמקדות בחצי (בערך) מהשורות (רק אלה בהן הספרה בעמודה זו היא 1): נסתכל בעמודה הלפני אחרונה,נספור את מספר ה0-ים ומספר ה1-ות שאנו רואים , וכולי.

להלן פסוודו-קוד יעיל המממש זאת:

Print-Missing-Number(M)
1	n = Num-Cols(M)
 
2	Rows = Make-Stack()
 
3	for j in [1, … 2^n - 1]
4		Insert-Front(Rows, j)
 
5	for i in [1, … n]
6		Zeros = Make-Stack()
7		Ones = Make-Stack()
 
8		while Size(Rows) &gt; 0
9			row = Pop(Rows)
 
10			if M[row][i] == 0
11				Push(Zeros, row)
12			else
13				Push(Ones, row)
 
14		if Size(Zeros) &gt; Size(Ones)
15			Print(1)
16			Rows = Ones
17		else
18			Print(0)
19			Rows = Zeros

1-4 מאתחלות את ה[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] Rows כך שתכיל את כל (מספרי השורות). 5-19 עובורת על כל העמודות. בכל איטרציה, 8-13 מחלקות את מספרי השורות בRows לשתי מחסניות, לפי ערך ביט העמודה הנכחית. 14-19 מדפיסות את הביט החסר בעמודה הנכחית, ומחליטות באיזו משתי המחסניות להתמקד.

נותר לנתח הסיבוכיות. נשים לב שהאיטרציה הראשונה פועלת בזמן $\displaystyle \Theta(m)$ , האיטרציה השניה בזמן $\displaystyle \Theta(m / 2)$ , ובאופן כללי, האיטרציה ה $\displaystyle i$ בזמן $\displaystyle \Theta(m / 2^i)$ . זמן הריצה, לכן, הוא $\displaystyle \sum_{i = 1}^n \left[ \Theta(m / 2^i)\right] = \Theta(m).$

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

סעיף זה הוא טריביאלי. נשתמש ברשימה מקושרת דו-כוונית (ייתכנו מימושים אחרים, כמובן). Insert תקרא לInsert-Front של רשימה מקושרת, ותעבוד בזמן $\displaystyle O(1)$ . את Min וDelete-Min נממש בעזרת לולאות על חוליות הרשימה. סיבוכיות כל אחת מפעולות אלה תהיה לינארית במספר החוליות במקרה הגרוע.
נזכר שבהנתן תור קדימויות, ניתן לממש בעזרת סידרת $\displaystyle n$ פעולות Insert ולאחריה סידרת $\displaystyle n$ פעולות Delete-Min (באופן כמעט זהה לHeapsort). לו כל פעולה היתה עובדת בזמן $\displaystyle O(1)$ , אז ניתן היה למיין בזמן לינארי, בניגוד לחסם התחתון על מיון מבוסס-השוואות שלמדנו.

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

נוכיח את הטענה באינדוקציה על $\displaystyle n$ , מספר הצמתים.

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

(מעבר האינדוקציה) נניח שהטענה נכונה עבור כל גרף בעל $\displaystyle n - 1$ צמתים, ונראה שהטענה נכונה עבור כל גרף בעל $\displaystyle n$ צמתים. ניקח גרף בעל $\displaystyle n$ צמתים, ונחפש צומת $\displaystyle u$ שמספר שכניו אי-זוגי. (אם אין צומת כזה, הטענה בהכרח נכונה לגרף זה.) נניח ששכניו של $\displaystyle u$ הם $\displaystyle u_1, \ldots, u_i$ . נשים לב ש $\displaystyle i$ בהכרח אי-זוגי. אם נמחק את $\displaystyle u$ והקשתות שיוצאות ממנו, הטענה נכונה מהנחת האינדוקציה. לאחר הוספת $\displaystyle u$ מחדש, כמה צמתים בעלי דרגה אי-זוגית נוצרו? $\displaystyle u$ עצמו תורם 1. כל שכן של $\displaystyle u$ בעל דרגה זוגית הופך להיות בעל דרגה אי-זוגית, וכל שכן של $\displaystyle u$ בעל דרגה אי-זוגית הופך להיות בעל דרגה זוגית. היות ש $\displaystyle i$ אי-זוגי, תרומת שכניו היא מספר אי-זוגי (חיובי או שלילי). לכן נוצר עוד מספר זוגי (חיובי או שלילי) של צמתים בעלי דרגה זוגית.

דוגמה:

בתרשים הבא, יש ל $\displaystyle u$ ‏ 3 שכנים: 2 בעלי דרגה אי-זוגית (בלעדיו), ו1 בעל דרגה זוגית (בלעדיו).

לאחר הוספת $\displaystyle u$ , יש ל $\displaystyle u$ ‏ 2 שכנים בעלי דרגה אי-זוגית (יחד אתו), ושכן יחיד בעל דרגה זוגית (יחד אתו). הוספת $\displaystyle u$ ייצרה עוד 0 צמתים בעלי דרגה אי-זוגית: $\displaystyle u$ עצמו בעל דרגה אי-זוגית, $\displaystyle u_1$ הפך להיות בעל דרגה זוגית, $\displaystyle u_2$ הפך להיות בעל דרגה אי-זוגית ו $\displaystyle u_3$ הפך להיות בעל דרגה זוגית.

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

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

תוכן עניינים

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

[עריכה] פתרון מלמטה למעלה

[עריכה] פתרון מלמעלה למטה

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

[עריכה] תשובה שגויה ע"י שימוש באלגוריתם Kruskal

[עריכה] תשובה שגויה ע"י שימוש לא נכון באינדוקציה

[עריכה] תשובה ע"י שיקול הקשת הזולה ביותר בגרף

[עריכה] תשובה ע"י שיקול הקשת היקרה ביותר במעגל

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

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

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

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא