Algoritmi e strutture dati - Risposte Esami 2009

Torna alla pagina di Algoritmi e strutture dati

---

 :: Algoritmi e strutture dati - Risposte Esami 2009 ::

2 Novembre 2009

Testo dell'esame dal sito del docente (.PDF)

Risposta 3.1

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:

• Fase 1: Viene trovata la prima parola nel file codificato.
• Fase 2: Viene tradotta la parola e scritta nel file di decodifica.
• Fase 3: Viene eliminata la parola dal file di codificato.
• Fase 4: Si ripete fino a che non è stato decodificato l'intero file.

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:

• Fase 1: Si ottengono le frequenze dei caratteri.
• Fase 2: Si costruisce il codice ottimo.
• Fase 3: Si rappresenta il file tramire il codice ottimo.
• Fase 4: Si aggiunge al file una rappresentazione del codice ottimo.

L'algoritmo di Huffman è gready perchè ad ogni passo costruisce il nodo interno avente la frequenza minima possibile.

Risposta 3.3

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:

• Fase 1: Si usa la visita in profondità in G per ordinare i vertici in ordine di tempo di completamento f decrescente.
• Fase 2: Si calcola il grafo trasposto G' di G.
• Fase 3: Si esegue la visita in profondità su G' usando l'ordine dei vertici calcolato nella prima fase.

Gli alberi della vista in profondità del grafo trasposto rappresentano le componenti fortemente connesse di G.

21 Settembre 2009

Testo dell'esame dal sito del docente (.PDF)

Risposta 3.3

L'ordinamento topologico di un grafo orientato è un ordinamento lineare dei suoi vertci tale che:

1. Per ogni arco uv appartenenti a E il vertice u precede il vertice v.
2. Per transtitività, se u è raggiungibile da v allora u viene prima di v nell'ordinamento.

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:

1. Si cercano tutti i vertici che non hanno archi incidenti in ingresso.
2. Si stampa il verticie e si elimina il vertice con i suoi archi.
3. Si ripete la procedura fino a che non ci sono più vertici.

20 Luglio 2009

Testo dell'esame dal sito del docente (.PDF)

Risposta 3.3

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:

1. All'inizio dell'algoritmo tutti i vertici sono bianchi tranne la sorgente da cui parte

l'esecuzione dell'algoritmo.

1. Con l'andare avanti nella visita i vertici del grafo vengono colorati di grigio, ed

inseriti nella coda, che in ogni istante conterrà tutti i nodi colorati di grigio, ma dei quali ancora non sono stati visitati gli adiacenti.

1. Quando tutti i nodi adiacenti ad un nodo grigio sono stati visitati e quindi colorati di grigio, il nodo verrà colorato di nero e rimosso da Q.

Il tempo di esecuzione di questo algoritmo è O(V+E).

Risposta 3.4

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.

17 Giugno 2009

Testo dell'esame dal sito del docente (.PDF)

Risposta 2

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:

1. All'inizio dell'algoritmo tutti i vertici sono bianchi tranne la sorgente da cui parte l'esecuzione dell'algoritmo.
2. Con l'andare avanti nella visita i vertici del grafo vengono colorati di grigio, ed

inseriti nella coda, che in ogni istante conterrà tutti i nodi colorati di grigio, ma dei quali ancora non sono stati visitati gli adiacenti.

1. Quando tutti i nodi adiacenti ad un nodo grigio sono stati visitati e quindi colorati di grigio, il nodo verrà colorato di nero e rimosso da Q.

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:

1. d[u] che registra quando è stato scoperto un vertice e colorato di grigio.
2. f[u] che registra quando il vertice è stato completamente visitato e viene colorato di nero.

Pseudocodice DFS:

DFS(G)

DFS-Visit(u)

Il tempo di esecuzione di questo algoritmo è O(|V|+|E|)

---

Torna alla pagina di Algoritmi e strutture dati