Informatica - Algoritmi e strutture dati

Full exam

Algoritmi e Strutture Dati 15/16 Durata: 3 ore Prova Scritta del 3 Febbraio 20161. In matematica una matrice sparsa e una matrice i cui valori sono quasi tutti uguali a zero. Rapp- resentare una matrice sparsa con un array bidimensionale corrisponderebbe ad un grosso spreco di memoria. Si preferisce denire una matrice sparsa come un insieme di triple< r; c; v >dove ogni combinazionercnell'insieme e unica (rsta per riga,cper colonna evper valore). Si vuole progettare una struttura dati per matrici sparse. Completare la specica dimatrice sparsa (ms), fornendo la specica semantica per mezzo di pre e post condizioni (specica costruttiva o modello astratto), rispetto alla seguente specica sintattica: domini: sm, intero, valore operatori: (a) crea()!ms //crea una nuova matrice sparsa (b) aggiungi(ms, intero, intero, valore)!ms //aggiunge al la matrice un valore non nul lovin posizione rigar, il primo intero, e colonnac, il secondo intero. La matrice include la nuova tripla< r; c; v > (c) rimuovi(ms, intero, intero)!ms //rimuove dal la matrice l'elemento in rigar, il primo intero, e colonnac, il secondo intero (d) leggi(ms, intero, intero)!valore //restituisce il valore in rigar, il primo intero, e colonnac, il secondo intero (e) trasposta(ms)!ms //calcola la trasposta di una matrice (f ) somma(ms, ms)!ms //eettua la somma di due matrici[7pt] 2. Fornire in C++ una possibile realizzazione della struttura dati matrice sparsa al punto 1), riportandosolo la denizione di classe: variabili di classe e denizione dei metodi. Motivare la scelta di altre strutture dati nel caso se ne faccia uso. [4pt] 3. Fornire la specica sintattica e semantica degli operatoriinsSottoAlberoeinsPrimoSottoAlberoper la struttura datiAlberi n-ari[3pt] 4. Spiegare la realizzazione di alberi n-ari mediantevettore dei padri,liste di glie concursori, fornendo vantaggi e svantaggi di ognuna [5pt] 5. Fornire in pseudocodice l'algoritmo diricerca in profondita(DFS) per alberi n-ari [3pt] 6. Descrivere come uno stack e una coda possano essere rappresentati mediante vettore [3pt] 7. Spiegare la tecnica algoritmica delbacktracking[4pt] 8. Motivare le dierenze fra una tecnica greedy e una di backtracking quando applicate ad unproblema di ottimizzazione[4pt]