Question

dynamic_programming

summer_18_b

נתונים $n$ מספרים ממשיים, $a_1, \ldots, a_n$ , רוצים ליצור מהם ביטוי חשבוני על ידי הוספת פעולות כפל וחיבור בין כל שני מספרים עוקבים,כך שערך הביטוי שיתקבל יהיה מקסימלי.

הערות:

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

א. השלימו את הקלט הבא עם פעולות חיבור וכפל כך שערך הביטוי שמתקבל מקסימלי.

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 0.1 & \quad & -2 & \quad & 3 & \quad & 2 & = &\quad \\\hline \end{array}

ב. הוצע לחשב את ערך הביטוי על ידי נוסחת הנסיגה הבאה:

f(i) = \max \begin{cases} a_i + f(i + 1) \\ a_i \cdot f(i + 1) \end{cases}

כאשר $f(i)$ הוא ערך הביטוי עבור הקלט $a_i, \ldots, a_n$ ו- $f(n) = a_n$ .

הראו שנוסחה זו אינה מחשבת בהכרח את ערך הביטוי המקסימלי.

ג. תארו אלגוריתם פולינומי שבהינתן $n$ מספרים ממשיים כלשהם, $a_1, \ldots, a_n$ , מוסיף פעולות כפל וחיבור בין כל שני מספרים עוקבים,כך שערך הביטוי שמתקבל יהיה מקסימלי.יש לנתח סיבוכיות זמן ריצה אבל אין צורך להוכיח נכונות.

Answers

א.

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 0.1 & \times & -2 & + & 3 & \times & 2 & = & 5.8 \\\hline \end{array}

ב. למשל עבור הקלט $5,-1,5$ ערך נוסחת הנסיגה הוא 20 בעוד שערך הפתרון האופטימלי הוא 9.

ג. נשים לב שאם קיימת פעולת חיבור במקום ה- $i$ אז אנחנו מעוניינים למקסם את הביטויים משמאל ומימין לפעולה. מצד שני יכול להיות שערך הביטוי המקסימלי מתקבל מפעולות כפל בלבד, כלומר אם נסמן ב- $f(i,j)$ את ערך הביטוי המקסימלי עבור המספרים $a_i, \dots, a_j$ אז מתקיים ש:

f(i, j) = \max \begin{cases} \displaystyle{\max_{i \leq k < j} f(i,k) + f(k + 1, j)} \\\\ \displaystyle{\prod_{i \leq k \leq j} a_k} \end{cases}

כאשר $f(i,i) = a_i$ .

את הנוסחה הנ"ל אפשר לחשב במטריצה בגודל $n \times n$ לפי סדר האלכסונים.

סיבוכיות: אנחנו מחשבים $O(n^2)$ ערכים כאשר חישוב של כל ערך לוקח $O(n)$ זמן ולכן בסך הכל $O(n^3)$ זמן.