Data Structures – Recitation 10

Shay Golan

and Matan Kraus

1

תכנון (/תכנות) דינמי�Dynamic Programming

2

הקדמה

• פרדיגמה - פָּרָדִיגְמָה היא תבנית מחשבה במסגרת של תחום מדעי או בהקשר אפיסטמולוגי דומה.
• בתכנון אלגוריתמים, פרדיגמה היא דרך, שיטה מסוימת שמתארת הרבה אלגוריתמים שונים, ויכולה להיות שימושית לפתרון בעיות רבות.

​

• נדבר הקורס על שתי פרדיגמות בתכנון אלגוריתמים:
• הפרד ומשול
• תכנות דינמי
• אלגו' חמדניים – תלמדו בע"ה באלגוריתמים 1.

​

3

לאיזה בעיות נשתמש בתכנון דינמי?

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

4

תכנון דינמי

• במקום לחשב מחדש כל פעם את הקריאות הרקורסיביות נחשב את הפונקציה על כל קלט פעם אחת בלבד.
• שתי צורות חישוב סטנדרטיות:
• בחישוב "מלמעלה למטה" - בשיטת התזכור (Memo[r]ization)
• בחישוב "מלמטה למעלה".

5

סד"פ תכנון דינמי

6

בעיית תרמיל הגב בשלמים

7

שעת סיפור

8

בעיית תרמיל הגב

9

10

פתרון נאיבי

11

נסיון פתרון (כושל)

• ניקח כל פעם את החפץ ששוה הכי הרבה כסף לק"ג חומר.
• לא עובד. דוגמה נגדית – תיק שיכול לסחוב עד 100 ק"ג ושני חפצים:
• אחד שוקל 51 ק"ג ושווה 51 ש"ח.
• השני שוקל 100 קילו ושווה 70 ש"ח.
• האלגוריתם ייקח את החפץ ששוקל 51 ק"ג, ויסיים עם 51 ש"ח, כשניתן להרוויח 70 ש"ח.

12

פתרון רקורסיבי

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

13

פתרון רקורסיבי

14

פתרון רקורסיבי

15

פתרון רקורסיבי

16

הוכחת הנוסחה הרקורסיבית

17

הוכחה

18

הוכחה

19

הוכחה

20

ה"ה

הוכחה

21

ה"ה

זמן ריצה

22

מימוש יעיל – תכנון דינמי

23

מימוש יעיל – תכנון דינמי

24

שחזור

25

סיבוכיות מקום

26

הערה על פסאודו פולינומיות

27

בעץMIS בעיית

MIS=Maximum Independent Set

קבוצה בלתי תלויה גדולה ביותר

28

שעת סיפור 2

29

4

3

3

4

1

5

2

4

2

1

בעיית המסיבה (MIS בעץ)

30

4

3

3

4

1

5

2

4

2

1

2+4+5+2+3+4=20

פתרון נאיבי

31

פתרון רקורסיבי

32

פתרון רקורסיבי

33

פתרון רקורסיבי

34

זמן ריצה

35