Informatica - Algoritmi e strutture dati

Full exam

Algoritmi e Strutture Dati 15/16 Durata: 2 ore Prova Scritta del 20 Gennaio 20161. Si vuole progettare una struttura dati per un recommender system, dove gli utentisi registrano ad un sito di commercio elettronico e possono lasciare sul sito informazioni di gradimento per iprodotti venduti. Completare la specica direcommender system(rs), 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: rs, utente, prodotto, integer, real operatori: (a) creaRS()!rs //crea un nuovo recommender system (b) registraUtente(rs, utente)!rs //aggiunge un nuovo utente al recommender system (c) aggiungiProdotto(rs, prodotto)!rs //aggiunge un nuovo prodotto al recommender system (d) gradisce(rs, utente, prodotto, integer)!rs //memorizza un gradimento, espresso con un valore intero da 1 a 5, per un prodotto da parte di un utente (e) gradimenti(rs, prodotto)!integer //resituisce il numero di gradimenti ricevuti da un prodotto (f ) mediaGradimenti(rs, prodotto)!real //restituisce la media dei gradimenti ricevuti da un prodotto (g) gradimentiSimili(rs, utente, utente)!integer //restituisce il numero di prodotti per i quali sia il primo che il secondo utente hanno espresso un gradimento[7pt] 2. Fornire in C++ una possibile realizzazione della struttura dati recommender system al punto 1),riportando solo la denizione di classe: variabili di classe e denizione dei metodi [4pt] 3. Fornire la specica sintattica e semantica degli operatoricancnodoecancarcoper la struttura dati grafo[3pt] 4. Spiegare la realizzazione di gra mediante matrice di adiacenza e matrice di incidenza, fornendo van-taggi e svantaggi di ognuna [4pt] 5. Fornire in pseudocodice l'algoritmo di ricerca di ampiezza (BFS) per gra, motivando l'utilizzo di altrestrutture dati per la sua implementazione [3pt] 6. Spiegare il concetto dicol lisionee le corrispondenti tecniche di gestione perdizionari[5pt] 7. Fornire la specica diproblema di ricerca[3pt] 8. Spiegare la tecnica algoritmicagreedy[4pt] 1