170119

Pagina 1

Algoritmi e Strutture Dati 16/17 Durata: 3 ore Prova Scritta del 19 Gennaio 2017 1. Si vuole progettare una struttura dati per la memorizzazione di una griglia, di n righe ed m colonne, cosituita da celle. Lo stato di ogni cella nella griglia pu` o essere vivo o morto. Per ogni cella l’insieme delle sue celle vicine ` e costituito da quelle celle che si trovano immediatamente sopra, sotto, a sinistra e a destra. Una cella si dice circondata se tutte le celle vicine sono vive. Completare la specifica di gliglia, fornendo la specifica semantica per mezzo di pre e post condizioni (specifica costruttiva o modello astratto), rispetto alla seguente specifica sintattica: domini: gliglia, cella, stato, riga, colonna operatori: (a) creaGriglia() → griglia // crea una nuova griglia senza celle vive (b) inserisciCella(griglia, riga, colonna) → griglia // aggiunge una cella viva nella griglia in posizione (riga,colonna) (c) rimuoviCella(griglia, riga, colonna) → griglia // rimuove una cella viva dalla griglia in posizione (riga,colonna) (d) spostaADestra(griglia, riga, colonna) → griglia // sposta a destra di una posizione una cella viva nella griglia in posizione (riga,colonna) (e) spostaInBasso(griglia, riga, colonna) → griglia // sposta in basso di una posizione una cella viva nella griglia in posizione (riga,colonna) (f) evolve(griglia) → griglia // rimuove dalla griglia tutte le celle circondate [7pt] 2. Fornire in C++ una possibile realizzazione della struttura dati griglia definita al punto 1), riportando 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. Spiegare la realizzazione di grafi mediante matrice di adiacenza e matrice di incidenza, fornendo van- taggi e svantaggi di ognuna…