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

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


1 עריכה

שיטה א' עריכה

נשתמש באותו הרעיון בו השתמשתנו כדי לנתח טור של לוגריתמים.


ראשית נראה כי  .


הוכחה:  
.

 

כעת נראה כי  .


הוכחה:  .
נשים לב שכאשר   בתחום   ו  בתחום  , אז  .

לכן נקבל

 .

 

שיטה ב' עריכה

 .

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

נציב זאת חזרה בסכום הכפול:   .


נבצע החלפת משתנים  , ונקבל:

  .

2 עריכה

א' עריכה

1 עריכה

 , עפ"י מקרה 1 של משפט המאסטר.

2 עריכה

נפרוש את הנוסחה:  
 
 
 
 
 
 
(את המעבר האחרון ראינו בטורים שימושיים.)

3 עריכה

נגדיר  . בלי הגבלת הכלליות, נניח ש . להלן עץ הפרישה המתקבל:

 
עץ הפרישה.

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

קל לראות שכל רמה מלאה בעץ תורמת  .‏ הרמה הראשונה תורמת  ;‏ הרמה השניה תורמת  ,‏ הרמה השלישית תורמת  ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש  חסומה מלמטה ע"י  , וחסומה מלמעלה ע"י  . אבל היות ש  וכן  , אז  .

ב' עריכה

נשתמש בפרישה.בעץ המתאים לנוסחה:

  1. צומת הראש מציין את  , והרמה הראשונה תורמת  .
  2. ברמה הבאה, הצומת מציין את  , והרמה תורמת  .
  3. ברמה הבאה אחריה, הצומת מציין את  , והרמה תורמת  .

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

כדי למצוא את גובה העץ,  , נפתור  :  
 
 
 
 
כאמור, הרמה ה  תורמת  . נותר, לכן, לסכם את  :  
 
 
 

3 עריכה

הוכחה: נוכיח באינדוקציה שקיים   כך ש .

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

 
 
 
 
אם ניקח  ,‏ אז הביטוי האחרון גדול מ .


(בסיס האינדוקציה) היות ש ,‏ אז  ,‏ עבור   כלשהו. נפתור  ,‏ ונקבל  .‏

האינדוקציה, לכן, נכונה עבור  , החל מ .

 

4 עריכה

פעולת הפונקציה עריכה

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

כעת נראה מה הפונקציה עושה.

  • בשורה 3, הביטוי   הוא בדיוק ערך הביט  .
  • שוב בשורה 3, Foo( ⌊n / 2⌋ ) היא הקריאה לאותה פונקציה, אך עם הערך  .

מכאן ברור שהפונקציה פשוט סוכמת את הביטים של  . אפשר להראות זאת פורמלית באינדוקציה.


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

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


5 עריכה

1 עריכה

במערך[2, 3, 8, 6, 1] ישנם חמשת ההיפוכים הבאים:

  1.  
  2.  
  3.  
  4.  
  5.  

2 עריכה

 

כדאי לדעת:

הפתרון משתמש ברעיון "divide and conquer", כלומר פתרון בעיות "גדולות" ע"י פתירת בעיות "קטנות" יותר.

הפתרון מתבסס על שינויים קלים במיון מיזוג. ראשית, נתבונן בפסוודו-קוד הבא, שהוא ווריאציה קלה על Merge:

	# A global variable that counts the number of inversions.
1	inv


# Merge and count inversions. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R, and counts how many members
#	of L and R are inverted relative to each other.
Merge-Count-Inversions(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )

2	l = r = m = 1

3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6			inv = inv + r - 1
7		else if l > Length(L)
8			Merged[m++] = R[r++]
9		else if L[l] inv = inv + r - 1
10			Merged[m++] = L[l++]
11			inv = inv + r - 1
12		else
13			Merged[m++] = R[r++]

14	return Merged

המשתנה הגלובלי inv (ב1) שומר על מספר ההפכים. הפונקציה Merge-Count-Inversions כמעט זהה לפונקציה Merge שאותה כבר פגשנו, למעט השורות 6 ו11 שנוספו - שורות אלה מעדכנות את inv בכל פעם שנלקח איבר מL.



משפט:

אם Merge-Count-Inversions נקראת עם L וR ממוינים כלשהם, אז בסיום הקריאה:

  1. הפונקציה מחזירה מערך ממוין של איחוד איבריהם.
  2. למשתנה inv נוספו בדיוק מספר ההפכים בין איברי L לאיברי R (כלומר, מספר האיברים בL שגדולים מאיברים בR).



הוכחה: את החלק הראשון של המשפט הוכחנו כבר לגבי Merge, ולכן יש להוכיח רק את חלקו השני.

