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

1

נשתמש במספר סימונים ומשפטים פשוטים:

1. נגדיר את הרישה ה$\displaystyle i$ של מחרוזת $\displaystyle X$ כ$\displaystyle X_{i}=x_{1},...,x_{i}$.‏
2. נגדיר כ$\displaystyle l(i)$ את אורך הLIS של $\displaystyle X_{i}$ שאיברה האחרון הוא $\displaystyle x_{i}$.
3. נשים לב ש:
   1. $\displaystyle \max _{1\leq i\leq n}[l(i)]$ הוא אורך הLIS של $\displaystyle X$.
   2. $\displaystyle l(i)$ מקיים את הנוסחה $\displaystyle l(i)=1+\max _{1\leq j<i,\;x_{j}\leq x_{i}}[l(j)]$.

בפתרון נשתמש במערך גלובלי L המתאר, בכניסה ה$\displaystyle i$, את האיבר הקטן ביותר עד כה המסיים תת-סידרה עולה באורך $\displaystyle i$.

אלה שלבי פעולות הפתרון:

1. נאתחל את כל אחד מאיברי L ל$\displaystyle \infty$.
2. נעבור בלולאה, משמאל לימין, על איברי X. כשנגיע לאיבר ה$\displaystyle i$:
   1. נחפש את האיבר הגדול ביותר ב בL[1], ..., L[i - 1] שאינו גדול מX[i].
   2. אם מצאנו איבר כזה בכניסה ה$\displaystyle j$ של L, נקבע L[j + 1] = X[i].
   3. אם לא, נקבע L[1] = X[i].
3. נמצא את האיבר הגדול ביותר בL שאינו $\displaystyle \infty$, ונחזיר את האינדקס שלו כתשובה המבוקשת.

דוגמה: נניח שX == [1, 5, 2, 3]. תחילה נאתחל את המערך L, כך שL == [∞, ∞, ∞, ∞]. כעת נעבור בלולאה על איברי X: כשi == 1,‏ אז X[i] == 1. בL אין שום איבר קטן מ1 בתחום $\displaystyle [1:0]$. נקבע, לכן, L[1] = 1. בשלב זה L = [1, ∞, ∞, ∞]. כשi == 2,‏ אז X[i] == 5. האיבר הגדול ביותר בL שאינו גדול מ5, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 5. בשלב זה L = [1, 5, ∞, ∞]. כשi == 3,‏ אז X[i] == 2. האיבר הגדול ביותר בL שאינו גדול מ2, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 2. בשלב זה L = [1, 2, ∞, ∞,]. כשi == 4,‏ אז X[i] == 3. האיבר הגדול ביותר בL שאינו גדול מ4, הוא 2 באינדקס 2. נקבע, לכן, L[3] = 3. בשלב זה L = [1, 2, 3, ∞].האיבר הגדול ביותר בL שאינו $\displaystyle \infty$, הוא 3. נחזיר, לכן, את האינדקס שלו - 3.

את המשפט הבא קל להוכיח באינדוקציה:

משפט: בסוף האיטרציה ה$\displaystyle i$ של הלולאה: L ממוין. אם האיבר ה$\displaystyle j$ בL אינו $\displaystyle \infty$, אז יש תת-סידרה עולה בX[1], ..., X[i] המסתיימת באיבר שערכו L[j].

להלן הפסוודו-קוד המתאים:

1	L = Make-Array(n)
	
2	for i in [1, ..., n]
3		L[i] = ∞

4	for i in [1, ..., n]
5		j = Smaller-Index(L, X[i])
6			L[j + 1] = X[i]

7	max = 0
8	for i in [1, ..., n]
9		if L[i] > max and L[i] < ∞
10			max = L[i]

הנה הסבר לפסוודו-קוד:

1. ב1-3 מאתחלים את L. קל לראות שהסיבוכיות לינארית.
2. ב4-6 מעדכנים את L על פי ההסבר שראינו למעלה. הפונקציה Smaller-Index, שמימושה אינו מופיע כאן, ניתנת למימוש בקלות באופן דומה למה שראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] (שים לב שL ממוין). הסיבוכיות היא $\displaystyle \sum _{i=1}^{n}[O(\log(i))]=O(n\cdot \log(n))$.
3. ב7-10 מחפשים את המקסימום בL. קל לראות שהסיבוכיות לינארית.

2

מצד אחד, כל טור גדול לפחות כמו איברו הראשון. מכאן נקבל: $\displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\geq [2^{-1}\Theta (1)]\geq \Theta (1)$ ולכן הטור המקורי הוא $\displaystyle \Omega (1)$.

