Vai al contenuto principale
← OlimpiApp Olimpico

Informatica · Greedy

Risparmio in bit di un codice ottimo su lunghezza fissa

Un alfabeto ha 7 simboli con le seguenti frequenze assolute di utilizzo: 4, 7, 12, 15, 19, 26, 31. 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 i 7 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.