Informatica - Algoritmi e strutture dati

Full exam

Algoritmi e Strutture Dati 16/17 Durata: 3 ore Prova Scritta del 19 Gennaio 20171. Si vuole progettare una struttura dati per la memorizzazione di una griglia, di nrighe edmcolonne, cosituita da celle. Lo stato di ogni cella nella griglia puo esserevivoomorto. 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 dicecircondatase tutte le celle vicine sono vive. Completare la specica digliglia, 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: gliglia, cella, stato, riga, colonna operatori: (a) creaGriglia()!griglia //crea una nuova griglia senza cel le vive (b) inserisciCella(griglia, riga, colonna)!griglia //aggiunge una cel la viva nel la griglia in posizione (riga,colonna) (c) rimuoviCella(griglia, riga, colonna)!griglia //rimuove una cel la viva dal la griglia in posizione (riga,colonna) (d) spostaADestra(griglia, riga, colonna)!griglia //sposta a destra di una posizione una cel la viva nel la griglia in posizione (riga,colonna) (e) spostaInBasso(griglia, riga, colonna)!griglia //sposta in basso di una posizione una cel la viva nel la griglia in posizione (riga,colonna) (f ) evolve(griglia)!griglia //rimuove dal la griglia tutte le cel le circondate[7pt] 2. Fornire in C++ una possibile realizzazione della struttura dati griglia denita al punto 1), riportandola 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. Spiegare la realizzazione di gra mediante matrice di adiacenza e matrice di incidenza, fornendo van-taggi e svantaggi di ognuna [4pt] 4. Fornire in pseudocodice l'algoritmo di ricerca di ampiezza (BFS) per gra, motivando l'utilizzo di altrestrutture dati per la sua implementazione [3pt] 5. Spiegare il concetto dicol lisionee le corrispondenti tecniche di gestione perdizionari[5pt] 6. Fornire la specica diproblema di ottimizzazione[3pt] 7. Facendo riferimento ad uno specico problema di ricerca spiegare ed illustare l'esecuzione di unastrategia di backtracking applicata ad una istanza di quel problema. [7pt] 1