Cerchiamo di rispondere alla seconda domanda

2) La soluzione trovata con l’algoritmo goloso è ottima o esistono anche soluzioni con più di quattro attività?

ActivitySelector(a, s, f, n) // f1 ≤ ... ≤ fn

A = {a1}, k = 1 for m = 2 to n if s[m] ≥ f[k] A = A {⋃ am}, k = m return A

L’algoritmo comincia con scegliere la prima attività a1 (quella con tempo di fine minimo)

Siamo sicuri che questa scelta non possa compromettere il risultato?

In altre parole: esiste sempre una soluzione ottima che contiene a1?

La risposta è affermativa.

Sia b1,...,bj una qualsiasi soluzione ottima (ne esiste certamente almeno una) che supponiamo ordinata per tempo di fine

b1 b2 bj…………………..

a1 b2 bj…………………..a1

k viene posto ad 1 ed aggiornato ad m ogni volta che si sceglie una nuova attività am

Siccome le attività sono ordinate per tempo di fine non decrescente, f[k] è il massimo tempo finale delle attività selezionate precedentemente.

ActivitySelector(a, s, f, n) // f1 ≤ ... ≤ fn

A = {a1}, k = 1 for m = 2 to n if s[m] ≥ f[k] A = A {⋃ am}, k = m return A

Con il test:

Siamo sicuri che questa scelta non comprometta il risultato?

In altre parole: esiste sempre una soluzione ottima che contiene am e le attività finora scelte?

l’algoritmo seleziona la prima attività am il cui

tempo di inizio s[m] è maggiore o uguale di f[k]

if s[m] ≥ f[k] A = A {⋃ am}, k = m

La risposta è ancora affermativa.

Assumiamo che esista una soluzione ottima b1,...,bi,bi+1,...,bj che estende le attività b1,...,bi finora scelte e supponiamo b1,...,bi e bi+1,...,bj ordinate per tempo di fine

amb1 bi bj….. …..bi+2am

b1 bi bj….. bi+1 …..bi+2

f[k]

Sappiamo quindi che durante tutta l’esecuzione dell’algoritmo esiste sempre una soluzione ottima contenente le attività b1,...,bi scelte fino a quel momento

Quando l’algoritmo termina non ci sono altre attività compatibili con b1,...,bi e quindi le attività b1,...,bi sono una soluzione ottima

L’algoritmo è goloso perchè ad ogni passo, tra tutte le attività compatibili con quelle già scelte, sceglie quella che termina prima.

Questa scelta è localmente ottima (golosa) perché è quella che lascia più tempo a disposizione per le successive attività.

Esercizio 1. Problema dello “zaino” frazionario: Dati n tipi di merce M1,…,Mn in quantità rispettive q1,…,qn e con costi unitari c1,…,cn si vuole riempire uno zaino di capacità Q in modo che il contenuto abbia costo massimo. Mostrare che il seguente algoritmo risolve il problema:

RiempiZaino(q, c, n, Q) // c1 ≥ c2 ≥ ... ≥ cn

Spazio = Q for i = 1 to n if Spazio ≥ q[i] z[i] = q[i], Spazio = Spazio – z[i] else z[i] = Spazio, Spazio = 0 return z

Esercizio 2. Problema dello “zaino” 0-1: Sono dati n tipi di oggetti O1,…,On in numero illimitato. Un oggetto di tipo Oi occupa un volume vi e costa ci.

Si vuole riempire uno zaino di capacità Q in modo che il contenuto abbia costo massimo. Mostrare che il seguente algoritmo non risolve il problema. RiempiZaino(v, c, n, Q) // c1/v1 ≥ c2/v2 ≥ ... ≥ cn /vn Spazio = Q for i = 1 to n z[i] = Spazio/v[i]

Spazio = Spazio – z[i]v[i] return z

Esercizio 3Siano a1,...,an attività didattiche aventi tempi di inizio s1,...,sn e tempi di fine f1,...,fn e supponiamo di avere un insieme sufficiente di aule in cui svolgerle.

