FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 10. Tipologie di problemi.
Blue Glass Arrow RTL  9. Alberi binari di ricerca (BST)Crystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  11. Le tabelle di hash
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)
  • 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[1] 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: SV → 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: SV → 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 globalmenteModifica

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

Problema dello zaino

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 greedyModifica

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.

EsempiModifica

Il cambiamoneteModifica

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)Modifica

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 continuoModifica

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.  

CodiciModifica

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 HuffmanModifica

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.

NoteModifica

  1. cammino semplice = che non passa mai due volte per lo stesso nodo (in questo caso vertice).
Blue Glass Arrow RTL  9. Alberi binari di ricerca (BST)Crystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  11. Le tabelle di hash

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale