Algoritmi e Strutture di dati - Appunti

Algoritmi greedy

Selezione delle attività

Date n attività, a₁, a₂, ..., a_n che usano la stessa risorsa (es. lezioni da tenere in una stessa aula); ogni attività a(i) ha un tempo di inizio s(i) ed un tempo di fine f(i) con s(i) < f(i); a(i) occupa la risorsa nell'intervallo [s(i), f(i)); a(i) e a(j) sono compatibili se [s(i), f(i)) ed [s(j), f(j)) sono disgiunti. L'obiettivo è quello di scegliere il massimo numero di attività compatibili. L'idea è quella di scegliere una delle attività compatibili che termina per prima.

Algoritmo (idea)

SelezioneAttivita (A)
    AttScelte = 0;
    AttCompatibili = A;
    while (AttCompatibili != 0) do
        -> scegli l'attività a € AttCompatibili che termina per prima;
        -> aggiungi a ad AttScelte;
        -> togli da AttCompatibili tutte le attività incompatibili con a;
    end while
    return AttScelte

Algoritmo (implementazione)

Supponiamo che le attività a₁, a₂, ..., a_n siano ordinate per tempo di fine decrescente. (f₁ <= ... <= f_n)

SelezioneAttivita (a, s, f, n)
    b1 = a1; k = 1; maxf = f1;
    for i = 2 to n do
        if s(i) >= maxf then
            k = k+1;
            b(k) = a(i);
            maxf = f(i)
        end if
    end for
    return b, k

// dove b contiene le attività scelte
// k indica il numero di attività scelte.
// maxf indica il massimo tempo finale delle attività precedentemente selezionate.

Discussione

Dimostrazione passo iniziale: L'algoritmo comincia senza alcuna verifica a scegliere la prima attività a₁. Questa scelta non compromette il risultato perché essendo le attività ordinate per ordine di fine, esiste sempre una soluzione ottima (almeno una) che contiene la prima attività a₁. Questo perché, dato che a₁ ha il tempo di fine f₁ minimo in assoluto terminerà prima di qualsiasi altra attività (b₁) appartenente ad un insieme di attività che formano una soluzione ottima. Al massimo terminerebbe allo stesso istante i.

Dimostrazione passi successivi: Con il test all'interno del for, l'algoritmo seleziona la prima attività a(i) il cui tempo di inizio s(i) è maggiore o uguale di maxf e che ovviamente terminerà per prima. Tale scelta non compromette il risultato perché, l'attività a(i) è quella con tempo di fine f(i) minimo in assoluto tra tutte le scelte compatibili. Pertanto a(i) andrà a sostituire, nella soluzione ottima B, b(k+1) e sarà compatibile con b(k+2) e quindi esiste un'altra soluzione ottima contenente a(i).

Codici di Huffman

I codici di Huffman vengono ampiamente usati nella compressione dei dati. Normalmente permettono un risparmio compreso tra il 20% e il 90%. Sulla base delle frequenze con cui ogni carattere appare nel file, l'algoritmo di Huffman trova un codice ottimo, ossia un modo ottimale di associare ad ogni carattere una sequenza di bit detta parola di codice.

Esempio

Sia dato un file di 6 caratteri diversi (a, b, c, d, e, f) ripetuti, ciascuno con frequenze diverse, per un totale di 120 volte. Per rappresentare 6 caratteri servono chiaramente almeno 3 bit. Pertanto per codificare il file occorrono 120*3 = 360 bit. Si può fare di meglio assegnando codici più corti (1 o 2 bit) ai caratteri che sono più frequenti all'interno del file. Sicuramente, in questo modo, avremo un file codificato in meno di 360 bit.

Di particolare importanza sono i 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. Anche il codice a lunghezza variabile che abbiamo appena visto è un codice prefisso. Con i codici prefissi, la codifica e la decodifica sono particolarmente semplici. Siccome nessuna parola codice è prefisso di un'altra, la prima parola codice del file codificato risulta univocamente determinata.

Esempio di codifica

a -> 0
b -> 101
c -> 100
d -> 111
e -> 1101
f -> 1100

La codifica della stringa 'abc' è 0.101.100. Per la decodifica basta quindi:

