Approximation for dynamic optimization

הרקע לפרויקט:

1. תכנות דינאמי - Dynamic Programming הינו כלי רב עוצמה למידול בעיות אופטימיזציה דינאמיות. הוא כלי כל כך חזק עד שניתן באמצעותו למדל בעיות קשות - NP -Hard שלא סביר שניתן לפתור בזמן פולינומיאלי בגודל הקלט.
2. סכמות קרוב פולינומיאליות לחלוטין - Fully Polynomial Time Approximation Schemes (FPTASes) נחשבים הטובים ביותר מבין אלגוריתמי הקרוב. בסוג זה של אלגוריתמים ניתן בנוסף לקלט הבעיה גם פרמטר קרוב E>0<1 והאלגוריתם מחזיר פתרון אפשרי (פיסיבילי) שערכו קרוב עד כדי טעות יחסית של E מהאופטימום. זמן הריצה של האלגוריתם הנו פולינומי בגודל קלט הבעיה וב- 1/E. כלומר, ניתן להתקרב ככל הנדרש לפתרון האופטימאלי כאשר הגידול בזמן ריצת אלגוריתם הקרוב הנו פונקציה פולינאמית של 1/E. זהו סוג אלגוריתמי הקרוב עם הפוטנציאל הגבוה ביותר לשימוש מסחרי/הנדסי מבין כל אלגוריתמי הקרוב.
3. ישנן מספר שיטות לקרוב תכניות דינאמית באמצעות FPTASes, החדשנית מבניהן פותחה על ידי מנחה הפרוייקט, והיא נקראת K-approximation Sets and Functions

בפרוייקט זה יש לנסח בעיות אופטימזציה דינאמיות באמצעות תכנות דינאמי באופן שניתן יהיה לתת להם סכמות קרוב פולינאמיות לחלוטין באמצעות שיטת K-approximation Sets and Functions.

מטרת הפרויקט:

ניסוח בעיות אופטימזציה דינאמיות באמצעות תכנות דינאמי ומציאת סכמות קרוב פולינאמיות לחלוטין עבורן.

תכולת הפרויקט:

1. שליטה במידול בעיות אופטימיזציה דינאמית באמצעות תכנות דינאמי.
2. הבנה של אלגוריתמים מסוג FPTASes ושיטת עיקריות להשגתם.
3. שליטה בטכניקת K-approximation Sets and Functions והשגת סכמות קרוב פולינאמיות לחלוטין באמצעותה.

קורסי קדם:

83503 - מודלים דטרמינסטיים בחקר ביצועים
83119 - מבני נתונים ואלגוריתמים 1

דרישות נוספות:

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

מקורות:

היות ושיטת K--approximation Sets and Functions הינה חדשנית, אין עדיין ספר לימוד אודותיה. לכן ינתנו כדוגמא מאמרים שעשו בה שימוש. דוגמא לאחד כזה הוא המאמר בקישור הבא:

https://doi.org/10.1016/j.ipl.2021.106114