Trovare un algoritmo per programmare tutte le attività usando il minimo numero possibile di aule.

Esercizio 4 Siano a1,...,an attività didattiche aventi tempi di inizio s1,...,sn e tempi di fine f1,...,fn e abbiamo a disposizione m aule A1,..., Am

Trovare un algoritmo goloso per programmare il massimo numero di attività nelle m aule.

Codici di Huffman

I codici di Huffman vengono usati nella compressione dei dati.

Essi permettono un risparmio compreso tra il 20% ed il 90%.

Sulla base delle frequenze con cui ogni carattere appare nel file, l’algoritmo goloso di Huffman trova un codice ottimo — ossia un modo ottimale di associare ad ogni carattere una sequenza di bit detta parola di codice.

Sia dato un file di 120 caratteri con frequenze:

carattere a b c d e ffrequenza 57 13 12 24 9 5

Usando un codice a lunghezza fissa occorrono 3 bit per rappresentare 6 caratteri. Ad esempio

carattere a b c d e fcod. fisso 000 001 010 011 100 101

Per codificare il file occorrono 1203 = 360 bit.

Possiamo fare meglio con un codice a lunghezza variabile che assegni codici più corti ai caratteri più frequenti. Ad esempio con il codice

carattere a b c d e ffrequenza 57 13 12 24 9 5cod. var. 0 101 100 111 1101 1100

Bastano 571 + 493 + 144 = 260 bit

Codici prefissi

Un codice prefisso è un codice in cui nessuna parola codice è prefisso (parte iniziale) di un’altra

Ogni codice a lunghezza fissa è ovviamente prefisso.

Ma anche il codice a lunghezza variabile che abbiamo appena visto è un codice prefisso.

Codifica e decodifica sono semplici con i codici prefissi.

Con il codice prefisso

la codifica della stringa abc è 0101100

carattere a b c d e fcod. var. 0 101 100 111 1101 1100

La decodifica è pure semplice.

Siccome nessuna parola codice è prefisso di un’altra, la prima parola codice del file codificato risulta univocamente determinata.

Per la decodifica basta quindi:

1. individuare la prima parola codice del file codificato

2. tradurla nel carattere originale e aggiungere tale carattere al file decodificato

3. rimuovere la parola codice dal file codificato

4. ripetere l’operazione per i caratteri successivi

Ad esempio con il codice

la suddivisione in parole codice della stringa di bit 001011101 è 001011101 a cui corrisponde la stringa aabe

carattere a b c d e fcod. var. 0 101 100 111 1101 1100

Per facilitare la suddivisione del file codificato in parole codice è comodo rappresentare il codice con un albero binario.

Esempio: il codice a lunghezza fissacarattere a b c d e ffrequenza 57 13 12 24 9 5cod. fisso 000 001 010 011 100 101

120

a:57 f:5e:9d:24c:12b:13

1

1

1

1 10 0 0

0 0

0

ha la rappresentazione ad albero

106 14

70 36 14

120

106 14

70 36 14

a:57 f:5e:9d:24c:12b:13

1

1

1

1 10 0 0

0 0

0

In realtà, come albero binario, la rappresentazione sarebbe

Noi eliminiamo le foglie e chiamiamo foglie i nodi interni senza figli

Il codice a lunghezza variabile

63

120

a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0

0 0

0

1

1

11

1

è rappresentato

carattere a b c d e ffrequenza 57 13 12 24 9 5cod. var. 0 101 100 111 1101 1100

La lunghezza in bit del file codificato con il codice rappresentato da un albero T è:

c