נניח שאחת משורות 4 או 9 בוחרת למזג את L[l]. בשלב זה, מספר האיברים שכבר נלקחו מR הוא r - 1, וכל אחד מאיברים אלה קטן בהכרח מL[l], או, במילים אחרות, מרכיב הפך בייחס לL[l]. מצד שני, כל איבר בR שעדיין לא נבחר, בהכרח גדול מL[l], ולכן אינו מרכיב הפך בייחס לL[l]. לכן כשנבחר L[l], הפונקציה מוסיפה לinv בדיוק את מספר ההפכים שהוא חלק מהם. היות שהפונקציה בוחרת בשלב כלשהו כל איבר מL, היא מוסיפה לinv את סך כל ההפכים בין L לR, בדיוק כפי שנטען.

 

כדי להשלים את הפתרון, פשוט נכתוב שוב פעם את Merge-Sort , אלא שבמקום לקרוא לMerge נקרא לMerge-Count-Inversions:

# Merge sort also counting inversions. 
# Takes an array (Values).
# Returns an array of the same elements, sorted in increasing order; also increases global variable inv 
# 	by the number of inversions.
Merge-Sort-Count-Inversions(Values)
1	if Length(Values) <= 1
2		return Values

3	mid = (1 + Length(Values)) / 2
		
4	L = Merge-ּSort-Count-Inversions( Values[1, ... , mid] )
5	R = Merge-Sort-Count-Inversions( Values[mid + 1, ... , Length(Values)] )
	
6	return Merge-Count-Inversions(L, R)

לפני הקריאה הראשונה לMerge-Sort-Count-Inversions נאפס את המשתנה הגלובאלי inv. בסיום המיון, המשתנה inv יכיל את מספר ההחלפות, כפי שמראה המשפט הבא.



משפט:

בסיום המיון, המשתנה inv יכיל את מספר ההחלפות.



הוכחה: ההוכחה היא באינדוקציה על אורך המערך. נוכיח שבקריאה לMerge-ּSort-Count-Inversions במערך שארכו  , מספר ההפכים במערך מיתוסף לinv.

(בסיס האינדוקציה) אם אורך המערך הוא 0 או 1, אז שורה 2 של IMerge-ּSort-Count-Inversions תצא ישר. inv לא ישתנה מערכו ההתחלתי של 0, בדיוק כפי שאמור להיות (אין הפכים במערך ריק או במערך בעל איבר יחיד).

(מעבר האינדוקציה) נניח שאורך המערך גדול (ממש) מ1. יש שלושה סוגי הפכים אפשריים במערך:

  1. הפכים בין איברים בחציו השמאלי לבין עצמם
  2. הפכים בין איברים בחציו הימני לבין עצמם
  3. הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני

כל אלו בהכרח מחושבים נכון:

  1. הפכים בין איברים בחציו השמאלי לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 4 של Inversions-Imp.
  2. הפכים בין איברים בחציו הימני לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 5 של Inversions-Imp.
  3. הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני מחושבים נכון בפונקציה Merge-Count-Inversions, כפי שהוכחנו קודם. אמנם הפונקציה אינה נקראת על חלקי המערך המקוריים, אלא על פרמוטציות שלהם (שהרי 4 ו5 ממיינות אותם), אך לפרמוטציות בהכרח אותו מספר ההפכים אחד בייחס לשני.


 

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


6 עריכה

נסמן את זמן הריצה של Alg(A, i, j) כ .

נצייר את עץ הפרישה של הפונקציה:

 
עץ הפרישה. ט"ו בשבט שמח.

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

נפתור  , ונקבל

 .


הסיבוכיות, לכן, היא  .


7 עריכה

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

  1. הספרה החסרה בעמודה זו היא 1.
  2. עלינו להתמקד רק בשורות בהן הספרה בעמודה זו היא 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 מדפיסות את הביט החסר בעמודה הנכחית, ומחליטות באיזו משתי המחסניות להתמקד.

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

8 עריכה

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

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

 
 
עבור קבוע   כלשהו.

נגזור את הביטוי שבתוך ה , ונקבל  

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

כאשר , אז

 
 
 

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

9 עריכה

נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם  . ברמה השניה יש   צמתים, וכל אחד מהם תורם  . ברמה ה  (בהנחה שהרמה הראשונה היא ב ), יש   צמתים, וכל אחד מהם תורם  . אנו יודעים שגובה העץ הוא  . נפשט:  
 
 
 
 
 
 
נשים לב שעפ"י חסמי האינטגרלים לטורים,‏  .