Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 G9B9R9V9b9A9 (dove G sta per giallo, B per bianco, ecc.) rappresenta un cubo risolto. All’inizio dell’esecuzione della MdR, il cubo è risolto. Una stringa letta dal nastro di ingresso viene accettata dalla MdR se e solo se alla fine della sua scansione la macchina è in uno stato finale e il cubo è risolto. 1) Qual è il linguaggio L riconosciuto dalla macchina di Rubik seguente? Nome:_________________________________________________ Matricola:____________________________________________ Firma:_________________________________________________ 2) Si confronti il potere espressivo della MdR con quello degli automi visti a lezione. Esercizio 2 (punti 5) Si specifichi in logica del prim’ordine che ogni funzione computabile è calcolata da infinite macchine di Turing (MT). Per la specifica si può fare uso della funzione binaria calc(i,x) (che indica il valore calcolato dalla MT con indice i a fronte dell’ingresso x) e si possono inoltre usare i predicati di confronto tra numeri (=, >, i ∧ ∀x calc(i,x)=calc(j,x) ) Esercizio 3 E’ decidibile ed è anche deciso. Infatti, poiché L è riconosciuto da una MdR, esso è necessariamente riconosciuto anche da un automa a stati finiti e quindi necessariamente anche da una macchina di Turing. Inoltre, è noto che, per una macchina di Turing data, ne esistono infinite altre ad essa equivalenti.