Tc cdfTB )()(

in cui la sommatoria è estesa a tutti i caratteri c dell’alfabeto Σ, fc è la frequenza del carattere c e dT(c) è la profondità della foglia che rappresenta il carattere c nell’albero T

Nota: assumiamo che l’alfabeto Σ contenga almeno due caratteri. In caso contrario basta un numero per rappresentare il file: la sua lunghezza

La lunghezza in bit del file codificato è anche:

interno nodo x

fxTB .)(

in cui la sommatoria è estesa alle frequenze x.f di tutti i nodi interni x dell’albero T.

63

120

a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0

0 0

0

1

1

11

1

a:57b:13c:12 14 d:24

f:5 e:9

0 1

Q

a:57d:24f:5 e:9Q

b:13c:12

carattere a b c d e ffrequenza 57 13 12 24 9 5

Costruzione dell’albero di Huffman:

a:5725

b:13c:12

0 114 d:24

f:5 e:9

0 1

Q

a:5725

b:13c:12

0 138

14 d:24

f:5 e:9

0

0

1

1

Q

a:5725

b:13c:12

0 114 d:24

f:5 e:9

0 1

Q

a:5725

b:13c:12

0 138

14 d:24

f:5 e:9

0

0

1

1

Q

63a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0 0

0

1

11

1

Q

63a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0 0

0

1

11

1

Q

63

120

a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0

0 0

0

1

1

11

1

Q

Implementazione dell’algoritmo goloso di Huffman

Huffman(c, f, n) Q = Ø // coda con priorità for i = 1 to n Push(Q, Nodo(fi, ci)) for j = n downto 2 x = ExtractMin(Q) y = ExtractMin(Q) Push(Q, Nodo(x, y)) return ExtractMin(Q)

Nodo(f, c) costruttore dei nodi foglia Nodo(x, y) costruttore dei nodi interni

Assumendo che la coda Q venga realizzata con un heap, le operazioni Insert ed ExtractMin richiedono tempo O(log n).

Pertanto l’algoritmo richiede tempo O(n log n) (dove n è il numero di caratteri dell’alfabeto).

L’algoritmo è goloso perché ad ogni passo costruisce il nodo interno avente frequenza minima possibile.

Ricordiamo infatti che

Siamo sicuri che in questo modo otteniamo sempre un codice ottimo?

interno nodox

fxTB .)(

Elementi della strategia golosaIngredienti comuni a molti problemi risolvibili con la strategia golosa:

Sottostruttura ottima: Ogni soluzione ottima non elementare si ottiene da soluzioni ottime di sottoproblemi.

Proprietà della scelta golosa: La scelta localmente ottima (golosa) non pregiudica la possibilità di arrivare ad una soluzione globalmente ottima.

Se T è ottimo ogni nodo interno ha due figli (altrimenti togliendo il nodo si otterrebbe un codice migliore)

120

63a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0

0 0

0

1

1

11

1

63

120

a:57

25

38

14

b:13c:12

d:24

f:5

e:9

0

0

0

0

0

1

1

1

1 1

250

90

Se T è ottimo esistono due foglie sorelle x ed y a profondità massima.

Proprietà (sottostruttura ottima)Sia T l’albero di un codice prefisso ottimo per l’alfabeto Σ e siano a ed b i caratteri associati a due foglie sorelle x ed y di T. Se consideriamo il padre z di x ed y come foglia associata ad un nuovo carattere c con frequenza

fc = z.f = fa+ fb allora l’albero T'=T - {x,y} rappresenta un codice prefisso ottimo per l’alfabeto

Σ' = Σ - {a,b} ⋃ {c}

ba

TbaTba

TcTbTa

ffTB

cdffcdffTB

cdfbdfadfTBTB

)'(

)()())()(()'(

)()()()'()(

''

'

1

Supponiamo, per assurdo, esista un albero S' per Σ' tale che B(S') < B(T').

Aggiungendo ad S' le foglie x ed y come figlie del nodo z (che in S' è una foglia) otterremmo un albero S per Σ tale che B(S) < B(T) contro l’ipotesi che T sia ottimo.

a b

T

x y

zc

T’

z

S

a b

z

x y

