שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2018

השאלה עוסקת בדחיסת טקסט.

נתון א"ב

Σ = {a_{1}, a_{2}, \dots, a_{n}}

ומשקלים

W = {w_{1}, w_{2}, \dots, w_{n}}

כאשר המשקל של

a_{i}

הוא

w_{i}

. המשקלים מקיימים

w_{1} > w_{2} > \dots > w_{n}

. נגדיר את הקידוד הבא:

תו	קידוד
$a_{1}$	0
$a_{2}$	10
$a_{3}$	110
$a_{4}$	1110
...	...
$a_{n - 1}$	$n - 1 111 \dots 1 0$
$a_{n}$	$n - 1 111 \dots 1 1$

נקרא לקידוד כזה "קידוד מונוטוני".

א. עבור הא"ב

Σ = {a_{1}, a_{2}, a_{3}, a_{4}}

תנו דוגמה למשקלים

w_{1} > w_{2} > w_{3} > w_{4}

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

ב. עבור הא"ב

Σ = {a_{1}, a_{2}, a_{3}, a_{4}}

תנו דוגמה למשקלים

w_{1} > w_{2} > w_{3} > w_{4}

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א2018סמסטר א

★★★★★

קידודקידוד האפמן

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

שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2018 - קידוד