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 2010 ::
Testo dell'esame dal sito del docente (.PDF)
Il problema dell'ordinamento si propone di trovare algoritmi come soluzione di problemi computazionali, dove in input sono presenti un numero qualsiasi di elelmenti e in output la permutazioni di tali elementi ordinati in ordine crescente.
Radix Sort:
Assumiamo che i valori degli elementi dell'array siano interi rappresentabili con al più d cifre in una certa base b. Per ordinare l'array si usa d volte un algoritmo di ordinamento stabile (come CountingSort) per ordinare l'array rispetto a ciascuna delle d cifre partendo dalla meno significativa.
Pseudocodice:
Complessità:
BucketSort:
Assume che i valori da ordinare siano numeri reali in un intervallo sempiaperto [a,b) che per semplicità di esposizione assumiamo sia l'intervallo [0,1). Per ordinare un array A[1..n] divide l'intervallo in n parti uguali e usa un array B[0..n-1] di liste (i bucket) mettendo in B[k] gli A[i] che cadono nella k-esima parte dell'intervallo. Dopo di che riordina ciascuna lista e infine ricopia in A tutti gli elementi delle liste.
Pseudocodice:
[[
nA[i]]]
"
Complessità:
Le strutture dati per insiemi disgiunti servono a mantenere una collezione
S = {S1,S2,...,Sk}
di insiemi disgiunti. Ogni insieme della collezione è individuato da un rappresentante che è un particolare elemento dell'insieme.
Operazioni sugli insiemi disgiunti:
Rappresentazione con foreste:
Ogni insieme è rappresentato con un albero i cui nodi, oltre al campo info hanno soltanto un campo parent che punta al padre.
Euristica dell'unione per rango:
Per ogni nodo x manteniamo un campo rank che è un limite superiore all'altezza del
sottoalbero di radice x.
Union mette la radice con rango minore come figlia di quella di rango maggiore.
Un sottografo del grafo G=(V,E) è un grafo G'=(V',E') tale che V'DV e E'DE. Il sottografo di G=(V,E) indotto da V'DV è il grafo G'=(V',E') tale che:
E' = {uv: uv ∈ E e u, v ∈ V'}
Gli alberi binari di ricerca sono strutture dati che possono eseguire molte operazioni su insiemi dinamici come: SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE. Possono essere utilizzati sia come dizionari che come code di priorità. Il tempo delle operazioni è proporzionale all'altezza dell'albero. Ogni nodo può aver al massimo due figli rappresentati da record. Un albero binario di ricerca è rappresentato da una struttura dati concatenata in cui ogni nodo è un oggetto. Ogni nodo ha i seguenti campi: puntatore al padre, figlio sx e dx, chiave e dati. La mancanza di un figlio è rappresentata con puntatore a NIL. La radice è l'unico nodo ad avere puntatore al padre NIL.
Le proprietà da rispettare sono: tutti i valori dei nodi del sottoalbero sinistro sono minori della radice mentre quelli del sottoalbero destro sono maggiori della radice. La visita si può esegue in profondità con uno dei 3 algoritmi di ricorsione: preordine, inordine, postordine.
La cancellazione ha come argomento il puntatore al nodo z da cancellare e ci sono 3 casi:
non ha un figlio sinistro, poi si sostituiscono i dati di z con quelli di y.
La tecnica divide-et-impera è una tecnica ricorsiva che divide il problema in sotto problemi dipendenti e li risolve ricorsivamente (approccio top-down). Non si utilizza con problemi che non sono indipendenti perchè possono venire risolti più volte.
La tecnica di programmazione dinamica è una tecnica iterativa che si utilizza quando ci sono sottoproblemi in comune. La soluzione viene costruita a partire da più sotto-problemi non indipendenti potenzialmente ripetuti (approccio bottom-up).
Si applica quando:
Sottostruttura ottimale: E' possibile combinare soluzioni di sottoproblemi per trovare la soluzione di un problema più grande.
Sottoproblemi ripetuti: Un sottoproblema può occorrere più volte.
Spazio dei sottoproblemi: Deve essere polinomiale.
Le fasi della programmazione dinamica sono:
* Fase 1: Definire la struttura di una soluzione ottima. Mostrare che una soluzione ottima si ottiene da soluzioni ottime di sottoproblemi.
Una componente fortemente connessa di un grafo G è un insieme U di vertici contenuto in V tale che per ogni u,v appartente a U esiste un cammino da u a v e da v a u.
Dato un grafo orientato G, il grafo delle componenti fortemente connesse di G è H ed ha come vertici le componenti fortemente connesse di G e un arco da un cfc C ad una cfc C' se e solo se in G c'è un arco che connette un vertice di C ad un vertice di C'.
Per calcolare le componenti fortemente connesse di un grafo ci sono tre fasi:
Gli alberi della visita in profondità nel grafo trasposto rappresentano le componenti fortemente connesse.
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.
La soluzione diretta consiste nelle seguenti fasi:
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.