ba ffTBTB )'()(

)()'()'()( TBffTBffSBSB baba

c

S’

z

)'()'( TBSB

Proprietà (scelta golosa) Siano a e b due caratteri di Σ aventi frequenze fa ed fb minimeEsiste un codice prefisso ottimo in cui le parole codice di a e b hanno uguale lunghezza e differiscono soltanto per l’ultimo bit.

Se i codici di a e b differiscono soltanto per l’ultimo bit, nell’albero del codice le foglie a e b sono figlie dello stesso nodo, cioè sorelle.

Attenzione: Il Lemma non dice che ciò è vero per ogni codice prefisso ottimo e tanto meno che se ciò è vero il codice è ottimo!!!!

Dice solo che ciò è vero per almeno un codice ottimo.

Sappiamo che in T esistono due foglie sorelle a profondità massima.

Siano c e d i caratteri di tali foglie.

Mostriamo che scambiando c e d con a e b il codice rimane ottimo.

Possiamo supporre fc ≤ fd ed fa ≤ fb.

a e b sono i due caratteri con frequenza minima in assoluto e quindi fa ≤ fc ed fb ≤ fd.

c

ba

d

T

a

bc

d

T’

Sia T' ottenuto da T scambiando la foglia c con la foglia a (con ricalcolo delle frequenze dei nodi interni)

fa ≤ fc ed fb ≤ fd.

Allora:

Siccome T è ottimo B(T) = B(T') e quindi anche T' è ottimo.Scambiando poi le foglie d e b, si ottiene ancora un albero ottimo T'' in cui a e b sono foglie sorelle.

0

)]()(][[

)()()()(

)()()()(

)()()'()(

''

'

adcdff

adfcdfcdfadf

cdfadfcdfadf

kdfkdfTBTB

TTac

TcTaTcTa

TcTaTcTa

k

Tkk

Tk

Teorema L’algoritmo di Huffman produce un codice prefisso ottimo

Conseguenza della sottostruttura ottima e della proprietà della scelta golosa

Huffman(c, f, n) Q = Ø // coda con priorità for i = 1 to n Push(Q, Nodo(fi , ci)) for j = n downto 2 x = ExtractMin(Q) y = ExtractMin(Q) Push(Q , Nodo(x,y)) return ExtractMin(Q)

Esercizio 5Dimostrare che ogni algoritmo di compressione che accorcia qualche sequenza di bit deve per forza allungarne qualche altra.

Dimostrazione

Supponiamo per assurdo che l’algoritmo accorci qualche sequenza ma non ne allunghi nessuna.

Sia x la più corta sequenza che viene accorciata dall’algoritmo e sia m la sua lunghezza.

Le sequenze di lunghezza minore di m sono 2m-1 e non vengono accorciate o allungate.

Ognuna di esse viene codificata con una sequenza diversa e quindi le loro codifiche sono anch’esse 2m-1 e sono tutte di lunghezza minore di m.

Dunque ognuna delle 2m-1 sequenze più corte di m è codifica di qualche sequenza più corta di m.

Dunque la codifica di x coincide con la codifica di un’altra sequenza. ASSURDO!!!!

Suggerimento: usare 2n - 1 bit per la struttura dell’albero ed n log n bits per elencare i caratteri nell’ordine in cui compaiono nelle foglie (usando il codice del file non compresso)

Esercizio 6. Sia Σ = {c1, ...,cn} un insieme di caratteri ed f1,...,fn le loro frequenze

Rappresentare un codice prefisso ottimo per Σ con una sequenza di 2n - 1 + n log n bit

63

120

a:57

25 38

14b:13c:12 d:24

f:5 e:9

0

0

0 0

0

1

1

11

1

01001100111

se il nodo è interno metti uno 0 e scendi sul figlio sinistro;

se è una foglia metti un 1 e risali verso sinistra finché puoi: se arrivi alla radice fermati altrimenti risali di un passo verso destra e scendi sul figlio destro

Parti dalla radice e ripeti:

a

bc d

f e

0

0

0 0

0

1

1

11

1

01001100111 se incontri uno 0 crea il figlio sinistro e scendi su tale figlio;

se incontri un 1 risali verso sinistra finché puoi: se arrivi alla radice fermati altrimenti risali di un passo verso destra, crea un figlio destro e scedi su tale figlio

Crea la radice e ripeti: