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

1

1

נוכיח את הסופיות והנכונות באינדוקציה על $\displaystyle b-e+1$ (אורך הקטע), אותו נגדיר כ$\displaystyle n$.

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

(מעבר האינדוקציה) נניח סופיות ונכונות עד $\displaystyle n-1$ (לא כולל). נניח שמכניסים מערך בעל גודל $\displaystyle n$. שורה 5 קוראת לPartition, אשר מחלקת את המערך לשני חלקים: Values[b, ..., p] וValues[p + 1, ..., e], כך ש$\displaystyle b\leq p<e$, וכל איבר בחלק הראשון קטן או שווה לכל איבר בחלק השני (בשאלה נאמר שמותר להניח זאת, אך אפשר גם לוודא זאת מהתבוננות בPartition). שימו לב שהיות ש$\displaystyle b\leq p<e$, אז אורך כל אחד משני החלקים קטן ממש מ$\displaystyle n$. עפ"י הנחת האינדוקציה, 6-7 ימיינו כל אחד משני החלקים (ואף בזמן סופי). אם שני החלקים ממויינים, וכל איבר בחלק השמאלי קטן או שווה לכל אחד מאיברי החלק הימני, אז בהכרח כל המערך ממויין.

2

נתחיל במספר נקודות המשותפות לסעיף זה ולסעיף הבא. נגדיר את זמן הריצה על קלט בגודל $\displaystyle n$ כ$\displaystyle T(n)$. הקריאה לפונקציה וביצוע השורות 1-4 עולות $\displaystyle O(1)$, וPartition ב5 עולה $\displaystyle \Theta (n)$.

בסעיף זה, 6 פועלת על מערך בעל אורך $\displaystyle 1$, ו7 פועלת על מערך בעל אורך $\displaystyle n-1$. שורות אלה, על כן, פועלות בזמן $\displaystyle T(1)+T(n-1)$. נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=\Theta (n)+T(1)+T(n-1)$.

נפתור נוסחה זו בעזרת פרישה:

$\displaystyle T(n)=$
$\displaystyle \Theta (n)+T(1)+T(n-1)=$
$\displaystyle \Theta (n)+T(1)+\Theta (n-1)+T(1)+T(n-2)=$
$\displaystyle \Theta (n)+T(1)+\Theta (n-1)+T(1)+\Theta (n-2)+T(1)+T(n-3)=$

$\displaystyle \cdots$

$\displaystyle \Theta (n)+T(1)+\Theta (n-1)+T(1)+\Theta (n-2)+T(1)+\Theta (n-3)+T(1)+...T(1)+T(1)=$
$\displaystyle \sum _{i=1}^{n}[\Theta (i)+T(1)]=$
$\displaystyle \sum _{i=1}^{n}[\Theta (i)]+\sum _{i=1}^{n}[]T(1)]=$
$\displaystyle \Theta (n^{2})+n\cdot \Theta (1)=$
$\displaystyle \Theta (n^{2}).$

3

נשתמש בנקודות שצויינו בסעיף הקודם כמשותפות לשני הסעיפים.

בסעיף זה, 6 פועלת על מערך בעל אורך $\displaystyle n/2$ (בהזנחת שגיאות עיגול), ו7 פועלת ג"כ על מערך בעל אורך $\displaystyle n/2$ (שוב, בהזנחת שגיאות עיגול). שורות אלה, על כן, פועלות בזמן $\displaystyle 2\cdot T(n/2)$.

נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=\Theta (n)+2\cdot T(n/2)$. יש דרכים רבות לפתור נוסחת נסיגה זו - הפשוטה ביותר היא לזהות שזו נוסחת הנסיגה של מיון מיזוג, ולכן פתרונה $\displaystyle T(n)=\Theta (n\cdot \log(n))$.

2

הפתרון דומה מאד למיון ספירה. ראשית, הנה הפסוודו-קוד לInit:

# A global array.
1	Count

Init(Values, k)
1	Count = Make-Array(k)

2	for i in [1, ..., k]
3		Count[i] = 0
	
