12.7 Codici di Huffman
12.7.3 Correttezza
Vogliamo ora provare che il codice di Huffman di una qualsiasi stringa `e ottimale tra tutti i codici prefissi.
Proposizione 12.5 Dato un alfabeto A e una frequenza f r definita su A, il codice di Huffman, ottenuto
mediante la procedura data sopra `e un codice prefisso ottimale.
Dimostrazione. Ragioniamo per induzione sulla cardinalit`a n di A. Se n = 2 la propriet`a `e ovvia.
Sup-poniamo n > 2 e assumiamo la propriet`a vera per ogni alfabeto di dimensione k ≤ n − 1. Consideriamo due lettere u, v di frequenza minima in A e definiamo l’alfabeto B ottenuto da A sostituendo u e v con una nuova lettera x di frequenza f r(x) = f r(u) + f r(v). Sia β il codice di Huffman di B. Per ipotesi d’induzione β `e un codice prefisso ottimale per B. Possiamo allora definire il codice α per l’alfabeto A nel modo seguente:
α(a) = β(a) se a 6= u e a 6= v β(x)0 se a = v β(x)1 se a = u
Chiaramente, α `e un codice prefisso per A e coincide con il codice di Huffman perch`e di fatto si pu`o ottenere applicando la stessa procedura.
Vogliamo ora provare che α `e ottimale. Osserviamo anzitutto che
C(α) = C(β) − |β(x)|f r(x) + |α(u)|f r(u) + |α(v)|f r(v) = C(β) + f r(u) + f r(v). (12.1) Consideriamo ora un qualsiasi codice prefisso γ sull’alfabeto A. Vogliamo provare che C(α) ≤ C(γ). Siano s e t le due lettere in A che hanno lunghezza di codice maggiore (cio`e tali che |γ(s)| e |γ(t)| siano massime in {|γ(a)| | a ∈ A}). Senza perdita di generalit`a , possiamo assumere che s e t siano fratelli nell’albero che rappresenta γ, altrimenti sarebbe possibile costruire un nuovo codice, nel quale s e t sono fratelli, che possiede un costo minore o uguale a quello di γ e quindi proseguire la dimostrazione per questo.
Definiamo un nuovo codice γ0che si ottiene da γ scambiando i le stringhe binarie associate a s e u e quelle associate a t e v. Si pu`o facilmente provare che il costo del nuovo codice non `e maggiore di quello del precedente:
C(γ0) = C(γ) + (|γ(u)| − |γ(s)|)(f r(s) − f r(u)) + (|γ(v)| − |γ(t)|)(f r(t) − f r(v))
Per le ipotesi fatte sulle lettere u, v, s e t, i due prodotti nel secondo termine dell’equazione precedente forniscono valori minori o uguali a zero; questo prova che C(γ0) ≤ C(γ). Ora poich´e u e v sono fratelli nell’albero che rappresenta γ0, possiamo denotare con ` il massimo prefisso comune di γ0(u) e γ0(v), definendo cos`ı un nuovo codice δ per l’alfabeto B:
δ(b) = (
γ0(b) se b 6= x ` se b = x
Osserva che C(γ0) = C(δ) + f r(u) + f r(v). Inoltre, poich´e β `e un codice ottimale su B, abbiamo che C(β) ≤ C(δ). Quindi, applicando la disuguaglianza (12.1), otteniamo
C(α) = C(β) + f r(u) + f r(v) ≤ C(δ) + f r(u) + f r(v) = C(γ0) ≤ C(γ)
Esercizi
1) Costruire il codice di Huffman delle seguenti frasi interpretando il blank tra una parola e l’altro come un simbolo dell’alfabeto:
il mago merlino e la spada nella roccia re art`u e i cavalieri della tavola rotonda
2) Considera il problema Knapsack 0-1 (Zaino) definito nel modo seguente:
Istanza: un intero positivo H, n valori v1, v2, . . . , vn∈ IN e n dimensioni d1, d2, . . . , dn∈ IN.
Soluzione : un insieme S ⊆ {1, 2, . . . , n} di dimesione al pi`u H e di valore massimo, ovvero tale che X i∈S di≤ H, X i∈S vi= max{X i∈A vi| A ⊂ {1, 2, . . . , n},X i∈S di≤ H}.
a) Definire un algoritmo greedy per il problema dato (per esempio basato sul rapporto tra il valore e la dimensione di ogni elemento).
b) Dimostrare mediante un esempio che l’algoritmo non fornisce sempre la soluzione ottima. 3) Considera la seguente variante al problema precedente (Knapsack frazionato):
Istanza: un intero positivo H, n valori v1, v2, . . . , vn∈ IN e n dimensioni d1, d2, . . . , dn∈ IN.
Soluzione : n numeri razionali f1, f2, . . . , fntali che 0 ≤ fi≤ 1 per ogni i e inoltre
n X i=1 fi· di≤ H, n X i=1 fi· vi= max{ n X i=1 gi· vi| g1, g2, . . . , gn∈ Q, ∀i 0 ≤ gi≤ 1, n X i=1 gi· di≤ H}.
a) Definire un algoritmo greedy per il problema assegnato.
Capitolo 13
I problemi NP-completi
Gli argomenti principali trattati nei capitoli precedenti riguardano la sintesi e l’analisi degli algoritmi. Lo scopo era quello di illustrare le tecniche principali di progettazione di un algoritmo e i metodi che permettono di valutarne le prestazioni con particolare riferimento alle risorse di calcolo utilizzate (tempo e spazio).
Vogliamo ora spostare l’attenzione sui problemi, studiando la possibilit`a di classificare questi ultimi in base alla quantit`a di risorse necessarie per ottenere la soluzione. Si `e riscontrato infatti, che per certi gruppi di problemi, le difficolt`a incontrate per trovare un algoritmo efficiente sono sostanzialmente le stesse. Lo stato di conoscenze attuale permette grossolanamente di raggruppare i problemi in tre categorie:
1. I problemi che ammettono algoritmi di soluzione efficienti;
2. I problemi che per loro natura non possono essere risolti mediante algoritmi efficienti e che quindi sono intrattabili;
3. I problemi per i quali algoritmi efficienti non sono stati trovati ma per i quali nessuno ha finora provato che tali algoritmi non esistano.
Molti problemi di notevole interesse appartengono al terzo gruppo e presentano tra loro caratteristiche cos`ı simili dal punto di vista algoritmico che risulta naturale introdurre metodi e tecniche che consentano di studiarne le propriet`a complessivamente. Questo ha portato a definire e studiare le cosiddette “classi di complessit`a ”, cio`e classi di problemi risolubili utilizzando una certa quantit`a di risorse (per esempio di tempo oppure di spazio). Lo scopo `e anche quello di confrontare la difficolt`a intrinseca dei vari problemi, verificando per esempio se un problema dato `e pi`u o meno facile di un altro, o se `e possibile trasformare un algoritmo per il primo in uno per il secondo che richieda all’incirca la stessa quantit`a di risorse.
Tra le classi di complessit`a definite in base al tempo di calcolo di grande interesse sono le classi P e NP che contengono un gran numero di problemi di interesse pratico. Lo studio delle relazioni tra queste classi `e indubbiamente una delle pi`u interessanti problematiche (alcune tutt’ora aperte) dell’informatica teorica.
13.1 Problemi intrattabili
Descriviamo ora con maggior precisione le tre classi di problemi sopra menzionate1.
Vi `e un generale accordo nel considerare come efficiente un algoritmo che opera in un tempo di calcolo che, nel caso peggiore, `e limitato da un polinomio nelle dimensioni dell’input. Questo porta a considerare la classe P dei problemi risolubili su RAM in tempo polinomiale secondo il criterio di costo logaritmico (vedi capitolo 3). Risulta quindi naturale individuare P come la classe dei problemi “praticamente” risolubili. Vi sono risultati che dimostrano come tale classe sia sostanzialmente robusta, cio`e non dipenda dal particolare modello di calcolo considerato.
La naturale controparte della classe appena descritta `e quella dei problemi che non possono essere risolti in un tempo polinomiale. Questi problemi sono tali che ogni algoritmo risolutivo richiede, nel caso peggiore, un tempo di calcolo esponenziale o comunque asintoticamente superiore ad ogni polinomio; essi sono chiamati “intrattabili” perch´e , pur essendo risolubili per via automatica, richiedono un tempo di calcolo molto elevato, tale da rendere ogni algoritmo di fatto inutilizzabile anche per dimensioni piccole dell’input. Per esempio, nella tabella presentata nella sezione 1.3, abbiamo visto che con tempi di calcolo dell’ordine di 2n, anche eseguendo 106operazioni al secondo, sono necessari parecchi anni per risolvere istanze di dimensione n = 50.
Le due classi precedenti sono ben definite ed essendo l’una il complementare dell’altra, dovrebbero contenere tutti i problemi risolubili. In realt`a per molti problemi di notevole interesse non sono stati trovati algoritmi che funzionano in tempo polinomiale ma neppure `e stato dimostrato che tali algoritmi non esistono. Tra questi vi sono problemi di decisione che provengono dalla ottimizzazione combinatoria o dalla logica, alcuni dei quali gi`a incontrati nei capitoli precedenti. Si tratta di problemi classici ampia-mente studiati in letteratura che trovano applicazioni in vari settori e per i quali sono noti algoritmi che funzionano in tempo esponenziale o subesponenziale, oppure algoritmi di approssimazione polinomiali. La classe pi`u rappresentativa di questo folto gruppo `e quella dei problemi NP-completi. Questa `e stata definita all’inizio degli anni ’70 e raccoglie una grande variet`a di problemi che sorgono natural-mente in vari settori dell’informatica, della ricerca operativa e della matematica discreta. Su di essi `e stata sviluppata una notevole letteratura2e il loro numero `e ormai di parecchie migliaia, raggruppati e studiati per settori specifici. Tali problemi sono computazionalmente equivalenti fra loro, nel senso che un eventuale algoritmo polinomiale per uno solo di essi implicherebbe l’esistenza di un analogo algorit-mo per tutti gli altri. Proprio l’assenza di una tale procedura, nonostante gli sforzi compiuti, ha portato alla congettura che i problemi NP-completi non siano risolubili in tempo polinomiale e quindi non siano contenuti nella classe P (anche se finora nessuno ha dimostrato un tale risultato).
1E bene ricordare che l’analisi che svolgiamo si riferisce comunque a problemi che ammettono un algoritmo di soluzione.` Infatti, `e noto che non tutti i problemi possono essere risolti mediante un algoritmo. I problemi che non ammettono un algoritmo di soluzione sono detti non risolubili o indecidibili e sono stati ampiamente studiati a partire dagli anni ’30. Tra questi quello pi`u noto `e il problema dell’arresto; nel nostro contesto, tale problema pu`o essere formulato nel modo seguente:
Istanza : un programma RAM P e un input I per P . Domanda : il programma P si arresta sull’input I?
Questo `e solo l’esempio pi`u famoso di una vasta gamma di problemi indecidibili che riguardano il comportamento dei programmi oppure le propriet`a delle funzioni da loro calcolate.
2
Si veda in proposito M.R.Garey, D.S.Johnson, Computers and intractability: a guide to the theory of NP-completeness, W.H. Freeman, 1979.