שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2026 - אלגוריתמים חמדניים

שאלה 2: נתונה מחרוזת $S$ מעל האלפבית $\Sigma = \{a_1, a_2, \dots, a_n\}$ נסמן ב-$f_i$ את שכיחות הופעתה של האות $a_i$ במחרוזת $S$. סעיף א': (5 נקודות) נניח כי $n \ge 2$ היא חזקה של 2. הראו כי קיימת בחירה של שכיחויות לאותיות כך שהעץ המתאים לקוד התחיליות האופטימלי הוא עץ בינארי שלם, כלומר כל העלים בעץ באותו עומק. סעיף ב': (5 נקודות) נניח כי מספר האותיות הוא $n = 7$. להלן נתון מבנה של עץ בינארי מלא: [איור של עץ הושמט] הציעו רשימת שכיחויות $f_1, \dots, f_7$ עבור האותיות כך שעץ זה יכול להיות העץ המייצג קוד תחיליות אופטימלי עבור שכיחויות אלו. נמקו בקצרה את בחירתכם. כתבו את השכיחויות על העץ עצמו. סעיף ג': (15 נקודות) הוכיחו כי לכל עץ בינארי מלא עם $n$ עלים קיימת רשימת שכיחויות שעבורה $T$ הוא עץ קוד תחיליות אופטימלי.

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