4	for j in [1, ..., Length(Values))
5		value = Values[j]
6		++Count[value]
	
7	for i in [2, ..., k]
8		Count[i] = Count[i] + Count[i - 1]

המערך Count הוא משתנה גלובלי. הפונקציה Range מאתחלת אותו כך שהאיבר הi שלו מכיל את מספר האיברים הקטנים או שווים לi בA. בניתוח מיון ספירה ראינו שהסיבוכיות היא $\displaystyle \Theta (n+k)$.

לאחר שאתחלנו את המערך Count, הפונקציה Range פשוטה מאד. כל שעלינו לעשות הוא לחסר את מספר האיברים הקטנים מa ממספר האיברים הקטנים או שווים לb:

Range(a, b)
	# First find the number of values less than a.
1	if a == 1
2		less-than-a = 0
3	else if a - 1 ≤ Length(Count)
4		less-than-a = Count[a - 1]
5	else
6		less-than-a = Count[Length(Count)]

	# Now find the number of values less than or equal to b.

7	if b ≤ Length(Count)
8		at-most-b = Count[b] 
9	else
10		at-most-b = Count[Length(Count)]
	
	# The answer is obviously the difference between the two.
11	return at-most-b - less-than-a

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

3

א'

נתבונן בפסוודו-קוד עם memoization:

Min-Time(i, j)
1	if M[i][j] != Nil
2		return M[i][j]

3	if i == j
4		M[i][j] = 0
5		return 0
	
6	min-time = ∞
	
7	for k in [i, ..., j - 1]
8		guess = Min-Time(i, k) + Min-Time(k + 1, j) + PQR(i, k, j)
	
9		if guess M[i][j] < min-time
10			M[i][j] = min-time = guess
				
11	return min-time

נשים לב שאם נניח שכל קריאה רקורסיבית אורכת $\displaystyle O(1)$, אז יש לנו מספר קריאות שכ"א היא $\displaystyle O(1)$ (1-6, 11), ולולאה בת $\displaystyle j-i$ איטרציות, כאשר כל איטרציה היא $\displaystyle O(1)$. זמן הריצה, לכן הוא $\displaystyle T'(i,j)=O(1)+(j-i)\cdot O(1)=\Theta (j-i+1)$.

ב'

ההוכחה חוזרת, למעשה, על זו של דג הסלמון.

נצייר את עץ הקריאות הרקורסיביות, תוך לקיחה בחשבון את נושא הmemoization.

עץ הקריאות הרקורסיביות.

הציור אינו מראה את כל צמתי הקריאה מטעמי נוחות. הצומת $\displaystyle 1,n$ קורא לצומת $\displaystyle 1,1$, בעקיפין לצמתים $\displaystyle 2,2$ ו$\displaystyle 23,36$, ולעוד צמתים. הקווים המקווקווים מציינים שהקריאות אינן בהכרח ישירות.

חלק מהצמתים מודגשים, וחלק אינם:

1. צומת מודגש אם הוא מתאר קריאה "רצינית", כלומר אחת שבה החלק העיקרי בפונקציה מתבצע (שורות 3-11 בMin-Time).
2. צומת אינו מודגש אם הוא מתאר קריאה "פושטית", בה לכל היותר רק חלק הmemoization מתבצע (שורות 1-2 בMin-Time).

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

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

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

1. ניקח צומת $\displaystyle i,j$ מודגש שאין לו ילדים מודגשים.
2. ננתח את זמן הריצה שלו, ונרשום את התוצאה בצד. נשים לב שאם לצומת אין ילדים מודגשים, אז כל קריאה רקורסיבית שלו היא אכן $\displaystyle O(1)$ (מפני שזו איננה ממש קריאה רקורסיבית). זמן הריצה שלו, לכן, הוא אכן $\displaystyle T'(i,j)$.
3. נמיר אותו בצומת לא מודגש, מפני שניתחנו כבר את חלק הקוד המסובך בו (ורשמנו אותו בצד). כל שנותר הוא הקריאה לפונקציה, והיא לוקחת $\displaystyle O(1)$.

