חזרה על מושגי מפתח

בשיעור הזה נעבור על מושגי המפתח שנלמדו בקורס תכנות דינמי 101.

1. תכנות דינמי: תכנות דינמי הוא טכניקה לפתרון בעיות אופטימיזציה באמצעות פירוק שלהן לתת־בעיות פשוטות יותר ופתרון של כל תת־בעיה פעם אחת בלבד.
2. ממואיזציה: ממואיזציה היא טכניקה למניעת חישובים מיותרים באמצעות שמירת התוצאות של קריאות יקרות לפונקציות והחזרת התוצאה השמורה במטמון כאשר אותן קלטים מופיעים שוב.
3. מילוי טבלה: מילוי טבלה הוא טכניקה לפתרון בעיות של תכנות דינמי באמצעות מילוי איטרטיבי של טבלה או מערך של פתרונות, עד לקבלת הפתרון הסופי.
4. תת־מבנה אופטימלי: בעיה מציגה תת־מבנה אופטימלי אם הפתרון האופטימלי לבעיה מכיל בתוכו פתרונות אופטימליים לתת־הבעיות שלה.
5. תת־בעיות חופפות: בעיה מציגה תת־בעיות חופפות אם ניתן לפרק אותה לתת־בעיות שחולקות תת־תת־בעיות.
6. אופטימיזציית זיכרון: אופטימיזציית זיכרון היא טכניקה להפחתת דרישות הזיכרון של אלגוריתם תכנות דינמי באמצעות מעקב רק אחר המצב הנחוץ.
7. מסכת סיביות: מסכת סיביות היא טכניקה לייצוג קבוצת איברים כמספר בינארי באמצעות פעולות על סיביות.
8. גיזום: גיזום הוא טכניקה להפחתת מספר החישובים הנדרשים באלגוריתם תכנות דינמי באמצעות הימנעות מחישובים מיותרים.