• Individuare la prima parola codice del file codificato;
• Tradurla nel carattere originale e aggiungere tale carattere al file decodificato;
• Rimuovere la parola codice dal file codificato;
• Ripetere l'operazione per i successivi caratteri.

La decodifica della stringa di bit 001011101 sarà: 0.0.101.1101 --> aabe.

Lunghezza in bit del file codificato

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

B(T) = sum (f(c)d(T)(c))

dove:

• C è l'alfabeto;
• f(c) è la frequenza del carattere c;
• d(T)(c) è la profondità della foglia che rappresenta il carattere c nell'albero T.

Si assume che l'alfabeto C contenga almeno due caratteri. In caso contrario basta un numero per rappresentare il file: solamente la sua lunghezza.

Implementazione dell'algoritmo greedy di Huffman

Huffman (c, f, n)
    Q = 0;
    for i = 1 to n do
        Push(Q, nodo (f(i), c(i)))
    end for
    for j = n down to 2 do
        x = ExtractMin (Q);
        y = ExtractMin (Q);
        Push (Q, nodo (x, y));
    end for
    return ExtractMin (Q)

Dove:

• Q è una coda con priorità;
• nodo (f, c) è il costruttore di un nodo foglia;
• nodo (x, y) è il costruttore di un nodo interno.

Assumendo che la coda Q venga realizzata con un heap, le operazioni Push ed ExtractMin richiedono tempo O(log n). Pertanto l'intero 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.

Dimostrazione della scelta greedy

Per dimostrare che la scelta ottima localmente (greedy) non pregiudica la possibilità di arrivare ad una soluzione globalmente ottima, utilizzo la seguente proprietà:

Proprietà della scelta greedy

Siano a e b due caratteri di C aventi frequenze f(a) e f(b) minime. Allora esiste un codice prefisso ottimo in cui le parole codice di a e b hanno la stessa lunghezza e differiscono soltanto per l'ultimo bit. Ciò significa che a e b sono figlie dello stesso nodo e quindi sorelle.

Dimostrazione

• Sia T un albero contenente i caratteri e le loro frequenze; Supponiamo che questo sia ottimo. Quindi in T esistono due foglie a profondità massima che sono sorelle;
• Siano c e d i caratteri corrispondenti a tali foglie;
• Mostriamo che scambiando c e d con a e b il codice rimane ottimo;
• Possiamo supporre che f(c) <= f(d) e che f(a) <= f(b);
• a e b sono due caratteri con frequenza minima in assoluto e quindi f(a) <= f(c) ed f(b) <= f(d).

Allora:

B(T) - B(T') = sum (f(e)d(T)(e)) - sum (f(e)d(T')(e))

Dimostrandolo per a e c oppure per d e b, con diversi passaggi si ottiene che tale uguaglianza sarà >= 0; Pertanto siccome T è ottimo B(T) = B(T') e quindi anche T' è ottimo.

Sottostruttura ottima

Dimostrare che ogni soluzione ottima non elementare si compone di soluzioni ottime di sottoproblemi utilizzo la seguente proprietà:

Proprietà della sottostruttura ottima

Sia C un alfabeto e siano a ed b i caratteri con frequenza minima. Sia C' l'alfabeto ottenuto sostituendo ad {a, b} un unico carattere nuovo carattere con frequenza (f(c) = f(a) + f(b)). E sia T' l'albero di un codice prefisso ottimo per C'. Allora l'albero T ottenuto da T' sostituendo la foglia corrispondente a c con un nodo interno, avente come figli le foglie a ed b rappresenta un codice prefisso ottimo per l'alfabeto C.

Dimostrazione

B(T) = B(T') + f(a)d(T)(a) + f(b)d(T)(b) - f(c)d(T')(c) = B(T') + (f(a) + f(b))(d(T')(c) + 1) - (f(a) + f(b))d(T')(c) = B(T') + f(a) + f(b)