נתחיל בצומת $\displaystyle 1,1$ המודגש. לצומת זה אין כלל ילדים, ולכן זמן הקריאה הוא בבירור $\displaystyle T'(1)$. נרשום בצד שעד כה הקריאות שעברנו עליהן עלו $\displaystyle T'(1)$, ונחליף את הצומת $\displaystyle 1,1$ בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת $\displaystyle 1,1$, וכל שנותר הוא $\displaystyle O(1)$.

עץ הקריאות הרקורסיביות - שלב 1.

נחזור על אותה הפעולה עבור הצומת $\displaystyle 2,2$.

עץ הקריאות הרקורסיביות - שלב 2.

כנ"ל לגבי הצומת $\displaystyle 23,23$.

עץ הקריאות הרקורסיביות - שלב 3.

כעת נתבונן בצומת $\displaystyle 23,36$ בשלב בו כל ילדיו אינם מודגשים. כל קריאה רקורסיבית של צומת זה כוללת שני מחירים:

• עצם הקריאה לפונקציה, שעולה $\displaystyle O(1)$
• זמן הקריאה האמיתי, שאותו כבר חייבנו (ורשמנו בצד), ולכן אין צורך לחייב אותו כאן שוב

הפועל היוצא הוא שבשלב זה, מותר לנו לחייב את הצומת אך ורק בקריאות רקורסיביות שעלות כל אחת מהן היא $\displaystyle O(1)$. זה בדיוק $\displaystyle T'(23,36)$.

קל להשתכנע שבשלב בו נחליף את צומת הראש בצומת לא מודגש, רשמנו בצד את כל האיברים מהצורה $\displaystyle T'(i,j)$, כאשר $\displaystyle 1\leq i\leq n$ ו$\displaystyle j\leq i\leq n$. בצורה אחרת, מה שרשום בצד הוא $\displaystyle \sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]$.

ג'

נשלב את שני הסעיפים הקודמים: $\displaystyle T(1,n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]$.

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

4

המבנה הרקורסיבי

נגדיר את $\displaystyle m(i,j)$ כאיכות המשוקללת הגבוהה ביותר האפשרית כאשר יש $\displaystyle j$ עובדות ו$\displaystyle i$ פרוייקטים.

משפט: $\displaystyle m(i,j)$ = $\displaystyle h(1)q(1,j)$, אם $\displaystyle i=1$. $\displaystyle \max _{j'\;|0\leq j'\leq j}\left[h(i)q(i,j')+m(i-1,j-j')\right]$, אם $\displaystyle i>1$.

הוכחה: אם יש פרוייקט יחיד, אז ברור שכדאי להקצות את כל העובדות לו (שהרי נתון שהוספת עובדות אינה יכולה להוריד את איכות הפרוייקט). לכן, אם יש פרוייקט יחיד ו$\displaystyle j$ עובדות, נקבל שאיכותו הטובה ביותר היא $\displaystyle q(1,j)$.

נניח שיש $\displaystyle i>1$ פרוייקטים. אם נקצה $\displaystyle j'$ עובדות לפרוייקט ה$\displaystyle i$, אז איכות הפרוייקט תהיה $\displaystyle q(i,j')$, ונוותר עם $\displaystyle j-j'$ עובדות. על פי הגדרתנו, $\displaystyle m(i-1,j-j')$ הוא הטוב ביותר שנוכל להשיג במקרה זה.

פסוודו-קוד

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

Max-Value(i, j)
1	if i == 1
2		return h(1) q(1, j)

3	max-value = 0
4	for j' in [0, ..., j]
5		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
6		if guess > max-value
7			max-value = guess

8	return max-value

הדפסת פרטי הפתרון

נוסיף עוד מטריצה גלובלית A כך שA[i][j] מתארת את מספר העובדות האופטימלי שכדאי להקצות לפרוייקט ה$\displaystyle i$ אם יש $\displaystyle i$ פרוייקטים ו$\displaystyle j$ עובדות.

