Vai al contenuto principale
← OlimpiApp Olimpico

Informatica · Greedy

Quanti bit risparmia un codice ottimo su lunghezza fissa

Un alfabeto ha 8 simboli con le seguenti frequenze assolute di utilizzo: 5, 8, 10, 14, 20, 28, 36, 44. Si vuole assegnare a ciascun simbolo un codice binario prefix-free (nessun codice è prefisso di un altro) che renda minima la lunghezza totale del messaggio codificato (somma, per ogni simbolo, di frequenza per lunghezza del suo codice); chiama $T$ questa lunghezza minima. Se invece si usasse un codice a lunghezza fissa, assegnando a tutti i simboli lo stesso numero di bit (il minimo sufficiente a distinguere gli 8 simboli), la lunghezza totale del messaggio sarebbe un'altra quantità $F$. Quanto vale $F - T$, cioè quanti bit si risparmiano usando il codice ottimo?

La tua risposta

Vanno bene sia 3,14 sia 3.14.