16 07 2015

Page 1

Algoritmi e Prin Informatica Appello del 16 Luglio 2015 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singol i esercizi hanno senso solo con hanno valore puramente indicativo. Esercizio 1 (punti 8) Scrivere una grammatica a potenza minima che generi il linguaggio { anbmcl | n m o n l } In alternativa è possibile costruire un automa, sempre a potenza minima, che riconosca lo stesso linguaggio; ciò però comporta una diminuzione del punteggio ottenibile di 2 punti. Esercizio 2 (punti 8) Parte a È decidibile stabilire se una macchina di Turing M entra più di una volta in un qualche stato organo di controllo quando riceve in input una stringa w? In altre parole: Indicata con <M> la codifica di una MT M e con <w> quella di una alfabeto di input di M, si dica se è computabile la funzione F(<M>, <w>) = 1, se quando M opera su w esistono due configurazioni di M 0 altrimenti Parte b È controllo) entra più di una volta nello stato iniziale dell'organo di controllo quando riceve in input una stringa w? In altre parole: Indicata con <M> la codifica di una MT M, con <w> quella di una stringa sull'alfabeto di input di M e con q 0 lo stato iniziale dell'organo di controllo di M, si dica se è computabile la funzione F(<M>, <w>) = 1, se quando M opera su w esistono due configurazioni di M i 0 0 altrimenti Giustificare brevemente le risposte date. Esercizio 3 (punti 10) Dato un albero binario di ricerca T , i cui nodi memorizzano una variabile che ne rappresenta il colore, si vuole determinare se T è un albero Rosso-Nero. Si definisca un algoritmo che risolva questo problema…