25 06 2013

Page 1

Algoritmi e Principi dell’Informatica Appello del 25 Giugno 2013 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 3 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2, in 1 ora e 30 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3, 4, 5 in 1 ora e 30 minuti. NB: i punti attribuiti ai singoli esercizi hanno se nso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 7) Nel gioco Reversi ci sono due giocatori (“bianco” e “nero”), ciascun o dotato di 32 dischi bicolori (neri da un lato, bianchi dall'altro) da p iazzare su una scacchiera di 8x8 caselle inizialmente vuota. Si muove alternativamente (inizia il nero) piazzand o ogni volta un nuovo disco (girato dalla parte del proprio colore) in una casella vuota. Se tra il disco appena piazzato e quelli del proprio colore già presenti sulla scacchiera sono p resenti orizzontalmente, verticalmente o diagonalmente solo dischi avversari senza caselle v uote nel mezzo, tali dischi vengono rovesciati e diventano del colore di chi ha eseguit o la mossa. La figura sottostante mostra un esempio di mossa del nero che produce il rovesciamento di un disco bianco. Per semplicità rispetto alla versione ufficiale del gioco, si assuma che sia sempre possibile muovere, ossia piazzare nuovi dischi, fino a che la scacchiera non sia piena. A fine partita, vince il giocatore con il maggior numero di dischi del proprio colore. Scopo dell’esercizio è specificare alcune (non tutte!) regole del gioco mediante formule del prim’ordine. Si considerino i predicati seguenti, che fanno rife rimento al tempo (discreto) in cui avviene una mossa (ossia al numero d’ordine della mossa all’interno della…