Esercitazione greedy - tracce su CD, scheduling shortest-first e (2,1)-boxing

L'esercitazione ha lo scopo di mostrare che un approccio greedy spesso cattura la strategia risolutiva più naturale e umana, che per alcuni problemi è provatamente ottima, e che scrivere l'algoritmo è immediato mentre provare che è ottimo resta delicato anche per un caso semplicissimo. La teoria è in 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à → e, per il caso più importante, in 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à →.

Il metodo, in sei passi

1. Scelta greedy: la prima scelta, quella che sembra localmente migliore, fatta senza risolvere sottoistanze.
2. Clean-up e sottoistanza residua: cosa si elimina dopo la scelta; ciò che resta è una sottoistanza dello stesso problema.
3. Algoritmo: discende direttamente dai passi 1 e 2 (ricorsione di coda, quindi un ciclo). Si dà lo pseudocodice, si argomenta che l'uscita è ammissibile e si calcola la complessità.
4. Proprietà di scelta greedy: esiste una soluzione ottima che contiene la scelta greedy. Si parte da una soluzione ottima qualsiasi e, se non la contiene, la si modifica (scambio, cut-and-paste) senza peggiorare il costo, controllando che resti ammissibile.
5. Proprietà di sottostruttura ottima: la parte di un ottimo che resta dopo la scelta greedy è ottima per la residua. Si dimostra per assurdo: una residua migliore, composta con la scelta greedy, darebbe una soluzione migliore dell'ottimo.
6. Conclusione: per induzione sulla taglia (base: istanza vuota), l'algoritmo ritorna un ottimo.

Se non c'è clean-up (nessuna incompatibilità) la sottostruttura (passo 5) è quasi immediata: ogni soluzione della residua si può completare con la scelta greedy. È il caso di tutti e tre i problemi qui sotto; la sottostruttura più delicata è quella della selezione delle attività, dove il clean-up è limitato.

I tre problemi a confronto

Che cosa cambia da un problema all'altro

Tracce su CD. Il vincolo che l'ordine delle canzoni sia fisso rende la soluzione una frammentazione della stringa, e riempire il primo CD non può far perdere nulla: ogni altra frammentazione chiude il primo CD prima. La prova sposta le canzoni $c_{s+1}, \dots, c_g$ dal secondo al primo CD e verifica che il secondo non si svuota (altrimenti l'ottimo avrebbe un CD in più del necessario, assurdo). Il caso con canzoni riordinabili è il bin packing, che non è risolubile così.

Shortest-first. Il costo si scrive $T_{sum}^\pi = \sum_{j=1}^{n-1} (n-j)\, t_{\pi(j)}$: i primi job pesano di più, quindi va avanti il più breve. Qui si dimostra qualcosa di più forte della scelta greedy: ogni scheduling ottimo ha come primo job uno di durata minima (non solo "ne esiste uno"). La prova è per assurdo con scambio: se il primo job $J_r$ non è minimo e un job più breve $J_s$ ($t_s < t_r$) è in posizione $k > 1$, scambiandoli l'attesa di ciascuno dei job in posizione $2, \dots, k$ scende di $t_r - t_s$ e le altre non cambiano. Lo stesso criterio, per i processi di un sistema operativo, è in Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin →.

(2,1)-boxing. Si parte dall'oggetto più difficile da sistemare, il più pesante. La scelta è "azzardata" perché accoppia $o_n$ con il più leggero $o_1$ anche quando ci starebbe un oggetto più pesante; la prova di scelta greedy è un doppio scambio di scatole, dove la disuguaglianza chiave è $p_s \le p_n$ e $p_t \le 1 - p_n$, da cui $p_s + p_t \le 1$.

Controesempi: provare che una strategia è sbagliata

Per mostrare che una strategia greedy non è ottima basta un'istanza. Per la selezione delle attività sono sbagliate, per esempio, "minima durata" (istanza $[0,5), [4,6), [5,10)$: sceglie $[4,6)$ e ottiene 1 attività, l'ottimo ne ha 2) e "minor numero di incompatibilità" (istanza a 11 attività della nota sulla selezione delle attività). Non vale invece il greedy quando le attività hanno pesi da massimizzare: serve la programmazione dinamica (Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigmala programmazione dinamica (DP) evolve il divide and conquer: invece di risolvere di nuovo le stesse sottoistanze, le salva in una tabella. Fibonacci ricorsivo costa F_n - 1 addizioni (esponenziale), quello con tabella n - 1. Tre condizioni: sottostruttura, sottoistanze ripetute, spazio dei sottoproblemi ristretto. Bottom-up o memoizzazione (ricorsione + tabella globale). Per i problemi di ottimizzazione lo schema è: sottostruttura ottima, ricorrenza sui costi, informazione addizionale, calcolo della tabella, ricostruzione.Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma →).

Domande d'esame

1. Quali due proprietà bisogna dimostrare per un algoritmo greedy e che cosa cambia se non c'è clean-up? Traccia: scelta greedy (esiste un ottimo che la contiene, per scambio) e sottostruttura ottima (assurdo con cut-and-paste); senza clean-up la residua è semplicemente ciò che rimane e la sottostruttura segue subito.
2. Dimostrare che in ogni scheduling ottimo il primo job è di durata minima. Traccia: formula $T_{sum} = \sum_j (n-j) t_{\pi(j)}$; scambio di $J_r$ (primo, non minimo) con $J_s$ più breve in posizione $k$: attese $T_i - t_r + t_s$ per $2 \le i \le k$, invariate per $i > k$; il totale scende di $(k-1)(t_r - t_s)$.
3. Quanti CD servono per $d = (4,3,5,2,6,1,4,7)$ con $d_{max} = 10$? Risposta: $5$ (greedy: $\{4,3\}, \{5,2\}, \{6,1\}, \{4\}, \{7\}$).