להלן הקוד המכיל את השינויים הנדרשים:

Max-Value(i, j)
1	if i == 1
2		A[1][j] = j
3		return h(1) q(1, j)

4	max-value = 0
5	for j' in [0, ..., j]
6		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
7		if guess > max-value
8			A[i][j] = j'
9			max-value = guess

10	return max-value

כעת נשתמש במטריצה כדי להדפיס את האלוקציות האופטימליות:

Print-Assignments(i, j)
1	if i == 0
2		return

	# The optimal assignment assigns j' workers to project i.
3	j' = A[i][j] 

4	Print('Assign ' + j' + ' workers to project ' + i)

5 	Print-Assignments(i - 1, j - j')

כך נפעיל את שתי הפונקציות:

1	A = Make-Matrix(k, n)

2	max-value = Max-Value(k, n)

3	Print(max-value)

4	Print-Assignments(k, n)

הוספת תזכור (memoization)

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

Max-Value(i, j)
1	if i == 1
2		M[1][j] = h(1) q(1, j)
3		return h(1) q(1, j)

4	max-value = 0
5	for j' in [0, ..., j]
6		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
7		if guess > max-value
8			M[i][j] = guess
9			max-value = guess

10	return max-value

ניתוח סיבוכיות

כרגיל, נגדיר את $\displaystyle T'(i,j)$ כזמן הריצה של Max-Value(i, j) כאשר כל קריאה רקורסיבית היא $\displaystyle O(1)$. קל לראות שמתקיים $\displaystyle T'(i,j)=\Theta (j)$

כרגיל, נמצא את זמן הריצה האמיתי של הקריאות הרקורסיביות כך:

$\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}[T'(i,j)]=$
$\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}[\Theta (j)]=$
$\displaystyle \sum _{i=1}^{k}[\Theta (n^{2})]=$
$\displaystyle \Theta (k\cdot n^{2}).$

יש לקחת בחשבון גם את זמן הריצה של אתחול המטריצה (M ואת הדפסת פרטי הפתרון:

• אתחול המטריצה אורך$\displaystyle \Theta (k\cdot n)$
• הדפסת הפרטים אורכת $\displaystyle \Theta (k)$

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

$\displaystyle \Theta (k\cdot n)+\Theta (k)+\Theta (k\cdot n^{2})=\Theta (k\cdot n+k+k\cdot n^{2})=\Theta (k\cdot n^{2})$

5

המבנה הרקורסיבי

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

משפט: $\displaystyle m(i)$ נתונה על ידי נוסחת הנסיגה הבאה: אם $\displaystyle i=1$,‏ אז $\displaystyle f(1)$. אם $\displaystyle i>1$,‏ אז $\displaystyle \min \left\{f(i),\min _{1\leq j<i}\left\{m(j)+k+m(i-j)\right\}\right\}$.

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

1. אם $\displaystyle i=1$,‏ אז אין מה לחתוך; ההובלה תעלה $\displaystyle f(1)$.
2. אם $\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})$.

6

פסוודו-קוד

להלן הפסוודו-קוד לאלגוריתם:

ּSelection-Sort(Values)
1	for i in [1, ..., n - 1]
2		min = i
3		for j in [i + 1, ..., n]
4			if Values[j] < A[min]
5				min = j

		# Exchange Values[i] and Values[min]
6		Values[i] <-> Values[min]

הוכחת נכונות

הנכונות מתבססת על המשפט הבא:

משפט: בסוף האיטרציה ה$\displaystyle i$ של 1-6, Values[1, ..., i] הוא מערך ממויין המכיל את $\displaystyle i$ האיברים הקטנים ביותר במערך המקורי.

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

הוכחת נכונות

קל להראות שהסיבוכיות היא $\displaystyle O(n^{2})$, ושיש קלט שעבורו הסיבוכיות היא $\displaystyle \Omega (n^{2})$, וגם זאת בצורה דומה למה שראינו בזו של מיון הכנסה.

7

נטפל בבעיה זו בתרגול התגבור בנושא.