Informatica - Algoritmi e strutture dati

Full exam

Algoritmi e Strutture Dati 15/16 Durata: 3 ore Prova Scritta del 17 Febbraio 20161. Si vuole progettare una struttura dati per polinomi, deniti come una sequenza ordinata di coppie . Ad esempio il polinomiop(x) =x2 + 3 corrisponde alla sequenzaf ; g. Completare la specica dipolinomio, 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: polinomio, coeciente, esponente operatori: (a) crea()!polinomio //crea un nuovo polinomio di grado 0,p(x) = 0 (b) settaEsponente(polinomio, esponente, coeciente)!polinomio //imposta il coeciente (ultimo parametro) di un dato esponente (secondo parametro) (c) rimuoviEsponente(polinomio, esponente)!polinomio //imposta a zero il coeciente di un dato esponente (secondo parametro) (d) leggiCoeciente(polinomio, esponente)!coeciente //restituisce il coeciente di un dato esponente (secondo parametro) (e) grado(polinomio)!esponente //restituisce l'esponente piu grande (f ) somma(polinomio, polinomio)!polinomio //restituisce la somma di due polinomi (g) prodotto(polinomio, polinomio)!polinomio //restituisce il prodotto di due polinomi[7pt] SOLUZIONE domini:polinomio: famiglia di insiemi di coppie di tipo< c; e >dovece di tipo coeciente edee di tipo esponente;coeciente: insieme dei valori tipo reale;esponente: insieme dei valori di tipo intero. operatori: (a) crea()!p PRE: - POST: p =; (b) settaEsponente(p, e, c)!p' PRE:6 9< c0 ; e0 >2pt.c.e=e0 POST:p0 =p[< c; e > (c) rimuoviEsponente(p, e)!p' PRE:9< c0 ; e0 >2pt.c.e=e0 POST:p0 =pn< c; e > (d) leggiCoeciente(p, e)!c PRE:9< c0 ; e0 >2pt.c.e=e0 POST:c=c0 (e) grado(p)!e PRE: - POST: sep=;allorae= 0, altrimentie=e0 t.c.< e0 ; c0 >2pe6 9< e00 ; c00 >2pt.c. e00 > e0 1 (f ) somma(p, p') !p" PRE: POST:p00 =f< c; e >gt.c.< c; e > (g) prodotto(p, p')!p" PRE: POST: 2. Fornire in C++ una possibile realizzazione e rappresentazione della struttura dati polinomio al punto1), riportando solo 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 operatoricostrBinAlberoecancSottoBinAlberoper la struttura datiAlberi binari[3pt] 4. Spiegare la realizzazione di alberi binari mediantevettoreecol legata con cursori, fornendo vantaggi e svantaggi di ognuna[4pt] 5. Fornire in pseudocodice l'algoritmo divisita in post-ordineper alberi binari [3pt] 6. Descrivere come un albero binario pu essere utilizzato per rappresentare una coda con priorita, de-scrivendo inoltre come si eettuano le operazioni di inserimento e cancellazione di elementi [6pt] 7. Spiegare cosa e unproblema di ottimizzazionee quali tecniche si possono adottare per risolverlo [6pt]