מצד שני, נקבל $\displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\leq \sum _{j=1}^{\infty }[2^{-j}\Theta (j)]=\Theta \left(\sum _{j=1}^{\infty }[2^{-j}j]\right)$, ולכן נחסום מלמעלה את $\displaystyle \sum _{j=1}^{\infty }[2^{-j}j]$.

עבור ערכי $\displaystyle j$ מספיק גדולים, $\displaystyle 2^{-j}j<1.5^{-j}$ (קל לראות זאת מל'וספיטל, לדוגמה). נגדיר את $\displaystyle k$ כאינדקס הראשון בו $\displaystyle 2^{-k}k<1.5^{-k}$. נקבל $\displaystyle \sum _{j=1}^{\infty }[2^{-j}j]=\sum _{j=1}^{k-1}[2^{-j}j]+\sum _{j=k}^{\infty }[2^{-j}j]\leq O(1)+\sum _{j=k}^{\infty }[1.5^{-j}]\leq O(1)+\sum _{j=1}^{\infty }[1.5^{-j}]=O(1)+O(1)=O(1)$

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

3

הפתרון דומה מאד להוכחת הטענה שעצים אדומים-שחורים הם לוגריתמיים. נניח שגובה העץ הוא $\displaystyle h$. מה מספר המפתחות הקטן ביותר היכול להיות בעץ? קל לראות שזה המספר המתקבל כאשר כל אחד מהצמתים הוא מסוג Bar. במצב זה, היות שעל פי הנתונים כל המסלולים משורש לעלה הם בעלי אותו אורך, נקבל שמספר המפתחות הוא לכל הפחות $\displaystyle \sum _{i=1}^{h}\left[2^{i-1}\right]=2^{h}-1$. הפתרון, לכן, מתקבל על ידי פתירת אי-השוויון $\displaystyle n\geq 2^{h}-1$:

$\displaystyle n\geq 2^{h}-1\Rightarrow$
$\displaystyle n\geq 2^{h}/2\Rightarrow$
$\displaystyle \log(n)\geq h-1\Rightarrow$
$\displaystyle h=O\left(\log(n)\right)$

4

להלן מימוש יעיל אפשרי:

Median
# A min binary heap.
# This will be used to store the half of the larger values.
1	min-bh

# A max binary heap.
# This will be used to store the half of the smaller values.
2	max-bh


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

2	m.min-bh = Make-Binary-Heap()
3	m.max-bh = Make-Binary-Heap()


# Adds another value (v) to a Median data-structure (m).
Insert(m, v)
1	if Size(m.max-bh) == 0 or v < Med(m)
2		Insert(m.max-bh)
3	else
4		Insert(m.min-bh)

5	if Size(m.max-bh) > Size(m.min-bh) + 1
6		Insert(m.min-bh, Delete-Max(m.max-bh))
7	else if Size(m.min-bh) > Size(m.max-bh) + 1
8		Insert(m.max-bh, Delete-Min(m.min-bh))


# Returns the median of all the values in	a Median data-structure (m).
Med(m)
1	if Size(m.min-bh) == Size(m.max-bh)
2		return (Min(m.min-bh) + Max(m.max-bh)) / 2

3	if Size(m.min-bh) > Size(m.max-bh)
4		return Min(m.min-bh)

5	return Max(m.max-bh)

הנה הסבר לפתרון. מבנה הנתונים כולל שני תורי קדימויות ‏:max-bh וmin-bh (שורות 1-2 של Median ו2-3 של Make-Median). ‏ הראשונה מיועדת לשמירת חצי האיברים הקטנים יותר, והיא ערימה בינרית השומרת על האיבר הגדול ביותר בראש הערימה; השנייה מיועדת לשמירת חצי האיברים הגדולים יותר, והיא ערימה בינרית השומרת על האיבר הקטן ביותר בראש הערימה.

תורי הקדימויות בחציון דינאמי.

אם הפרש הגדלים בין גדלי שתי הערימות הוא $\displaystyle \pm 1$ (כלומר, שתי הערימות מחלקות את כל האיברים לשני חלקים שווים כמעט בגדלם), אז החציון הוא בהכרח האיבר בראש אחת מהערימות, או ממוצע ראשי האיברים (שורות 1-5 של Med). זאת אומרת שמציאת החציון דורשת לכל היותר שתי קריאות לSize, Min,‏ וMax של ערימה בינרית - פעולות שהן $\displaystyle O(1)$ כל אחת.

כעת נשאר רק לדאוג שהפרש הגדלים בין שתי הערימות הוא אכן $\displaystyle \pm 1$. כאשר מכניסים איבר חדש, בוחרים לאיזו ערימה להכניס אותו, על ידי השוואתו לחציון (שורות 1-4 של Insert). אם אחת הערימות נהיית גדולה מדי (לדוגמה max-bh), אז שולפים ממנה את איבר הראש, ודוחפים אותו לערימה השנייה.

העברה בין שני תורי הקדימויות בחציון דינאמי.

מבדיקת פעולות הערימה הבינרית שנעשות, קל להווכח שסיבוכיות Insert היא $\displaystyle O(\log(n))$,‏ וסיבוכיות Med היא $\displaystyle O(1)$.‏

5

1. הטענה נכונה. נניח שבערימה יש $\displaystyle s$ איברים. האיבר האחרון בערימה הוא באינדקס $\displaystyle s$, ואביו (אם יש לו) בהכרח יושב ב$\displaystyle \left\lfloor {\frac {s}{2}}\right\rfloor$. לכן, למרות שהלולאה אינה עוברת על כל האיברים, היא מדלגת רק על ערימות בעלי איבר יחיד, שהן, עפ"י תכונת הערימה, תקינות. הלולאה תתקן כל ערימה שדורשת תיקון, בדיוק מהסיבה שראינו בהרצאה. הסיבוכיות היא $\displaystyle \Theta (n)$. אפשר לראות שהלולאה עוברת על חצי מהאיברים, ולכן היא $\displaystyle \Omega (n)$. מצד שני, היא עושה פחות מBuild-Heap, וזו היתה $\displaystyle O(n)$, ולכן גם לולאה זו $\displaystyle O(n)$.
2. הטענה נכונה. אם ילדו השמאלי של איבר במקום $\displaystyle i$ נמצא באינדקס $\displaystyle 2\cdot i$, וילדו הימני נמצא באינדקס $\displaystyle 2\cdot i+1$, אז כל מסלול מהשורש לעלה עובר על סדרת אינדקסים מונוטונית עולה. לכן, אם המערך ממויין, כל מסלול מהשורש לעלה יעבור על סדרת ערכים מונוטונית לא-יורדת. הסיבוכיות הנה מיון מיזוג, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.
3. הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [3,4,2,1]$. הסיבוכיות הנה $\displaystyle \Theta (n)$, בדיוק מהניתוח שכבר ראינו לגבי הפתרון מההרצאה.
4. הטענה נכונה. היות ש Bubble-Up(bh, i) אינו יכול להשפיע על איברים באינדקס מעל $\displaystyle i$, הקוד שקול לסדרת פעולות Insert. מאותה סיבה, הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.
5. הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [4,1,2,3]$. הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.

6

הפונקציה Convert(X) פשוט תחזיר את המערך ממויין בסדר עולה. (אם נשתמש במיון מיזוג, אז הסיבוכיות תהיה $\displaystyle \Theta (n\log(n))$).

נניח שהמערך המקורי הוא $\displaystyle X$, והמערך הממויין הוא $\displaystyle X'$.

כל תת-מחרוזת עולה של $\displaystyle X$, נניח $\displaystyle Y$, היא תת-מחרוזת משותפת ל$\displaystyle X$ ו$\displaystyle X'$: היא בהכרח תת-מחרוזת של $\displaystyle X$ לפי ההגדרה, והיא תת-מחרוזת של $\displaystyle X'$ מפני שהיא מחרוזת עולה שאיבריה הם איברי $\displaystyle X$.

לכן, בפרט, תת-המחרוזת המשותפת הארוכה ביותר היא גם בהכרח תת-המחרוזת העולה הארוכה ביותר של $\displaystyle X$.

7

כבר ראינו את נוסחת הנסיגה $\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]$. נשתמש בזאת כדי להוכיח את הטענה בשאלה באינדוקציה. נראה שקיים $\displaystyle c>0$ כך שתמיד $\displaystyle T(n)\geq c\cdot 2^{n}$.

הוכחה: (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונראה שהיא נכונה גם ל$\displaystyle n$.

$\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]\geq$
$\displaystyle \sum _{i=0}^{n-1}[c\cdot 2^{i}\cdot c\cdot 2^{n-i-1}]=$
$\displaystyle {\frac {c^{2}}{2}}\sum _{i=0}^{n-1}[2^{n}]=$
$\displaystyle {\frac {n\cdot c}{2}}c\cdot 2^{n}$

נפתור $\displaystyle {\frac {n\cdot c}{2}}\geq 1$, ונקבל $\displaystyle c\geq {\frac {2}{n}}$. עבור $\displaystyle n\geq 5$, נקבל שמספיק שיתקיים $\displaystyle c\geq {\frac {2}{5}}$.

מבדיקת מספר העצים השונים, עולה שקיים $\displaystyle c$ מתאים גם לבסיס האינדוקציה (המקרים $\displaystyle n\leq 4$).