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

הנחיות

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

1

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.

דוגמה:

2

נתון גרף מכוון $\displaystyle G=(V,E)$ , צומת $\displaystyle s\in V$ ,וטבלת מחירים חיוביים לקשתות $\displaystyle E$ . בשאלה זו אנו מתעניינים במסלול הזול ביותר מ-s לכל צומת $\displaystyle u\in V$ .

א'

אנא הראי מקרה שבו קיים צומת $\displaystyle u\in V$ , כך שאין מסלול יחיד זול ביותר מ $\displaystyle S$ ל $\displaystyle V$ .

ב'

אנא מצאי אלגוריתם יעיל המקבל את הגרף, צומת המוצא, וטבלת העלויות, ומחזיר מערך בוליאני Unique. Unique[u] יכיל את הערך True אמ"ם יש מסלול יחידי מ $\displaystyle s$ ל $\displaystyle u$ . אנא הוכיחי את נכונות האלגוריתם ונתחי סיבוכיותו.

ג'

אנא מצאי אלגוריתם יעיל המקבל את הגרף, צומת המוצא, וטבלת העלויות, ומחזיר מערך Shortest-Cheapest. ּShortest-Cheapest[u] יכיל את מספר הצמתים במסלול הקצר ביותר מבין המסלולים הזולים ביותר מ $\displaystyle s$ ל $\displaystyle u$ . אנא הוכיח את נכונות האלגוריתם ונתחי סיבוכיותו.

3

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

ברצוננו להדפיס פסקת טקסט בצורה יפה.

נתונות לנו $\displaystyle n$ מילים, Word[1], Word[2], ..., Word[n]. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:

בכל שורת טקסט יש מקום ל $\displaystyle M$ תווים (אין מילה בעלת יותר מ $\displaystyle M$ תווים).
יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.

דוגמה:

נניח ש $\displaystyle M=20$ , והמילים הן

If they have no rice, let them eat ladoo.

נוכל לבנות פסקה כך:

If they have no

rice, let them

eat ladoo.

אך לא כך:

If they have no rice, let them eat

ladoo.

(בדוגמה השניה יש יותר מ20 תווים בשורה הראשונה).

אם בשורה יש $\displaystyle m'$ תווים (כולל הרווחים בין המילים), אז יופי השורה הוא $\displaystyle {\frac {1}{(M-m'+1)^{2}}}$ . יופי הפסקה מוגדר כסכום היופי של השורות שלו, למעט השורה האחרונה.

דוגמה:

בפסקה

If they have no

rice, let them

eat ladoo.

יש 15 תווים בשורה הראשונה, ו14 תווים בשורה השניה. יופי הפסקה, לכן הוא $\displaystyle {\frac {1}{(20-15+1)^{2}}}+{\frac {1}{(20-14+1)^{2}}}={\frac {1}{6^{2}}}+{\frac {1}{7^{2}}}$ .

אנא מצא אלגוריתם יעיל למציאת הפסקה היפה ביותר. הנח ש $\displaystyle n$ הוא משתנה גלובלי נתון, ושקיימת פונקציה Length המקבלת מספר $\displaystyle i$ ומחזירה את מספר התווים במילה ה $\displaystyle i$ .