לדלג לתוכן

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

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


שימו לב:

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


הגדרה:

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

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




דוגמה:

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



הגדרה:

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


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


אנא הוכח ש.


רמז

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


כדאי לדעת:

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

בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ 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 הוא לוגריתמי: אם יש בו מפתחות וגבהו הוא , אז .


שימו לב:

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

הגדרה:

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




דוגמה:

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

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

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

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

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

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

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

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



דוגמה:

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

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

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

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



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

, , .


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