160120

Page 1

Algoritmi e Strutture Dati 15/16 Durata: 2 ore Prova Scritta del 20 Gennaio 2016 1. Si vuole progettare una struttura dati per un recommender system, dove gli utenti si registrano ad un sito di commercio elettronico e possono lasciare sul sito informazioni di gradimento per i prodotti venduti. Completare la specifica di recommender system (rs), fornendo la specifica semantica per mezzo di pre e post condizioni (specifica costruttiva o modello astratto), rispetto alla seguente specifica 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 definizione di classe: variabili di classe e definizione dei metodi [4pt] 3. Fornire la specifica sintattica e semantica degli operatori cancnodo e cancarco per la struttura dati grafo [3pt] 4. Spiegare la realizzazione di grafi mediante matrice di adiacenza e matrice di incidenza, fornendo van- taggi e svantaggi di ognuna [4pt] 5. Fornire in pseudocodice l’algoritmo…