יסודות מדעי המחשב — מרחב למידה אישי

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

הליבה: אופטימיזציה של רקורסיה

תכנות דינמי (Dynamic Programming - DP) ומימוניזציה (Memoization) הן טכניקות חזקות המשמשות לאופטימיזציה של אלגוריתמים רקורסיביים. הרעיון המרכזי הוא להימנע מחישוב חוזר של אותה תת-בעיה מספר פעמים, על ידי שמירת תוצאות הביניים. זהו הבסיס לפתרון יעיל של בעיות רבות במדעי המחשב.

תתי-בעיות חופפות ותת-מבנה אופטימלי

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

תתי-בעיות חופפות (Overlapping Subproblems): בעיה בעלת תתי-בעיות חופפות היא כזו שבה אותו חישוב של תת-בעיה חוזר על עצמו פעמים רבות במהלך הפתרון הרקורסיבי. לדוגמה, בחישוב מספרי פיבונאצ'י, F(5) דורש את F(4) ו-F(3), ו-F(4) דורש את F(3) ו-F(2). F(3) מחושב פעמיים.

תת-מבנה אופטימלי (Optimal Substructure): בעיה בעלת תת-מבנה אופטימלי היא כזו שבה הפתרון האופטימלי לבעיה המקורית יכול להיבנות מפתרונות אופטימליים של תתי-הבעיות שלה. לדוגמה, המסלול הקצר ביותר מ-A ל-C העובר דרך B, מורכב מהמסלול הקצר ביותר מ-A ל-B ומהמסלול הקצר ביותר מ-B ל-C.

גישות ליישום: מימוניזציה מול טבולציה

קיימות שתי גישות עיקריות ליישום תכנות דינמי, הנבדלות באופן שבו הן בונות את הפתרון:

מימוניזציה (Memoization) - מלמעלה-למטה (Top-Down)

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

טבולציה (Tabulation) - מלמטה-למעלה (Bottom-Up)

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

דוגמאות קלאסיות ויישומים

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

מספרי פיבונאצ'י: הדוגמה הקלאסית ביותר להדגמת תתי-בעיות חופפות.
כפל שרשרת מטריצות (Matrix Chain Multiplication): מציאת הסדר האופטימלי לכפל סדרת מטריצות כדי למזער את מספר הפעולות. בעיה זו מדגימה היטב את תת-המבנה האופטימלי.
בעיית התרמיל (Knapsack Problem): בחירת פריטים בעלי משקל וערך נתונים, כך שסך המשקל לא יעלה על קיבולת התרמיל וסך הערך יהיה מקסימלי.
תת-רצף משותף ארוך ביותר (Longest Common Subsequence - LCS): מציאת התת-רצף הארוך ביותר המשותף לשתי רצפות נתונות.

זיהוי וניסוח בעיות DP: בחינות בבן-גוריון נוטות לבחון את יכולתכם לזהות בעיות המתאימות לתכנות דינמי, לנסח את יחס הנסיגה (recurrence relation) שלהן, להגדיר את מקרי הבסיס, ולתאר את האלגוריתם (בין אם בגישת מימוניזציה או טבולציה). חשוב מאוד לתרגל את השלבים הללו ולנתח את סיבוכיות הזמן והמקום של הפתרונות. הבנה עמוקה של אופן הגדרת "מצב" (state) בטבלת ה-DP היא קריטית.

שאלות לדיון

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

נקודות לתשובת מודל

יעילות פיבונאצ'י: רקורסיה ללא מימוניזציה מחשבת שוב ושוב את אותם ערכים (לדוגמה, F(3) מחושב גם עבור F(5) וגם עבור F(4)). מימוניזציה שומרת את התוצאה בטבלה לאחר החישוב הראשון, ובקריאות הבאות פשוט שולפת אותה, מה שמפחית את הסיבוכיות האקספוננציאלית ללינארית.
זיהוי בעיות DP: דוגמאות אפשריות: בעיית שינוי מטבעות (Coin Change), בעיית הדרך הקצרה ביותר ברשת (Shortest Path in DAG), עריכת מרחק (Edit Distance). ההסבר צריך לפרט את תתי-הבעיות החופפות (למשל, חישוב שינוי עבור סכום מסוים חוזר על עצמו) ואת תת-המבנה האופטימלי (הפתרון האופטימלי לסכום גדול מבוסס על פתרונות אופטימליים לסכומים קטנים יותר).
השוואת מימוניזציה וטבולציה:
- מימוניזציה (Top-Down): יתרונות - קל יותר לכתוב, עוקב אחר ההיגיון הרקורסיבי, מחשב רק את תתי-הבעיות הנחוצות. חסרונות - תקורה של קריאות רקורסיביות, שימוש במחסנית (stack).
- טבולציה (Bottom-Up): יתרונות - לרוב יעילה יותר בזמן ריצה (ללא תקורה רקורסיבית), ללא סכנת גלישת מחסנית, קל יותר לייעל את השימוש במקום. חסרונות - לעיתים פחות אינטואיטיבית לניסוח, מחשבת את כל תתי-הבעיות (גם אם לא כולן נחוצות).
- בחירה: מימוניזציה מועדפת כאשר רק חלק קטן מתתי-הבעיות נחוץ, או כשהניסוח הרקורסיבי מורכב. טבולציה מועדפת כאשר כל תתי-הבעיות נחוצות, או כאשר יש צורך בביצועים אופטימליים וחיסכון במקום.
ניתוח סיבוכיות:
- סיבוכיות זמן: נגזרת ממספר המצבים (states) בטבלת ה-DP כפול הזמן שלוקח לחשב כל מצב (לרוב קבוע או תלוי במספר קטן של מצבים קודמים).
- סיבוכיות מקום: נגזרת מגודל טבלת ה-DP, כלומר מספר המצבים שיש לשמור. לעיתים ניתן לייעל את המקום על ידי שמירת רק את המצבים הנחוצים לחישוב המצב הנוכחי (לדוגמה, רק השורה הקודמת בטבלה דו-ממדית).

מצאתם טעות או שחסר משהו?