Algoritmi e programmazione:Tipologie di problemi/sub

• 2 problemi di ricerca: ricerca di una soluzione valida (= che soddisfa certi criteri), se esistente (ho o non ho trovato la soluzione?):

  es.: ciclo hamiltoniano: dato un grafo non orientato, esiste un cammino semplice chiuso (ciclico) che collega tutti i vertici?

• problemi di ottimizzazione: ricerca della soluzione ottima (= che minimizzi un determinato costo o massimizzi un determinato vantaggio):

  es.: cammini minimi: data una rete di città modellata come un grafo, a ogni arco è associata una funzione distanza (peso). Si cerca di minimizzare la funzione distanza. Se il cammino minimo non esiste, è come se ci fosse un cammino di peso infinito;

• 3 problemi ibridi (ricerca + ottimizzazione): ricerca della soluzione valida minima. Non si conoscono tuttora algoritmi polinomiali per risolvere questo tipo di problemi → algoritmi euristici:

  es.: commesso viaggiatore: ricerca del cammino semplice chiuso minimo.

4 S spazio delle soluzioni (= insieme di tutte le possibilità) → V soluzioni valide → M soluzioni migliori

• 5 problemi di ricerca: S ⊂ V → verificare che V ≠ ∅ e trovare una soluzione valida qualsiasi;
• problemi di ottimizzazione: S = V (tutte le soluzioni sono valide) → trovare la soluzione ottima;
• problemi ibridi: S ⊂ V → trovare la soluzione di minimo costo/massimo vantaggio all'interno di S.

6 Trovare la soluzione ottima significa esaminare tutto lo spazio delle soluzioni → non è sempre possibile:

• soluzione ottima globalmente: massimo assoluto della funzione di ottimizzazione nell'intero dominio;
• soluzione ottima localmente: massimo relativo della funzione di ottimizzazione in un sottoinsieme del dominio → meno costo.

Soluzione ottima globalmente

Il problema dello zaino discreto (approccio divide et impera di tipo ricorsivo)

Un ladro con uno zaino piccolo di volume $P$ deve rubare $N$ oggetti appartenenti a un insieme $S$; l'oggetto $j$-esimo, di peso $p_j$ e valore $v_j$, vale $x_{j}=1$ se viene preso oppure $x_{j}=0$ se lasciato. Il ladro deve minimizzare il volume occupato ($\sum _{j\in S}p_{j}x_{j}\leq P$) e massimizzare il valore complessivo ($\sum _{j\in S}v_{j}x_{j}={\text{MAX}}$), verificando ogni volta la capacità residua disponibile, cioè il volume ancora libero. Il problema si dice discreto perché ogni oggetto è preso o lasciato, non si può spezzare in più parti. Le soluzioni possono essere enumerate esaustivamente tramite un albero, in modo da poterle esplorare tutte ricorsivamente. Si arriva a una foglia quando non è più possibile andare avanti (non è detto che lo zaino è pieno). L'obiettivo è trovare la foglia per cui il valore degli oggetti è massimo, tenendo presente che ci possono essere eventualmente più foglie con lo stesso valore. Questo approccio ha un costo elevato, ma la soluzione è ottima globalmente.

Il paradigma greedy

7 Si segue un solo cammino, scegliendo quella che appare di volta in volta la soluzione migliore, secondo una funzione di appetibilità (= che misura la convenienza locale) → non è detto che si trovi la soluzione ottima globalmente, però si riduce il costo. Nell'algoritmo greedy non c'è il backtrack, ossia non si ritorna mai sui passi precedenti. Il procedimento termina quando la configurazione non permette più l'esecuzione di alcuna scelta.

9 Tipi di appetibilità

• appetibilità fisse: le appetibilità sono costanti → una volta ordinate in un vettore, a ogni passo si sceglie l'appetibilità massima;
• appetibilità modificabili: a ogni passo si ricalcolano le appetibilità → le code a priorità permettono di mantenere l'ordinamento.

Esempi

Il cambiamonete

10 Il problema consiste nel trovare il resto con numero minimo di monete. A ogni passo, si sceglie la moneta di valore più grande (cioè avente appetibilità massima) tra quelle compatibili sul resto, quindi si considera il resto residuo. Le appetibilità sono fisse, perché dipendono unicamente dal sistema di monetazione corrente → 12 se la monetazione è particolare, la soluzione data dall'algoritmo greedy può però essere non ottima.

Il problema dello zaino discreto (approccio greedy)

Si estrae un cammino dallo spazio di ricerca, cioè a ogni passo si segue un solo cammino. Questo approccio ha un costo inferiore, ma non è detto che si riesca a trovare la strada ottima globalmente.

14 Si cerca l'oggetto ad appetibilità massima (= massimo valore), con la limitazione che sia compatibile con la funzione volume.

Il problema dello zaino continuo

17 $0\leq x_{j}\leq 1$ è una variabile reale che misura quanta parte di un oggetto (es. polvere d'oro) è stata presa.

18 Per ogni oggetto non si considera il valore complessivo, ma si considera il valore specifico: ${\tfrac {v_{j}}{p_{j}}}$ → soluzione migliore.  

Codici

21 Come effettuare codifiche (da simbolo a parola di codice) e decodifiche (da parola di codice a simbolo)? Una serie di parole di codice si dice codice.

• simboli isofrequenti: la probabilità di trovare simboli è uniforme (c'è la stessa probabilità di trovare un simbolo piuttosto che un altro)
• simboli non isofrequenti: es. lingue (più vocaliche o più consonantiche)

22 Le parole di codice possono essere:

• a lunghezza fissa: dati ${\text{card}}\left(S\right)$ simboli, sono possibili $n!$ parole di codice costituite da $n=\sup {\left(\log _{2}{{\text{card}}\left(S\right)}\right)}\in \mathbb {N}$ bit. La decodifica di un codice è più facile, perché basta suddividerlo nella unità di lunghezza;
• a lunghezza variabile: ogni parola di codice ha una lunghezza variabile → la decodifica è difficoltosa, però si può usare per la compressione delle informazioni perché, assegnando meno bit ai simboli più frequenti, si può limitare il numero di bit necessari.

24 stringa di ordine k (k-prefisso) = stringa contenente i primi k bit

Nel caso a lunghezza variabile, è necessario costruire un codice (libero da) prefisso per evitare le ambiguità, in modo che nessuna parola di codice sia a sua volta prefisso di un'altra parola di codice.

Codici di Huffman

32 I codici di Huffman sono buoni codici a lunghezza variabile. Come costruire un codice di Huffman tramite un albero binario:

1. i simboli si ordinano per frequenza crescente in una coda a priorità;
2. la coppia di simboli a frequenza meno elevata (costituita dal primo minimo e dal secondo minimo) si fonde in un aggregato;
3. si associa a un simbolo il bit 0 e all'altro simbolo il bit 1;
4. si assegna all'aggregato una frequenza pari alla somma delle loro frequenze;
5. l'aggregato si reinserisce nella coda a priorità;
6. si riparte al punto 1, considerando l'aggregato come un semplice simbolo ma con la nuova frequenza.

Condizione di terminazione: la coda a priorità è vuota (a ogni passo da due simboli si passa a un solo simbolo). È un algoritmo greedy perché ogni volta si scelgono le appetibilità massime (in questo caso: le frequenze minime).

40 Il costo è linearitmico perché si usano le operazioni sulle code a priorità: $T \left( n \right) = O \left( n \log{n} \right)$

25 Percorrendo questo albero binario, si possono effettuare le operazioni di codifica/decodifica.