Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Tema d'esame del 25 Agosto 2021 Esercizio 1 (8 punti, si svolgano solo i punti a e c in caso di riduzione del 30%) Si de niscariconoscitore ad automi gemel li(RAG) un meccanismo di calcolo ottenuto facendo ope- rare due automi sullo stesso nastro di ingresso. Gli automi operano indipendentemente sul nastro di ingresso, ognuno di essi accede al nastro attraverso una propria testina. La parola presente sul nastro di ingresso si considera riconosciuta se e solo se i due automi la riconoscono (non necessa- riamente nello stesso numero di mosse). Si consideri il caso dei RAG costruiti come segue e si dica se il loro potere riconoscitore e maggiore, minore o uguale a quello delle loro componenti: a)RAG costituito da un automa a stati niti deterministico e uno non deterministico; b)RAG costituito da un automa a stati niti deterministico ed un automa a pila deterministico; c)RAG costituito da due automi a pila non deterministici. SoluzioneDettiA 1e A 2gli automi che compongono un dato riconoscitore ad automi gemelli A, si osserva che il riconoscitore ad automi gemelli riconosce il linguaggioL(A) =L(A 1) \L(A 2). E infatti suciente osservare che i due automi che lo compongono operano senza in uenzarsi e la condizione di accettazione richiede che entrambi accettino la parola sul nastro d'ingresso. Si ha quindi che a)Il riconoscitore ad automi gemelli ha la stessa potenza riconoscitiva delle sue componenti: ilinguaggi regolari sono chiusi per intersezione b)Il riconoscitore ad automi gemelli ha la stessa potenza riconoscitiva di un automa a pila deter-ministico. E possibile derivare questo fatto sia dal fatto che i linguaggi liberi dal contesto sono chiusi rispetto all'intersezione con i linguaggi regolari. Alternativamente, e possibile costruire un riconoscitore a pila deterministico equivalente al riconoscitore ad automi gemelli modi cando l' organo di controllo dell'APD per incorporare anche il comportamento dell'automa a stati niti c)Il riconoscitore ad automi gemelli ha potenza riconoscitiva superiore ad un automa a pila de-terministico. E infatti noto che i linguaggi liberi dal contesto non sono chiusi per intersezio- ne. Un esempio di quanto detto e il riconoscitore ad automi gemelli conL(A 1) = an bn c e L(A 2) = a bn cn , conn2N. Esercizio 2 (8 punti, si svolga solo il punto 1 in caso di riduzione del 30%)1.Si consideri la seguente funzione e si dica, motivando adeguatamente la risposta, se essa siacalcolabile: w(x; y) = fy( x) sef y( y) =f x( x)6 =? ?altrimenti 2.Si dica, motivando adeguatamente la risposta, se il seguente insiemeTe ricorsivo: T=fi2NjM ipossiede istati senza transizioni uscentig: 1/3 Soluzione 1.La funzione e calcolabile: una MT che la calcola non deve fare altro che calcolaref y( y) e fx( x): se entrambi terminano, controlla se sono uguali e restituisce il valore opportuno. Se uno dei due non termina, la MT non deve terminare. 2.Te ricorsivo: basta costruireM itramite l'enumerazione E, e contare il numero di stati con la caratteristica richiesta. Esercizio 3 (9 punti, si svolga solo il punto 1 in caso di riduzione del 30%) Si de niscapermutazione bidimensionaleuna funzione biunivoca dall'insiemeSdi tutte le coppie ordinate di numeri interi tra 0 en1, per un dato interon, a se stesso. Si consideri una matriceMquadrata, di laton. Ogni elemento della matrice e una coppia di numeri interi,xey, compresi tra 0 en1. Si interpreti la matrice come una funzionef(x; y) : (x; y)7!M[x; y] conxeyinteri, 0x < n, 0y < n. 1.Si realizzi in pseudocodice un algoritmo a complessita temporale minima che veri ca se unamatriceMrappresenta una permutazione bidimensionale, dimostrandone la minimalita della complessita. 2.Viene dettoorbitain una permutazione un (sotto-)insieme degli elementi permutati tale per cui, applicando iterativamente la permutazione ognuno di essi va ad occupare, via via ad ogni iterazione, il posto di tutti gli altri dell'orbita. Si descriva un algoritmo che determina la dimensione dell'orbita massima della funzione rappresentata da una matriceM, assumendo che essa sia una permutazione bidimensionale. Soluzione 1b o o l v e r i f i c a _ p e r m ( i n t M [ n ] [ n ] ) { 2b o o l v i s t o [ n ] [ n ] = { { f a l s e } } ; 3f o r ( i n t i = 0 ; i < n ; i + + ) { 4f o r ( i n t j = 0 ; j < n ; j + + ) { 5i f ( v i s t o [ M [ i ] [ j ] . x ] [ M [ i ] [ j ] . y ] = = t r u e ) 6r e t u r n f a l s e 7e l s e 8v i s t o [ M [ i ] [ j ] . x ] [ M [ i ] [ j ] . y ] = t r u e 9} 10} 11r e t u r n t r u e 12} La soluzione ha complessitaO(n2 ), minima in quanto e necessario almeno leggere l'intera matrice in input allo scopo di veri care la biiettivita della funzione rappresentata. 1b o o l o r b i t a _ m a x ( i n t M [ n ] [ n ] ) { 2i n t o r b i t a , o r b i t a m a x = 0 ; 3b o o l v i s t o [ n ] [ n ] = { { f a l s e } } ; 4f o r ( i n t i = 0 ; i < n ; i + + ) { 5f o r ( i n t j = 0 ; j < n ; j + + ) { 2/3 6 i f ( v i s t o [ M [ i ] [ j ] . x ] [ M [ i ] [ j ] . y ] = = f a l s e ) { 7i n t c u r r _ i = M [ i ] [ j ] . x ; 8i n t c u r r _ j = M [ i ] [ j ] . y ; 9i n t o r b i t a = 1 ; 10w h i l e ( ! ( c u r r _ i = = i & & c u r r _ j = = j ) ) { 11v i s t o [ M [ c u r r _ i ] [ c u r r _ j ] . x ] [ M [ c u r r _ i ] [ c u r r _ j ] . y ] = t r u e ; 12i n t t m p = c u r r _ i ; 13c u r r _ i = M [ c u r r _ i ] [ c u r r _ j ] . x ; 14c u r r _ j = M [ t m p ] [ c u r r _ j ] . y ; 15o r b i t a + + ; 16} 17i f ( o r b i t a > o r b i t a _ m a x ) { 18o r b i t a _ m a x = o r b i t a ; 19} 20} 21} 22} 23r e t u r n t r u e 24} La soluzione ha complessitaO(n2 ), sfruttando il fatto che ogni elemento puo appartenere ad una sola orbita a causa della biunivocita della permutazione. Come sopra, la complessita e minima in quanto e necessario almeno leggere l'intera matrice in input allo scopo di veri care a quale orbita appartenga ciascuno degli elementi. E' possibile ottenere un guadagno (costante) arrestando la ricerca dell'orbita massima quando gli elementi ancora da ispezionare sono in numero minore di quelli dell'orbita massima trovata no a quel punto. Esercizio 4 (7 punti) Si descriva in maniera esauriente una MT a nastro singolo che accetti il linguaggiofai bi +j aj ji > 5; j >3ge se ne valutino la complessita temporale e spaziale. SoluzioneUna macchina per il linguaggio richiesto puo procedere in questo modo: fa varie passate da sinistra verso destra, cancellando, appena le trova, unaapoi unab. Usando gli stati dell'organo di controllo, la macchina puo assicurarsi che il numero delle passate sia maggiore di 5. Finite lea a sinistra, la macchina procede con passate analoghe da sinistra verso destra, cancellando pero ad ogni passata unabed unaa. Come prima, usando gli stati dell'organo di controllo, la macchina puo assicurarsi che il numero di queste passate sia maggiore di 3.Sianla lunghezza della stringa in ingresso. Complessita spaziale:O(n) (non viene usata altra memoria), complessita temporale:O(n2 ) (ad ogni passata, lunga al piun, si eliminano 2 simboli). 3/3