Supponiamo, per assurdo, che esista un albero S per C tale che B(S) < B(T). Per il lemma precedente (1.1) possiamo assumere che le foglie corrispondenti ad a e b siano sorelle, figlie di un nodo z. Consideriamo l'albero S' per C' ottenuto da S facendo diventare z una foglia, corrispondente al carattere c, (con frequenza f(c) = f(a) + f(b)); Allora come in precedenza avremo: B(S') = B(S) - (f(a) + f(b)) < B(T) - (f(a) + f(b)) = B(T') Questo contraddice l'ottimalità di T'. Assurdo.

Programmazione dei lavori

Un lavoro unitario è un lavoro che richiede esattamente una unità di tempo per essere eseguito. Dato un insieme S di lavori unitari, una programmazione per S è semplicemente un ordine in cui eseguirli. L'esecuzione del primo lavoro inizia all'istante 0 e termina all'istante 1, quella del secondo inizia all'istante 1 e termina all'istante 2, ecc.

Il problema della programmazione di lavori unitari

Nel problema della programmazione di lavori unitari con scadenza e penalità sono dati:

• n lavori unitari a₁, a₂, ..., a_n;
• le scadenze d₁, d₂, ..., d_n entro cui deve essere terminato ciascuno di tali lavori;
• le penalità w₁, w₂, ..., w_n da pagare per i lavori che non sono terminati entro la scadenza.

La richiesta è quella di minimizzare la somma delle penalità da pagare.

Proprietà della programmazione

• Proprietà 1: Data una programmazione qualsiasi ne esiste una equivalente in cui i lavori in orario vengono eseguiti prima di quelli in ritardo;
• Proprietà 2: Data una programmazione qualsiasi ne esiste una equivalente in cui i lavori in orario sono ordinati per scadenza;
• Proprietà 3: In una programmazione ottima l'ordine dei lavori in ritardo è irrilevante;
• Proprietà 4: Una programmazione canonica ottima è determinata dall'insieme A dei lavori in orario.

Definizione di indipendenza

Un insieme di lavori A si dice indipendente se esiste almeno una programmazione in cui tutti i lavori in A sono in orario. Quest'ultima definizione permette di riformulare il problema della programmazione dei lavori. Dato un insieme di lavori unitari con scadenze e penalità, determinare un sottoinsieme di A tale che:

• A è indipendente;
• A ha costo w(A) massimo.

È equivalente dire che:

1. A è indipendente;
2. N(t)(A) <= t per ogni t = 0, 1, 2, ..., n; //N(t)(A) indica il numero di lavori in A con scadenza minore o uguale a t.
3. Se i lavori in A sono eseguiti in ordine di scadenza nessuno di essi risulta essere in ritardo.

Verifica dell'indipendenza di un insieme A

Algoritmo: IndipTest(I, k, d)
    //Pre-condiz: I[1..k] sono gli indici di k lavori scelti tra a1, a2, ..., an;
    for t = 0 to n do
        N(i) = 0;
    for j = 1 to k do
        d = dI[j];
        N(d) = N(d) + 1;
    end for
    //N(t) = numero di lavori in I[1..k] con scadenza = t;
    for t = 1 to n do
        N(t) = N(t) + N(t-1);
    end for
    //N(t) = numero di lavori in I[1..k] con scadenza <= t;
    if (N(t) > t) then
        return false
    end if
return true

Tutte queste analisi ci portano verso un bel algoritmo greedy per la selezione dei lavori:

Algoritmo di selezione dei lavori

Algoritmo: SelezLavori (d, w, n)
    //Pre-condiz: w1 >= w2 >= ... >= wn
    k = 0;
    h = n + 1;
    //I[1..k] indipendenti e I[h..n] incompatibili con i lavori in I[1..k]
    for i = 1 to n do
        I[k+1] = i; //provo ad aggiungere i a I[1..k]
        if (IndipTest(I, k+1, d)) then //se I[1, k+1] è indipendente OK.
            k = k+1;
        else //altrimenti metto il lavoro i in coda
            I[h-1] = i;
            h = h-1;
        end if
    end for
    Sort(I, k, d) //ordina I[1,k] in ordine di scadenza
    return I //Post-condiz I[1..n] è una programmazione ottima.

Vedere dimostrazione da slide n. 24

Matroidi

La tecnica usata per risolvere il problema della programmazione di un insieme S di lavori unitari con scadenza e penalità si può generalizzare ad una vasta gamma di problemi. Per risolvere il problema abbiamo costruito un sottoinsieme indipendente A di lavori tale che la somma dell...