תכנות דינאמי

Question 1

מהם השלבים לפתרון בעיה באמצעות תכנון דינאמי?

Answer 1

Question 2

על איזה מבנה פועל אלגוריתם בלמן-שכבות?

מה האלגוריתם עושה?

Answer 2

Question 3

מהו אוסף תת הבעיות של אלגוריתם בלמן-שכבות?

מהי נוסחת הרקורסיה?

Answer 3

אוסף תת הבעיות:

עבור כל קודקוד v, נמצא את המסלול הקל ביותר מs (=קודקוד ההתחלה) לv.

נשים לב שעבור t (=קודקוד הסיום), זאת בדיוק הבעיה שאנו מנסים לפתור.

נוסחת הרקורסיה: בתמונה.

Question 4

מהו זמן הריצה של אלגוריתם בלמן-שכבות?

Answer 4

(O(E+V

Question 5

מהו מיון טופולוגי בגרף מכוון חסר מעגלים?

Answer 5

זהו מיון של קודקודי הגרף כך ש:

אם יש צלע מקודקוד u לקודקוד v, אזי ברשימת הקודקודים הממויינת, u יופיע לפני v.

Question 6

באיזה סוג אלגוריתם נשתמש כדי למצוא תת מחרוזת משותפת ארוכה ביותר (תמ”א) לשתי מחרוזות?

Answer 6

אלגוריתם דינאמי.

Question 7

מהו אוסף תתי הבעיות של בעיית תת מחרוזת משותפת ארוכה ביותר לשתי המחרוזות:

X = x₁, x₂, … , x_n

Y = y₁, y₂, … , y_m

?

Answer 7

Question 8

מהי נוסחת הרקורסיה של בעיית תת מחרוזת משותפת ארוכה ביותר לשתי המחרוזות:

X = x₁, x₂, … , x_n

Y = y₁, y₂, … , y_m

?

Answer 8

Question 9

איך נשחזר מהטבלה את הפתרון של בעיית תת מחרוזת משותפת ארוכה ביותר לשתי המחרוזות:

X = x1, x2, … , xn

Y = y1, y2, … , ym

?

Answer 9

Question 10

מהו זמן הריצה של האלגוריתם למציאת תת מחרוזת משותפת ארוכה ביותר לשתי המחרוזות:

X = x₁, x₂, … , x_n

Y = y₁, y₂, … , y_m

?

Answer 10

Question 11

איך נוכיח את נכונות האלגוריתם למציאת תת מחרוזת משותפת ארוכה ביותר לשתי המחרוזות:

X = x1, x2, … , xn

Y = y1, y2, … , ym

?

מהי טענת האינדוקציה?

מהו בסיס האינדוקציה?

מהו צעד האינדוקציה?

Answer 11

Question 12

בשאלה שבתמונה:

1. מה תהיה החלוקה לתתי בעיות?
2. מה תהיה נוסחת הרקורסיה.
3. איך נמלא את הטבלה ונחלץ ממנה את הפתרון?

Answer 12

Question 13

יהי גרף מכוון עם פונקציית משקל על הצלעות.

איך נמצא את הדרך עם המשקל הנמוך ביותר בין כל זוג קודקודים בגרף?

Answer 13

נשתמש באלגוריתם פלוייד-וורשל.

האלגוריתם מחזיר טבלה כך שבתא הi,j כתוב משקל המסלול הקל ביותר מi לj.

Question 14

מהו זמן הריצה של אלגוריתם פלוייד-וורשל?

Answer 14

O(|V|³)

Question 15

איך נמצא את המרחק המינימלי בין קודקוד v בגרף לכל שאר הקודקודים בגרף?

Answer 15

נשתמש באלגוריתם בלמן פורד או באלגוריתם דייקסטרה.

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

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

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

Question 16

מה זמן הריצה של בלמן-פורד?

Answer 16

O(|V||E|)

Question 17

מה זמן הריצה של דייקסטרה?

Answer 17

O(|E| + |V|log|V|)

Question 18

באיזה סוג בעיה נבחר להשתמש בפתרון דינאמי על פני פתרון חמדני?

Answer 18

אם, כדי לפתור את הבעיה, יש צורך בחשיבה קדימה, כי למשל בחירת הפתרון החמדני בהתחלה “תדפוק” את מוצלחות הפתרון בהמשך -

נשתמש בפתרון דינאמי.