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

שימו לב: *נא להגיש רק את שאלות 1-5. שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

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

1

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$ בייצוג רשימה, וטבלת עלויות לקשתות Edge-Costs.‏ $\displaystyle k$ הוא מספר שלם חיובי כלשהו, שאינו גדל עם שאר נתוני הבעיה (כגון מספר הצמתים והקשתות). ידוע שלכל קשת מחיר בתחום $\displaystyle [1,k]$. אנא מצא אלגוריתם יעיל למציאת עץ פורש מינימום בגרף כגון זה.

2

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות על הקשתות Edge-Costs.

הגדרה: קבוצת קשתות $\displaystyle E'\subseteq E$ היא קבוצת קשתות היזון חוזר אם לאחר הסרתה, $\displaystyle G$ חסר מעגלים; במילים אחרות, הקבוצה היא קבוצת קשתות היזון חוזר אם $\displaystyle G'=(V,E\ E')$ הוא יער.

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

רמז אל תתמקד בקבוצה $\displaystyle E'$, אלא בקבוצה המשלימה אותה, $\displaystyle E\setminus E'$. אם $\displaystyle E'$ היא קבוצת קשתות ההיזון החוזר הזולה ביותר - מהי $\displaystyle E\setminus E'$?‏ אם $\displaystyle E'$ היא קבוצת קשתות ההיזון החוזר הזולה ביותר - איך תוכל למצוא את הקבוצה המשלימה לה ביעילות?

3

להלן גרסה של אלגוריתם החיפוש הרוחבי:

BFS(G, s)
1	q = Make-Queue()

2	Visited = Make-Array( |V| )

3	for u in V
4		Visited[u] = False

5	Print s
6	Visited[s] = True
7	Enqueue(q, s)

8	while not Empty(q)
9		u = Dequeue(q)
	
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Enqueue(q, v)

גרסה זו עוברת על כל הצמתים ברכיב הקשירות של $\displaystyle s$ ומדפיסה אותם לפי סדר ההגעה מ$\displaystyle s$.

להלן גרף $\displaystyle G$ שבו צומת המוצא הוא $\displaystyle s$.

בעיית החיפוש הרוחבי.

הנח שבשורה 10, אם לצומת $\displaystyle u$ יש יותר משכן יחיד, סדר הצמתים הוא כסדרם המספרי.

1. באיזה סדר יודפסו האיברים?
2. נניח ש $\displaystyle G=(V,E)$ קשיר מ$\displaystyle s$ (יש מסלול מ$\displaystyle s$ לכל צומת). אנא הוכח שהאלגוריתם יעבוד בזמן $\displaystyle \Theta (|V|+|E|)$.

4

נחזור שוב לאלגוריתם בשאלה סדר הדפסת הצמתים וזמן הריצה, אך כעת נניח שיש מסלול מ$\displaystyle s$ רק ל$\displaystyle |V|^{\alpha }$ מהצמתים, כאשר $\displaystyle \alpha <1$ הוא קבוע כלשהו.

1. האם זמן הריצה הוא בהכרח $\displaystyle \Theta (|V|+|E|)$?
2. האם ייתכן שזמן הריצה הוא $\displaystyle \Theta (|V|+|E|)$?

5

נתון טיפוס אבסטרקטי "שק" בעל הממשק הבא:

#Makes a new sack.
Make-Sack()

# Inserts an element (v) to a sack (ks).
Insert(k, v)

# Returns whether the sack is empty.
Empty(k)

# Deletes *some* element from a (non-empty) sack (k) and returns the value of 
#	the deleted element.
Delete(k)

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

להלן ווריאציה אפשרית של אלגוריתם החיפוש הרוחבי, אך כעת עם שק במקום תור:

Sack-Search(G, s)
1	k = Make-Sack()

2	Visited = Make-Array( |V| )

3	for u in V
4		Visited[u] = False

5	Print s
6	Visited[s] = True
7	Insert(k, s)

8	while not Empty(q)
9		u = Delete(k)
	
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Insert(k, v)

נניח שהגרף קשיר מ$\displaystyle s$ (יש מסלול מ$\displaystyle s$ לכל צומת).

1. האם Sack-Search בהכרח ידפיס כל צומת בדיוק פעם יחידה?
2. האם סדר ההדפסות בהכרח יהיה לפי מרחק הצמתים מ$\displaystyle s$?

6

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

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