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

1

שני הפתרונות מתחילים בצורה זהה. מייצרים מערך של $\displaystyle n$ קבוצות זרות (1-3). מכאן ואילך הפתרונות מתחלקים לפי הסעיף:

סדרת פעולות עבור המימוש הנאיבי

עוברים בלולאה (4-5) על איברי המערך (משמאל לימין), ומצרפים כל קבוצה לקבוצה שלפניה:

1	Sets = Make-Array(n)

2	for i in [1, ..., n]
3		Sets[i] = Make-Set()

4	for i in [1, ..., n - 1]
5		Union(Sets[i + 1], Sets[i])

הסיבוכיות של 4-5 הנה:

$\displaystyle \sum _{i=1}^{n-1}[\Theta (i)]=\Theta (\sum _{i=1}^{n-1}[i])=\Theta (n^{2})$

סדרת פעולות עבור איחוד רשימות על פי גודל

עובדים בשלבים, כשכל שלב מכיל לולאה. בשלב הראשון מאחדים את קבוצה 1 עם קבוצה 2, את קבוצה 3 עם קבוצה 4, וכולי. בשלב השני מאחדים את קבוצה 1 עם קבוצה 3, את קבוצה 5 עם קבוצה 7, וכולי. ממשיכים בשלבים עוד ועוד, עד שכל הקבוצות מאוחדות לקבוצה אחת גדולה:

1	Sets = Make-Array(n)

2	for i in [1, ..., n]
3		Sets[i] = Make-Set()

4	d = 0

5	while n / 2^d > 1
6		j = 1

7		while j < n
8			Union(Sets[j], Sets[j + 2^d])
			
9			j = j + 2 &middot; 2^d
		
10		d = d + 1

הסיבוכיות של 5-10 הנה:

$\displaystyle \sum _{d=1}^{\log(n)}[n/2^{d}\Theta (2^{d})]=n\cdot \sum _{d=1}^{\log(n)}[\Theta (1)]=\Theta (n\cdot \log(n))$

2

נוכיח באינדוקציה שקיים $\displaystyle c>0$ כך ש(עבור $\displaystyle n$-ים מספיק גדולים) $\displaystyle T(n)\leq c\cdot n\cdot \log(n)$.

