170202

Page 1

Algoritmi e Strutture Dati 16/17 Durata: 3 ore Prova Scritta del 2 Febbraio 2017 1. In statistica, il clustering o analisi dei gruppi ` e un insieme di tecniche di analisi dei dati volte alla selezione e raggruppamento di elementi omogenei in un insieme di dati. Un cluster ` e una collezione di oggetti che sono simili l’un l’altro e sono dissimili dagli oggetti di altri cluster. Un clustering ` e un insieme di cluster. Si vuole progettare una struttura dati per rappresentare un clustering. Completare la specifica di clustering, fornendo la specifica semantica per mezzo di pre e post condizioni (specifica costruttiva o modello astratto), rispetto alla seguente specifica sintattica: domini: clustering, cluster, oggetto, intero operatori: (a) crea() → clustering // crea una clustering vuoto (senza nessun cluster) (b) aggiungiCluster(clustering, cluster) → clustering // aggiunge un cluster vuoto ad un clustering (c) aggiungiOggetto(clustering, cluster, oggetto) → clustering // aggiunge un oggetto ad un cluster (d) rimuoviOggetto(clustering, cluster) → clustering // rimuove un oggetto ad un cluster (e) spostaOggetto(clustering, cluster, cluster, oggetto) → clustering // sposta un oggetto dal primo al secondo cluster (f) nCluster(clustering) → intero // restituisce il numero di cluster [7pt] 2. Fornire in C++ una possibile realizzazione della struttura dati clustering definita al punto 1), ripor- tando la definizione di classe (variabili di classe e definizione dei metodi). Motivare la scelta di altre strutture dati nel caso se ne faccia uso [4pt] 3. Fornire la specifica sintattica e semantica degli operatori insSottoAlbero e insPrimoSottoAlbero per la struttura dati Alberi n-ari [3pt] 4. Spiegare la realizzazione di alberi n-ari mediante vettore dei padri, liste di figli e con…