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

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

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

שאלה 1

(~12 נקודות)

ליריד התעסוקה של האוניברסיטה הגיעו $\displaystyle m$ סטודנטים, $\displaystyle 1,\ldots m$, ו$\displaystyle n$ חברות, $\displaystyle 1,\ldots n$. נניח שכל סטודנט מוכן לעבוד בחברה אחת או יותר, וכל חברה מוכנה להעסיק סטודנט אחד או יותר, אך כל סטודנט יכול לעבוד בחברה אחת לכל היותר, וכל חברה יכולה להעסיק מספר ידוע של סטודנטים, שהוא לפחות 1.

נתון מערך רצון התעסוקה W, שבו $\displaystyle r$ זוגות. אם הזוג (i, j) מופיע בW, אז המשמעות היא שסטודנט $\displaystyle i$ מוכן לעבוד בחברה $\displaystyle j$, וחברה $\displaystyle j$ מוכנה להעסיק את סטודנט $\displaystyle i$. כמו כן, נתון מערך פוטנציאל ההעסקה P, שבו $\displaystyle n$ מספרים שלמים. P[j] מתאר את מספר המשרות הפנויות בחברה $\displaystyle j$ .

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

1. אם הזוג (i, j) מופיע בW', אז הוא גם מופיע בW.
2. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו הראשון $\displaystyle i$.
3. מספר הזוגות מהצורה (i, j) בW' בעלי אותו $\displaystyle j$, הוא לכל היותר $\displaystyle P[j]$.

שאלה 2

(~33 נקודות)

מעל הירקון עומד גשר שאורכו $\displaystyle m$ מטרים ($\displaystyle m$ מספר שלם חיובי גדול מ1 כלשהו). הגשר נמצא לא תקין אפילו בסטנדרטים של מדינת ישראל(!). יש לפרק את הגשר לחלקים ולפנותו בצורה הזולה ביותר. ראשית צריך לשבור את הגשר. ניתן לשבור את הגשר למספר חלקים. שבירת הגשר חייבת להתבצע בנקודות $\displaystyle 1,\cdots ,m-1$ בלבד. שבירת כל נקודה עולה $\displaystyle k$ שקלים ($\displaystyle k$ מספר שלם חיובי כלשהו).

דוגמה: נניח $\displaystyle m=3$ ו$\displaystyle k=100$ (ראה A בתרשים הבא). אפשר לשבור את הגשר ב4 אפנים: שוברים בנקודות 1 ו2. מתקבלים 3 חלקים בעלי אורך 1 כל אחד (ראה B בתרשים הבא). עלות השבירה היא $\displaystyle 2\cdot 100=200$. שוברים בנקודה 1. מתקבלים 2 חלקים: הראשון בעל אורך 1, והשני בעל אורך 2 (ראה C בתרשים הבא). עלות השבירה היא $\displaystyle 1\cdot 100=100$. שוברים בנקודה 2. מתקבלים 2 חלקים: הראשון בעל אורך 2, והשני בעל אורך 1 (ראה D בתרשים הבא). עלות השבירה היא $\displaystyle 1\cdot 100=100$. לא שוברים באף נקודה. מתקבל חלק יחיד בעל אורך 3. עלות השבירה היא $\displaystyle 0\cdot 100=0$. דוגמה לגשר הזבלה.

כעת יש להוביל את חלקי הגשר. הנח שקיימת פונקציה $\displaystyle f$ ידועה כך ש$\displaystyle f(i)$ מתארת את עלות הובלתו של חלק בעל אורך i. הנח ש$\displaystyle f(i)$ הוא מספר שלם חיובי לכל $\displaystyle i$.

שימו לב: וודא שאינך מניח במובלע דברים שלא נאמרו לגבי $\displaystyle f(i)$. בפרט, אל תניח שהפונקציה מונוטונית עולה (עלות ההובלה נקבעת לפי שיקולים שאיננו יודעים.)

דוגמה: בהמשך לדוגמה הקודמת שראינו, נניח $\displaystyle f(1)=1$,‏ $\displaystyle f(2)=10$,‏ ו$\displaystyle f(3)=2$. ארבע האפשרויות שראינו מקודם יעלו כך: עלות ההובלה היא $\displaystyle f(1)+f(1)+f(1)=3$. עלות ההובלה היא $\displaystyle f(1)+f(2)=11$. עלות ההובלה היא $\displaystyle f(2)+f(1)=11$. עלות ההובלה היא $\displaystyle f(3)=2$.

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

שאלה 3

(~33 נקודות)

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

דוגמה: בתרשים הבא, עלות הנסיעה בכביש מ1 ל2 היא $\displaystyle 1$. כבישי אגרה, עם כביש אחד שלילי.

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

דוגמה: בתרשים הקודם, עלות הנסיעה בכביש מ7 ל3 היא $\displaystyle -3$.

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

אנא מצא אלגוריתם יעיל המקבל את הגרף, טבלת עלויות לקשתות, וצומת מוצא $\displaystyle s$, ומחזיר, עבור כל צומת $\displaystyle u$, את עלות המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$.

דוגמה: בתרשים הקודם, נניח שצומת המוצא הוא $\displaystyle s=1$: המסלול הזול ביותר מ$\displaystyle s$ ל6 הוא $\displaystyle 1\rightarrow 6$,‏ ועלותו 2. המסלול הזול ביותר מ$\displaystyle s$ ל4 הוא $\displaystyle 1\rightarrow 6\rightarrow 7\rightarrow 3\rightarrow 4$,‏ ועלותו 3.

שאלה 4

(~28 נקודות)

הסטודנט העיראקי איפ חמיס תברא מתבונן בקטע הקוד הבא:

# Makes a binary heap from an array (Values).
Build-Heap(Values)
1	bh = Make-Priority-Queue()
	
2	bh.size = Length(Values)	
	
3	for i in [1, ..., Length(Values)]
4		bh.Values[i] = Values[i]
		
5	Arrange(bh)
	
6	return bh

קטע קוד זה מקבל מערך, ומחזיר ערימה בינרית . איפ חוכך בדעתו כיצד מומשה הפונקציה Arrange. (אנו למעשה כבר ראינו את המימוש הבא:

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Down(bh, i)

אך הוא אינו יודע זאת).

מספר אפשרויות עולות על דעתו:

Arrange(bh)
1	for i in [⌊Length(bh.Values) / 2⌋, ..., 1]
2		Bubble-Down(bh, i)

Arrange(bh)
1	Merge-Sort(bh.Values)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Down(bh, i)

Arrange(bh)
1	for i in [1, ..., Length(bh.Values)]
2		Bubble-Up(bh, i)

Arrange(bh)
1	for i in [Length(bh.Values), ..., 1]
2		Bubble-Up(bh, i)

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