Esercizio - domande di prima parte su greedy e Huffman (simulazioni d'esame)

---

Domanda 1: attività selezionate e sottoistanza residua

Testo. Si consideri un insieme di $6$ attività $a_i$, $1 \le i \le 6$, caratterizzate dai seguenti vettori $s$ e $f$ di tempi di inizio e fine: $$s = (2, 1, 2, 3, 5, 7), \qquad f = (3, 5, 6, 6, 7, 8).$$ Si determini l'indice della prima attività della sottoistanza residua ottenuta dopo la prima scelta greedy e il relativo clean-up.

Soluzione. Le attività sono già ordinate per fine non decrescente ($3 \le 5 \le 6 \le 6 \le 7 \le 8$), come richiede l'algoritmo (Paradigma greedy - scelta golosa, sottostruttura e selezione delle attivitàIl paradigma greedy compie subito una scelta localmente migliore (scelta greedy), pulisce l'istanza (clean-up) e risolve l'unica sottoistanza residua, con ricorsione di coda eliminabile; il codice è facile, la correttezza no e richiede due proprietà, la scelta greedy (esiste un ottimo che la contiene) e la sottostruttura ottima (cut-and-paste), da cui la correttezza segue per induzione. Caso di studio: la selezione delle attività, con l'algoritmo del primo che finisce, correttezza completa, complessità Theta(n) dopo l'ordinamento e controesempi per le scelte greedy sbagliate.Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività →). Gli intervalli sono $a_1 = [2,3)$, $a_2 = [1,5)$, $a_3 = [2,6)$, $a_4 = [3,6)$, $a_5 = [5,7)$, $a_6 = [7,8)$.

1. Scelta greedy: la prima attività dell'ordine, $a_1 = [2, 3)$, con $f_1 = 3$.
2. Clean-up: si eliminano, a partire da $a_2$, le attività incompatibili con $a_1$, cioè quelle con $s_j < f_1 = 3$:
   • $a_2 = [1, 5)$: $s_2 = 1 < 3$, eliminata;
   • $a_3 = [2, 6)$: $s_3 = 2 < 3$, eliminata;
   • $a_4 = [3, 6)$: $s_4 = 3 \ge 3$, compatibile (gli intervalli sono chiusi a sinistra e aperti a destra: $a_1$ finisce in $3$ e $a_4$ inizia in $3$), ci si ferma.
3. La sottoistanza residua è il suffisso $a_4, a_5, a_6$ e la sua prima attività è $a_4$.

Risposta: 4.

Nota sulla soluzione scritta a mano: la verifica usa $s_3 \ge f_1$ al posto di $s_4 \ge f_1$ per l'ultima riga: è una svista di scrittura, la disuguaglianza da controllare è quella di $a_4$ (con $s_3 = 2$ sarebbe falsa).

Per completare: proseguendo l'algoritmo si sceglie $a_4$ (con $f_4 = 6$), poi si scartano $a_5$ ($5 < 6$) e si sceglie $a_6$ ($7 \ge 6$): soluzione $\{a_1, a_4, a_6\}$, 3 attività, ottima (verificato con la forza bruta).

Domanda 2: estrazioni del minimo in HUFFMAN

Testo. Il numero complessivo di estrazioni del minimo sulla coda di priorità $Q$ effettuate dall'algoritmo HUFFMAN su un alfabeto di $n = 13$ caratteri è:

Soluzione. Si conta nel codice (Codifica di Huffman - codici prefissi, algoritmo e ottimalitàCompressione con codifica per carattere: la lunghezza variabile risparmia bit ma deve essere iniettiva, e i codici prefissi lo garantiscono; un codice prefisso è un trie binario con una foglia per carattere, di costo B(T) = somma di f(c) d_T(c), e quello ottimo è un albero pieno con n-1 nodi interni. L'algoritmo di Huffman fonde ripetutamente i due alberi di frequenza minima usando una coda con priorità (2n-1 estrazioni, costo O(n log n)); l'ottimalità si prova con la scelta greedy (i due caratteri più rari sono foglie sorelle di profondità massima, per scambio) e la sottostruttura (B(T) = B(T') + f(x) + f(y)). Esempio completo con 6 caratteri, B = 2,24.Codifica di Huffman - codici prefissi, algoritmo e ottimalità →):

1. Il ciclo for i <- 1 to n-1 ha $n - 1 = 12$ iterazioni, una per ogni nodo interno del trie (un albero pieno con $13$ foglie ha $12$ nodi interni); ciascuna esegue 2 extractmin: $2 \cdot 12 = 24$.
2. L'istruzione finale return Q.extractmin() ne esegue 1, per estrarre la radice.

Totale: $24 + 1 = 25 = 2n - 1$.

Risposta: 25.

Ne segue anche che le insert sono $n + (n - 1) = 2n - 1 = 25$ (13 iniziali e 12 nel ciclo).

---

Varianti per allenarsi

Stesso tipo di domanda, con dati nuovi (risposte controllate con Python).

1. Attività con $s = (1, 2, 4, 6, 5, 8)$ e $f = (3, 5, 7, 8, 9, 10)$ (già ordinate per fine). Quante attività sceglie l'algoritmo e quale è la prima della residua dopo $a_1$? Esecuzione: $a_1 = [1,3)$; $a_2$ ($2 < 3$) scartata; $a_3 = [4,7)$ ($4 \ge 3$) scelta; $a_4$ ($6 < 7$) e $a_5$ ($5 < 7$) scartate; $a_6 = [8,10)$ ($8 \ge 7$) scelta. Sono 3 attività, $\{a_1, a_3, a_6\}$, ed è il massimo; la prima della residua dopo $a_1$ è $a_3$, indice 3.
2. Huffman con $n = 13$: quante inserzioni in $Q$? $13 + 12 = 25$. Quanti nodi ha il trie finale? $13$ foglie e $12$ interni, 25 nodi.
3. Huffman con $n$ generico: quante iterazioni del ciclo, quante estrazioni? $n - 1$ iterazioni e $2n - 1$ estrazioni.
4. Codifica di Huffman per $a\,45$, $b\,13$, $c\,12$, $d\,16$, $e\,9$, $f\,5$ (percentuali): costo medio. $2{,}24$ bit per carattere (somma dei nodi interni $14 + 25 + 30 + 55 + 100 = 224$ centesimi).