Torna alla pagina di Algoritmi e strutture dati
Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)
:: Algoritmi e strutture dati - Risposte Esami 2009 ::
Testo dell'esame dal sito del docente (.PDF)
I codici di Huffman vengono utilizzati per comprimere i file. Consentono di risparmiare uno spazio che va dal 20% al 90% in base al tipo di file. Si basano sulla frequenza delle lettere nel file che permettono la costruzione di un codice ottimo. Ogni carattere ha associata una parola codice che può essere di lunghezza fissa o variabile.
Utizza dei codici prefissi che è un codice in cui nessuna parola è prefisso di un altra.
La decodifica avviene in quattro fasi:
Dato un file F, un codice C è ottimo per F se non esiste nessun altro codice che permette di risparmiare più spazio. Possono esistere più codici ottimi e sono rappresentato con un albero binario in cui ogni nodo interno ha due figli.
Il principio del codice di Huffman è il seguente: Deve minimizzare la lunghezza del codice delle parole più frequenti e assegnare ai caratteri con meno frequenza i codici corrispondenti ai percosi più lunghi all'interno dell'albero.
Ogni codice è progettato per uno specifico file e le fasi sono le seguenti:
L'algoritmo di Huffman è gready perchè ad ogni passo costruisce il nodo interno avente la frequenza minima possibile.
Una componente fortemente connessa in un grafo orientato è un insieme massimale di
vertici U contenuti in V. Per ogni vertice u,v appartentente a U esiste un cammino che va da u a v e uno che va da v a u.
Si calcola in tre fasi:
Gli alberi della vista in profondità del grafo trasposto rappresentano le componenti fortemente connesse di G.
Testo dell'esame dal sito del docente (.PDF)
L'ordinamento topologico di un grafo orientato è un ordinamento lineare dei suoi vertci tale che:
L'ordinamento topologico è utilizzato per determinare l'ordine di esecuzione di un insieme di attività in presenza di vincoli di precedenza.
Si può utilizzare la visita in profondità e per ordinare i vertici in ordine di tempo decrescente f di completamento oppure la soluzione diretta.
La soluzione diretta consiste nelle seguenti fasi:
Testo dell'esame dal sito del docente (.PDF)
La visita in ampiezza BFS permette di visitare il grafo a partire da un vertice s detto sorgente e visita sistematicamente tutto il grafo per scoprire tutti i vertici raggiungibili da s. Calcola le distanze minime di ogni vertice da s. Produce anche un albero i cui rami sono cammini di lunghezza minima. La visita espande uniformemente la frontiera tra i vertici scoperti e quelli non ancora scoperti.
L'algoritmo funziona nel seguente modo: assume che il grafo sia rappresentato con liste di adiacenze. Tutti i nodi adiacenti ad un nodo, sono aggiunti ad una coda Q di tipo FIFO che memorizza la frontiera.
Descrizione:
l'esecuzione dell'algoritmo.
inseriti nella coda, che in ogni istante conterrà tutti i nodi colorati di grigio, ma dei quali ancora non sono stati visitati gli adiacenti.
Il tempo di esecuzione di questo algoritmo è O(V+E).
Tecnica divide et impera: E' una tecnica ricorsiva dove il problema viene diviso in sotto problemi indipendenti che vengono risolti ricorsivamente (strategia top-down). E' utile solo quando i sottoproblemi sono indipendenti altrimenti gli stessi sottoproblemi possono venire risolti più volte. Un algoritmo che ne fà utilizzo è il merge-sort.
Testo dell'esame dal sito del docente (.PDF)
Ci sono due tecniche per visitare i grafi la DFS (visita in profondità) e la BFS (visita in ampiezza).
La visita in ampiezza BFS permette di visitare il grafo a partire da un vertice s detto sorgente e visita sistematicamente tutto il grafo per scoprire tutti i vertici raggiungibili da s. Calcola le distanze minime di ogni vertice da s. Produce anche un albero i cui rami sono cammini di lunghezza minima. La visita espande uniformemente la frontiera tra i vertici scoperti e quelli non ancora scoperti. L'algoritmo funziona nel seguente modo: assume che il grafo sia rappresentato con liste di adiacenze. Tutti i nodi adiacenti ad un nodo, sono aggiunti ad una coda Q di tipo FIFO che memorizza la frontiera.
Descrizione:
inseriti nella coda, che in ogni istante conterrà tutti i nodi colorati di grigio, ma dei quali ancora non sono stati visitati gli adiacenti.
Il tempo di esecuzione di questo algoritmo è O(V+E).
La visita in profondità DFS esplora il grafo partendo da un vertice s detto sorgente. Si esplorano gli archi uscenti dal vertice u raggiunto per ultimo. Se viene scoperto un nuovo vertice ci si sposta su tale vertice. Se tutti gli archi uscenti da u portano a vertici già scoperti si torna indietro e si riprende esplorando archi uscenti dal vertice cui u è stato scoperto. Il procedimento continua fino a che sono stati scoperti tutti i vertici raggiungibili dal vertice s iniziale scelto. Se non sono stati tutti scoperti si ripete il procedimento partendo da un vertice non ancora raggiunto (si sceglie una nuova sorgente).
Si utilizzano due marcatempi:
Pseudocodice DFS:
DFS(G)
DFS-Visit(u)
Il tempo di esecuzione di questo algoritmo è O(|V|+|E|)