API 2016 02 01

Page 1

Algoritmi e Principi dell'Informatica Appello d’esame 1 febbraio 2016 Esercizio 1 (punti 7) Si consideri un’estensione degli automi a stati finiti deterministici (come riconoscitori di linguaggi), detta Macchina di Rubik, in cui è presente un dispositivo di memoria basato sul famoso cubo di Rubik. Il Cubo di Rubik (CdR). E’ un cubo composto da una griglia di 3x3x3=27 cubetti, di cui, a seconda della posizione nel cubo, sono visibili 0, 1, 2 o 3 facce dette “quadretti” (vedi figura). Il CdR presenta quindi 9 quadretti su ognuna delle sue 6 facce, per un totale di 54 quadretti. I quadretti differiscono tra loro per il colore, con un totale di 6 colori differenti (Giallo, Bianco, Rosso, Verde, blu, Arancione). Ciascuna faccia può essere ruotata di 90° in senso orario o antiorario come mostrato in figura. In questo modo, il cubo può assumere oltre 1019 combinazioni possibili. Il cubo si dice risolto quando in ogni faccia i quadretti sono tutti dello stesso colore. La Macchina di Rubik (MdR). Nella MdR (dotata di stati e transizioni come ogni automa a stati), ogni transizione è associata a una “mossa” da compiere sul cubo. Una mossa sul cubo è una rotazione di 90° di una faccia, identificata da una lettera che ne rappresenta la posizione relativa nel cubo (Alto, Basso, Destra, Sinistra, Fronte, Retro) e dal senso di rotazione (orario: P, antiorario: Q). Nel diagramma degli stati, ogni arco è quindi dotato di un’etichetta del tipo i / f, s dove i denota un simbolo letto dall’ingresso, f ∈ {A, B, D, S, F, R} denota una faccia, e s ∈ {P, Q} denota un senso di rotazione della faccia. La configurazione del cubo è rappresentata da una stringa di 54 simboli, 9 per faccia, ciascuno dei quali rappresenta ordinatamente il colore delle caselle della faccia. Ad esempio, la stringa…