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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי


שימו לב:

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


1[עריכה]

הגדרה:

נתונה סידרה של מספרים שונים זה מזה. היא תת-סידרה עולה של אם:

  1. קיימת סדרה עולה ממש של אינדקסים כך ש לכל .
  2. היא סידרה עולה.




דוגמה:

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



הגדרה:

אם היא סידרה, אז היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של .


הנח שX הוא מערך גלובלי המתאר את הסדרה , בעלת האורך . בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.


2[עריכה]

אנא הוכח ש.


רמז

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


כדאי לדעת:

נצטרך חסם זה כשננתח את סיבוכיות בניית ערימה בינרית ממערך.

3[עריכה]

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:

  1. כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
    1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
    2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
  2. העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
    1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
    2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
  3. כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.



דוגמה: צומת Bar

צומת Bar.
צומת Bar.



דוגמה: צומת Foo

צומת Foo.
צומת Foo.



דוגמה: עץ Foo-Bar

להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2.

עץ Foo-Bar.
עץ Foo-Bar.


אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו מפתחות וגבהו הוא , אז .


שימו לב:

אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי.

4[עריכה]

הגדרה:

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




דוגמה:

  1. החציון של הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).
  2. החציון של הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).
  3. החציון של הוא 2.5 (2 ו3 הם איבריה האמצעיים של איבריה הממויינים).
  4. החציון של הוא 2 (2 הוא האיבר האמצעי של איבריה הממויינים).


רוצים לממש ביעילות מבנה נתונים Median בעל הממשק הבא:

# Makes a Median data-structure.
Make-Median()

# Adds another value (v) to a Median data-structure (m).
Insert(m, v)

# Returns the median of all the values in
#	a Median data-structure (m).
Med(m)

להלן דוגמה לשימוש במבנה הנתונים:

# Makes a median data-structure.
m = Make-Median()

# Inserts 1.
Insert(m, 1)
# Inserts 9.
Insert(m, 9)
# Inserts 2.
Insert(m, 2)

# Prints 2 (the median of {1, 9, 2}).
Print( Med(m) )

# Inserts 100.
Insert(m, 100)

# Prints 4.5 (the median of {1, 9, 2, 100}).
Print( Med(m) )

אנא הסבר כיצד לממש את מבנה הנתונים ביעילות.

5[עריכה]

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

# 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)

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

6[עריכה]

נניח שנתנה לך פונקציה יעילה LCS(X, Y) הפותרת את בעיית תת-המחרוזת המשותפת הארוכה ביותר. אנא הצע אלגוריתם יעיל Convert(X) המקבל מחרוזת, ומחזיר מחרוזת שתקיים תמיד שLCS(X, Convert(X)) הוא אורך תת-המחרוזת העולה הארוכה ביותר של X.

אנא הוכח את נכונות תשובתך, ונתח את סיבוכיות הפונקציה Convert במונחי ארכו של X.

7[עריכה]

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



דוגמה:

נניח שעץ החיפוש מכיל את המפתחות . יש 2 עצים מתאימים:

עצי חיפוש בינריים בעלי המפתחות 1 ו2.
עצי חיפוש בינריים בעלי המפתחות 1 ו2.

נניח שעץ החיפוש מכיל את המפתחות . יש 5 עצים מתאימים:

עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.
עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.



מהדוגמה נוכל להסיק כי

, , .


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