מבני נתונים ואלגוריתמים - מחברת קורס/מבחן סופי מועד א' סמסטר ב' 2008 - תשובות

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

1

א'

נפתור את סעיף ג' כך שיאחד שני מערכים של קוי-רקיע בעלי אורכים שונים (m ו- n) בסיבוכיות: $\theta (n+m)$.

נשתמש באלגוריתם לאחד את הבית (שהוא קו רקיע בגודל 1) עם קו רקיע בעל n איברים.

ב'

נשתמש באלגוריתם מסעיף א' להוסיף את הבתים, בזה אחר זה, לקו רקיע המתחיל ריק. ההוספה הראשונה תקח פעולה אחת, השניה שתים וכן הלאה ונקבל: $\Sigma _{i=1}^{n-1}\theta (i)=\theta (n^{2})$

ג'

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

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

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

• כל עוד לא הגענו למספר הלפני אחרון ברשימת המספרים נבצע את הפעולות הבאות:

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

-- אם המספר הנוכחי לא שווה למספר הבא, הוסף למערך התוצאה בלוק שצידו השמאלי המספר הנוכחי וצידו הימני המספר הבא. גובהו של הבלוק יקבע כך: אם הוא נמצא בשטחו של אחד הבלוקים הנוכחיים גובהו יהיה גובה הבלוק המקסימלי שבשטחו הוא נמצא. אחרת, גובה הבלוק יהיה 0.

-- התקדם למספר הבא.

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

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

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

ד'

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

$T(n)=2T(n/2)+\theta (n)=\theta (n\log(n))$

2

א'

דוגמא:

כיתוב תמונה

ב'

האלגוריתם יהיה וריאציה על אלגוריתם דייקסטרה. בנוסף על מערך המרחקים הקצרים ביותר שמחזיקים באלגוריתם, נחזיק מערך Unique. בהתחלה המערך מאותחל ל-false, כי כל המסלולים באורך אינסוף, ולכן לא ייחודיים (חוץ מצומת s). כאשר נמצא מסלול מינימום חדש לצומת u כלשהו, אז נשנה את הערך של u במערך unique לערך ה-unique של האב החדש (כי אם לאב אין מסלול ייחודי, אז גם לבן). אם נמצא מסלול ל-u, אך הוא לא מינימום חדש, אז: 1. אם הוא גדול יותר זה לא מעניין אותנו. 2. אם הוא שווה בערכו למסלול המינימום הנוכחי, אז נשנה את הערך במערך unique של u להיות false (כי כעת יש שני מסלולי מינימום שונים).

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

סיבוכיות: כיון שהוספנו פעולה אחת קבועה לכל בדיקת אורך מסלול באלגוריתם דייקסטרה, אז לא שינינו את הסיבוכיות הכוללת של האלגוריתם. לכן זה יוצא $O((|V|+|E|)log(|V|))$ .

ג'

האלגוריתם יהיה וריאציה על אלגוריתם דייקסטרה. בנוסף על מערך המרחקים הקצרים ביותר, נחזיק את מס' הצמתים שמכיל כל מסלול כזה. המערך של מס' הצמתים יאותחל בהתחלה ל-0 (כי מסלול באורך אינסוף מכיל 0 צמתים) לכל הצמתים u, מלבד הצומת s, שעבורו הערך 1.

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

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

סיבוכיות: הוספנו פעולה קבועה לכל השוואה, לכן זמן הריצה נשמר והוא $O((|V|+|E|)log(|V|))$

3

מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/הדפסה יפה/תשובה

4

א'

מכיוון שהקיבולת של כל הקשתות הנכנסות לבור (t) היא 4, ברור ממשפט החתך המינימלי/זרימה מקסימלית שזרימה של 5 אינה אפשרית.

ב'

את השאלה הזו ניתן לפתור בקלות ע"י שימוש המסטר: $a=2,b=8,p=\log _{b}{a}=\log _{8}{2}=1/3$, לכן נבקל ש- $f(n)=n^{1/3}=n^{p}$. מקרה ב' מתקיים ולכן הפתרון הוא $\Theta (n^{1/3}\log {n})$

ג'

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצים אדומים-שחורים/תרגילים/צביעה אפשרית לעץ לא-מאוזן/תשובה

ד'

את נוסחא זו ניתן לחסום מלמעלה ומלמטה: $2T(n/4)+5n\leq T(n/4)+T(n/3)+5n\leq 2T(n/3)+5n$. פתרון של כל אחת מהנוסחאות בנפרד (החסם התחתון והעליון) אפשרי ע"י משפט המסטר והוא $\Theta (n)$. לכן זה גם הפתרון של הנוסחא כולה.