Informatica - Algoritmi e strutture dati

Full exam

Algoritmi e Strutture Dati 16/17 Durata: 3 ore Prova Scritta del 2 Febbraio 20171. 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 specica di clustering, 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: 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 denita al punto 1), ripor-tando 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. Riportare l'albero binario di ricerca corrispondente ad una coda con priorita dovo aver inserito nell'ordinei seguenti elementi: 17, 26, 8, 50, 16, 19, 93, 4, 9 e 55. Poi illustrare il processo di inserimento del 7. Dopo l'inserimento del 7 illustrare il processo di rimozione del minimo. [5pt] 7. Facendo riferimento ad uno specico problema di ottimizzazione spiegare ed illustare l'esecuzione diuna strategia greedy applicata ad una istanza di quel problema. [6pt] 1