(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,

$\displaystyle T(n)=\max _{i=1,\ldots ,n/2}[T(i)+T(n-i)+\Theta (i)]\leq$
$\displaystyle \max _{i=1,\ldots ,n/2}[c\cdot i\cdot \log(i)+c\cdot (n-i)\cdot \log(n-i)+c'\cdot i]$
עבור קבוע $\displaystyle c'>0$ כלשהו.

נגזור את הביטוי שבתוך ה$\displaystyle \max$, ונקבל $\displaystyle c\cdot \log(i)-c\cdot \log(n-i)+c'$

נגזור את הביטוי פעם שניה, ונקבל ביטוי חיובי. מכאן ברור שמקסימום הביטוי הוא כאשר$\displaystyle i=n/2$.

כאשר$\displaystyle i=n/2$, אז

$\displaystyle T(n)\leq 2\cdot c\cdot n/2\cdot \log(n/2)+c'=$
$\displaystyle c\cdot n\cdot \log(n)-c\cdot n+c'\leq$
$\displaystyle c\cdot n\cdot \log(n)$

(בסיס האינדוקציה) נפתור: $\displaystyle (c\cdot i\cdot \log(i))|^{i=2,3}=O(1)$
ונווכח שהדבר נכון עבור $\displaystyle c$ גדול מספיק.

3

נוסיף עוד רשימה מקושרת, has-neighbors, המתארת את הצמתים שלהם יש שכנים.

דוגמה: בתרשים הבא, הרשימה המקושרת has-neighbors מכילה חוליות בעלות התוכן 1, 2, 3, ו4, מפני שאלה הצמתים שלהם שכנים. שתי הרשימות המקושרות.

קל לראות שסיבוכיות A(G, u) וV(G) אינן מושפעות מהוספת הרשימה המקושרת (הן אינן משתמשות בו). להלן הפסוודו-קוד החדש של E(G):

Count-Num-Edges(G)
1	count = 0
		
2	lnk = G.has-neighbors.front
	
3	while lnk != Nil
4		u = lnk.value
			
5		count = count + Size( G.Vertexes[u] )
	
6		lnk = lnk.next
	
7	return count
	
	
# Returns an array of the edges of a graph (G).
E(G)
1	Edges = Make-Array( Count-Num-Edges(G) )
			
2	i = 0
	
3	lnk = G.has-neighbors.front
		
4	while lnk != Nil
5		u = lnk.value
			
6		for v in A(G, u)		
7			Edges[i++] = (u, v)
	
8		lnk = lnk.next
				
9	return Edges

פונציית-העזר Count-Num-Edges סופרת את מספר הצמתים. שורה 1 מאתחלת משתנה הסופר את מספר הצמתים ל0, ושורה 7 מחזירה אותו. הלולאה 3-6 (יחד עם 2) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 4 מוצאת את מספר הצומת, ו$\displaystyle 5$ מוצאת את מספר שכניו. הפונקציה E מייצרת את המערך Edges ב1, ומחזירה אותו ב9. הלולאה 4-8 (יחד עם 3) עוברת על כל חוליות has-neighbors. עבור כל חוליה, 5 מוצאת את מספר הצומת, ו$\displaystyle 6-7$ רצות על שכניו. לכל שכן, קשת מתאימה מיתוספת לEdges.

4

מציאת דרגת היציאה

נזכר שבמערך Vertexes, כל איבר הוא רשימה מקושרת. נמצא את הרשימה המקושרת, ונחזיר את גודלה.

Out-Degrees(G, v)
1	lst = Vertexes[v]

2 	return Size(lst)

קל לראות שהסיבוכיות היא $\displaystyle O(1)$.

מציאת דרגת הכניסה

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

In-Degrees(G, v)
1	count = 0

2	for u in Vertexes
3		lst = Vertexes[u]
4		lnk = lst.front
5		while lnk != Nil
6			if lnk.value == (u, v)
7				++count

8	return count

הסיבוכיות היא $\displaystyle \Theta (|V|+|E|)$. הלולאה החיצונית 2-7 עוברת על כל איבר המתאים לצומת. הלולאה הפנימית 2-7 עוברת בסופו של דבר על כל קשת.

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}$ הפך להיות בעל דרגה זוגית.

6

ניצור שתי קבוצות. הקבוצה השמאלית, $\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$.

7

עלינו להראות שיש שני קבועים, $\displaystyle c_{0}$ ו$\displaystyle c_{1}$ המקיימים $\displaystyle c_{1}\cdot n\leq T(n)\leq c_{0}\cdot n$ עבור ערכי $\displaystyle n$ גדולים מספיק.

הטענה שקיים $\displaystyle c_{1}$ $\displaystyle T(n)\geq c_{1}\cdot n$ (כלומר $\displaystyle T(n)=\Omega (n)$) ברורה, מפני שאנו יודעים שהפונקציה עוברת על כל אחד מהצמתים, ויש $\displaystyle n$ צמתים עפ"י ההגדרה. נוכיח לכן רק את הטענה לגבי קיומו של $\displaystyle c_{0}$.

הוכחה: (בסיס האינדוקציה) נבחר את בסיס האינדוקציה כ$\displaystyle n=1$.

ונסמן ב$\displaystyle k$ את זמן הריצה של הפונקציה על קלט בגודל 1. מכאן נקבל את האילוץ על $\displaystyle c_{0}$: $\displaystyle k\leq c_{0}\cdot 1=c_{0}$. בוודאי שקיים $\displaystyle c_{0}$ המקיים אילוץ זה.

(מעבר האינדוקציה) נניח שהטענה מתקיימת לכל $\displaystyle n'<n$.

נזכר שראינו כבר את נוסחת הנסיגה המתאימה לבעיה $\displaystyle T(n)=T(n')+O(1)+T(n-n'-1)$ (קל לראות זאת גם מהתרשים הבא).

מעבר האינדוקציה.

הנוסחה אומרת שקיים $\displaystyle k'$ כך שמתקיים $\displaystyle T(n)\leq T(n')+k'+T(n-n'-1)$.

נשתמש בנוסחת הנסיגה ובהנחת האינדוקציה, ונקבל

$\displaystyle T(n)\leq T(n')+k'+T(n-n'-1)\leq$
$\displaystyle c_{0}\cdot n'+k'+c_{0}(n-n'-1)=$
$\displaystyle c_{0}\cdot n+(k'-c_{0})$

אם נבחר $\displaystyle k'\leq c_{0}$ אז $\displaystyle (k'-c_{0})$ שלילי, ולכן בהכרח $\displaystyle T(n)\leq c_{0}\cdot n$.

נשים לב שבסיס האינדוקציה הגביל אותנו לבחור $\displaystyle k\leq c_{0}$, ומעבר האינדוקציה הגביל אותנו לבחור $\displaystyle k'\leq c_{0}$.

מכאן יוצא שאכן יש $\displaystyle c_{0}$ המתאים לבעיה (למעשה יש אינסוף כאלה) - עלינו פשוט לבחור $\displaystyle c_{0}$ המקיים

$\displaystyle c_{0}\geq \max \left\{k,k'\right\}$.