מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 6/שאלות
שימו לב: *נא להגיש רק את שאלות 1-5.
|
1
[עריכה]
הגדרה: נתונה סידרה של מספרים שונים זה מזה. היא תת-סידרה עולה של אם:
|
דוגמה: נניח ש. אם נקבע , אז היא תת-סידרה עולה של . גם אם נקבע תהיה תת-סידרה עולה של . |
הגדרה: אם היא סידרה, אז היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של . |
הנח שX
הוא מערך גלובלי המתאר את הסדרה , בעלת האורך . בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.
2
[עריכה]אנא הוכח ש.
רמז חלק את הטור לשני טורים; הראשון יהיה טור קצר המכיל מספר קבוע של איברים, והשני יהיה טור ארוך יותר. חסום את הטור השני על ידי טור הנדסי. |
כדאי לדעת: נצטרך חסם זה כשננתח את סיבוכיות בניית ערימה בינרית ממערך. |
3
[עריכה]בכיתה למדנו כבר על עצי חיפוש בינריים. שאלה זו עוסקת בווריאציה. עץ Foo-Bar מוגדר כך:
- כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
- צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
- צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
- העץ מקיים את את תכונת הFoo-Bar - לכל צומת
x
:- כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
- כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
- כל המסלולים משורש העץ לעלה ריק (
Nil
) בעל אותו אורך בדיוק.
דוגמה: צומת Bar |
דוגמה: צומת Foo |
דוגמה: עץ Foo-Bar להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2. |
אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו מפתחות וגבהו הוא , אז .
שימו לב: אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי. |
4
[עריכה]
הגדרה: החציון של קבוצת מספרים מוגדר כך: נגדיר כסדרה ממוינת המורכבת מאיברי ; אם אי זוגי, החציון הוא האיבר האמצעי, ואם זוגי, אז החציון הוא ממוצע שני האיברים האמצעיים. |
דוגמה:
|
רוצים לממש ביעילות מבנה נתונים 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 עצים מתאימים: נניח שעץ החיפוש מכיל את המפתחות . יש 5 עצים מתאימים: |
מהדוגמה נוכל להסיק כי
, , .
אנא הוכח ש, כלומר שמספר עצי החיפוש הבינריים גדל בצורה אקספוננציאלית.