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 ::
17 Febbraio 2010
Testo dell'esame dal sito del docente (.PDF)
Risposta 1
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:
RadixSort(A,n)
for j=1 to d do
"usa un algoritmo stabile per ordinare A[1..n] rispetto alla j-esima cifra"
(A[1 .. n] è permutazione ordinata di a1,...,an)
Complessità:
Teta(d(n+k))
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:
BucketSort(A)
n=length(A)
for i=1 to n do
"inserisci A[i] nella lista B[[nA[i]]]"
(a1,...,an sono stati tutti inseriti nelle liste B[0..n-1] e gli elementi in una lista B[i] sono minori degli elementi nella lista successiva B[i+1])
for i=0 to n-1 do
"ordina la lista B[i] con insertion sort"
"concatena ordinatamente le liste B[0],B[1],...,B[n-1]"
(A[1..n] è una permutazione ordinata di a1,...,an)
Complessità:
Caso peggiore: Teta(n^2)
Caso migliore: Teta(n)
Caso medio: Teta(n)
Risposta 2.1
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:
- Make-Set(x): aggiunge alla struttura dati un nuovo insieme contenente solo l'elemento x (x non deve comparire in nessun altro insieme della struttura).
- Find-Set(x): ritorna il rappresentante dell'insieme che contiene x.
- Union(x,y): unisce i due insiemi contenenti x ed y in un'unico insieme.
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.
Risposta 2.2
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'}
Risposta 2.3
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:
- Z non ha figli quindi il puntatore a z del padre si sostituisce con NIL.
- Z ha un solo figlio. Il puntatore al padre di z punterà al figlio di z.
- Z ha due figli, si crea un nuovo collegamento per rimuovere il suo successore y che
non ha un figlio sinistro, poi si sostituiscono i dati di z con quelli di y.
Risposta 2.4
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.
- Fase 2: Definire ricorsivamente la soluzione ottima. La soluzione ottima contiene le soluzioni ottime ai sottoproblemi.
- Fase 3: Calcolare il valore di una soluzione ottima con strategia bottom up.
- Fase 4: Costruzione di una soluzione ottima a partire dalle informazioni calcolate.
Risposta 2.6
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:
- Si usa la visita in profondita su G per ordinare i vertici in ordine decrescente di completamento.
- Si calcola il grafo trasposto di G.
- Si esegue la visita in profondita sul grafo trasposto usando l'ordine dei vertici calcolato nella prima fase.
Gli alberi della visita in profondità nel grafo trasposto rappresentano le componenti
fortemente connesse.
27 Gennaio 2010
Testo dell'esame dal sito del docente (.PDF)
Risposta 2.1
L'ordinamento topologico di un grafo orientato è un ordinamento lineare dei suoi vertci tale che:
- Per ogni arco uv appartenenti a E il vertice u precede il vertice v.
- 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.
La soluzione diretta consiste nelle seguenti fasi:
- Si cercano tutti i vertici che non hanno archi incidenti in ingresso.
- Si stampa il verticie e si elimina il vertice con i suoi archi.
- Si ripete la procedura fino a che non ci sono più vertici.
Risposta 2.5
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.
Torna alla pagina di Algoritmi e strutture dati