פתרון: ### סעיף א' כדי להראות שקיים קוד תחיליות אופטימלי המיוצג על ידי עץ בינארי שלם, עלינו למצוא קבוצת שכיחויות $f_1, obreak\dots, f_n$ שעבורה **אלגוריתם הופמן** יבנה עץ כזה. עץ בינארי שלם הוא עץ שבו כל העלים נמצאים באותו עומק. נניח ש-$n = 2^k$ עבור $k obreak\ge 1$ שלם. נבחר שכיחויות זהות לכל האותיות, למשל, $f_i = 1$ לכל $i = 1, obreak\dots, n$. ננתח את פעולת אלגוריתם הופמן על שכיחויות אלו: 1. **שלב ראשון:** בתור העדיפויות יש $n = 2^k$ עלים, כולם עם משקל 1. האלגוריתם יבחר שני עלים כלשהם, ימזג אותם לצומת פנימי חדש עם משקל $1+1=2$, ויכניס את הצומת החדש לתור. לאחר $\frac{n}{2} = 2^{k-1}$ מיזוגים כאלה, תור העדיפויות יכיל $2^{k-1}$ צמתים, כולם עם משקל 2. כל צומת כזה הוא שורש של עץ שגובהו 1. 2. **שלב שני:** כעת, כל הצמתים בתור הם בעלי המשקל המינימלי (והיחיד) - 2. האלגוריתם יבצע $2^{k-2}$ מיזוגים של זוגות צמתים במשקל 2, וייצור $2^{k-2}$ צמתים חדשים במשקל $2+2=4$. כל צומת חדש כזה הוא שורש של עץ שגובהו 2. 3. **המשך התהליך:** התהליך ימשיך באופן דומה. בכל שלב $j$ (כאשר $1 \le j \le k$), האלגוריתם ימזג זוגות של צמתים שכולם בעלי משקל $2^{j-1}$, וייצור צמתים חדשים במשקל $2^j$. לאחר $k$ שלבים כאלה, כל העלים המקוריים יאוחדו תחת עץ אחד. מכיוון שבכל שלב מיזגנו עצים מאותו גובה, העץ הסופי יהיה עץ בינארי שלם. כל $n=2^k$ העלים יהיו בעומק $k$. לדוגמה, עבור $n=4=2^2$, עם שכיחויות {1, 1, 1, 1}: - מיזוג 1 ו-1 נותן עץ עם שורש 2. נחזור על כך. נקבל שני עצים עם שורש 2. - מיזוג שני השורשים במשקל 2 נותן עץ עם שורש 4. העץ הסופי הוא עץ בינארי שלם שבו כל 4 העלים בעומק 2. לכן, קיימת בחירת שכיחויות (למשל, שכיחויות שוות) שעבורה העץ האופטימלי הוא עץ בינארי שלם. $\blacksquare$ ### סעיף ב' כדי שעץ נתון יהיה עץ קוד תחיליות אופטימלי (עץ הופמן) עבור סט שכיחויות מסוים, תנאי הכרחי ומספיק הוא ש**תכונת האחים** תתקיים: לכל צומת פנימי $u$, כל עלה בתת-העץ של $u$ חייב להיות בעל שכיחות קטנה או שווה לשכיחות של כל עלה שאינו נמצא בתת-העץ של $u$. דרך פשוטה יותר להבטיח זאת היא להקצות שכיחויות כך שעלים עמוקים יותר מקבלים שכיחויות נמוכות יותר. נניח שהעץ הנתון הוא בעל המבנה הבא (שמוצג באיור חסר): - עלים $f_1, f_2, f_3$ בעומק 3. - עלים $f_4, f_5$ בעומק 2. - עלים $f_6, f_7$ בעומק 2. על מנת שעץ זה יהיה אופטימלי, השכיחויות של העלים בעומק 3 צריכות להיות קטנות או שוות לשכיחויות של העלים בעומק 2. נבחר את השכיחויות הבאות כדי להדגים זאת: - לעלים בעומק 3: $f_1 = 1, f_2 = 1, f_3 = 2$. - לעלים בעומק 2: $f_4 = 3, f_5 = 4, f_6 = 5, f_7 = 5$. רשימת השכיחויות המלאה היא: $f_1=1, f_2=1, f_3=2, f_4=3, f_5=4, f_6=5, f_7=5$. **נימוק:** סדר השכיחויות מהקטן לגדול הוא {1, 1, 2, 3, 4, 5, 5}. סדר העומקים של העלים מהגדול לקטן הוא {3, 3, 3, 2, 2, 2, 2}. מכיוון שהעלים עם השכיחויות הקטנות ביותר נמצאים בעומקים הגדולים ביותר, תכונת האופטימליות של קוד הופמן נשמרת. אלגוריתם הופמן, כאשר יופעל על שכיחויות אלו, יבצע מיזוגים באופן הבא (אחת האפשרויות): 1. מיזוג {1, 1} $\to$ צומת במשקל 2. 2. מיזוג {2, 2} $\to$ צומת במשקל 4 (הצומת הקודם והעלה 2). 3. מיזוג {3, 4} $\to$ צומת במשקל 7. 4. מיזוג {5, 5} $\to$ צומת במשקל 10. 5. מיזוג {4, 7} $\to$ צומת במשקל 11. 6. מיזוג {10, 11} $\to$ שורש במשקל 21. ניתן לבדוק שמבנה זה תואם את המבנה שהנחנו, ולכן השכיחויות שהצענו תקפות. ### סעיף ג' **טענה:** לכל עץ בינארי מלא $T$ עם $n$ עלים, קיימת רשימת שכיחויות $f_1, obreak\dots, f_n$ שעבורה $T$ הוא עץ קוד תחיליות אופטימלי. **הוכחה באינדוקציה על מספר העלים $n$:** **בסיס האינדוקציה:** עבור $n=2$, כל עץ בינארי מלא הוא שורש עם שני ילדים-עלים. עץ זה הוא עץ הופמן עבור כל שתי שכיחויות, למשל $f_1=1, f_2=1$. הטענה נכונה. **הנחת האינדוקציה:** נניח שהטענה נכונה לכל עץ בינארי מלא עם $k<n$ עלים. **צעד האינדוקציה:** יהי $T$ עץ בינארי מלא כלשהו עם $n$ עלים. מכיוון ש-$T$ מלא, קיים בו לפחות צומת פנימי אחד ששני ילדיו הם עלים (אחרת, היינו יכולים לרדת בעץ עד אינסוף). נבחר זוג אחים-עלים כזה, $u$ ו-$v$, שיהיו בעומק המרבי בעץ $T$. נסמן את אביהם המשותף ב-$p$. כעת, נבנה עץ חדש $T'$ מ-$T$ על ידי הסרת העלים $u$ ו-$v$ והפיכת אביהם $p$ לעלה. העץ $T'$ הוא עץ בינארי מלא עם $n-1$ עלים. לפי הנחת האינדוקציה, קיימת עבור $T'$ רשימת שכיחויות, $f'_1, obreak\dots, f'_{n-1}$, שעבורה $T'$ הוא עץ הופמן אופטימלי. נסדר שכיחויות אלו בסדר עולה: $f'_{(1)} \le f'_{(2)} \le obreak\dots \le f'_{(n-1)}$. השכיחות של העלה $p$ ב-$T'$ היא אחת מהשכיחויות ברשימה זו, נסמנה $f'_p$. כעת נבנה רשימת שכיחויות $F = \{f_1, obreak\dots, f_n\}$ עבור העץ המקורי $T$. נבחר שתי שכיחויות חדשות $f_u, f_v > 0$ כך שיתקיים $f_u + f_v = f'_p$. את שאר השכיחויות ב-$F$ ניקח מהרשימה $F' \setminus \{f'_p\}$. כך שבסך הכל $F = (F' \setminus \{f'_p\}) \cup \{f_u, f_v\}$. כדי להבטיח שהעץ $T$ יהיה עץ הופמן עבור השכיחויות $F$, עלינו לבחור את $f_u, f_v$ כך שיהיו שתי השכיחויות הקטנות ביותר ברשימה $F$. זה יבטיח שהצעד הראשון של אלגוריתם הופמן יהיה מיזוג של $u$ ו-$v$. לאחר המיזוג, נקבל צומת חדש $p$ עם משקל $f_u+f_v = f'_p$, ושאר השכיחויות הן בדיוק $F' \setminus \{f'_p\}$. זו בדיוק הבעיה המוקטנת שעבורה $T'$ הוא פתרון אופטימלי. נבחר למשל $f_u = \frac{f'_{(1)}}{2}$ ו-$f_v = \frac{f'_{(1)}}{2}$. רשימת השכיחויות החדשה תהיה $F = (F' \setminus \{f'_{(1)}\}) \cup \{\frac{f'_{(1)}}{2}, \frac{f'_{(1)}}{2}\}$. מכיוון שכל השכיחויות ב-$F'$ חיוביות, $f_u$ ו-$f_v$ הן אכן שתי השכיחויות הקטנות ביותר ב-$F$. הצעד הראשון של אלגוריתם הופמן על $F$ ימזג את $f_u, f_v$ לצומת במשקל $f'_{(1)}$. הבעיה שנותרה היא בדיוק הפעלת האלגוריתם על $F'$, שעבורה $T'$ הוא הפתרון האופטימלי לפי הנחת האינדוקציה. לכן, בנינו רשימת שכיחויות $F$ שעבורה העץ $T$ הוא עץ קוד תחיליות אופטימלי. מכוח האינדוקציה, הטענה נכונה לכל $n$. $\blacksquare$