Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Soluzioni al Tema d'esame26 Giugno 2020 1 Informatica teorica Esercizio 1 (prima variante) Si consideri l'alfabetoA=fd; s; tge il linguaggioLdi tutte e sole le stringhe suAche soddisfano i requisiti seguenti: 1.ogni stringa inizia con un pre sso che puo essere la stringa vuota, la stringa d o la stringa ds; 2.dopo il pre sso, c'e la sequenza tds ripetuta un numero arbitrario di volte (anche nessunavolta); 3.in ne, la stringa si chiude con la sequenza ts; 4.la sequenza dtd non appare mai all'interno della stringa; 5.la stringa contiene tutti e tre i simboli alfabetici. Esempi di stringhe appartenenti al linguaggio sono: dts, dsts, tdsts, dstdsts, tdstdsts. Esempi di stringhe non appartenenti al linguaggio sono: ddts, dtdsts, ts, d.Scrivere una grammatica a potenza generativa minima che generi L. Soluzione Basta una grammatica regolare. Il vincolo 5 impone che, in caso di pre sso vuoto, la sequenza tds sia ripetuta almeno una volta. Il vincolo 4 signi ca che, in caso di pre sso d, la sequenza tds sia ripetuta zero volte. L'espressione regolare corrispondente a L e la seguente:dtsj((tdsjds)(tds) ts) Una grammatica regolare e come segue: S!AjBjC A!tB B!dD D!sAjsL C!dL L!tM M!s Un modo equivalente per risolvere l'esercizio e di iniziare con una grammatica non regolare che genera il linguaggio:S!dtsjtdsRjdsR R!tdsRjts e di trasformarla in una grammatica regolare evitando le sequenze di terminali: 1/6 S !tS1jdS6 S1!dS2 S2!sS3 S3!tS4jtS7 S4!dS5 S5!sS3 S6!tS3jtS7 S7!s Esercizio 1 (seconda variante)Testo e soluzione sono come nella prima variante, dopo aver opportunamente sostituitotcon f,sconqedconr. Esercizio 2 (prima variante)Per ciascuno dei seguenti insiemi si stabilisca, fornendo un'opportuna motivazione, se e ricorsivo. S 1= fijie un numero primog S 2= fijie un numero primo minore di100g S 3= fijie l'indice di una macchina di Turing che stabilisce se il suo ingresso e un numero primog S 4= fijie un indice, minore di 100, di una macchina di Turing che stabilisce se il suo ingresso e un numero primog S 5= fijie l'indice di una macchina di Turing con un numero dispari di statig S 6= fijie un indice, minore di 100, di una macchina di Turing con un numero dispari di statig Soluzione S2, S 4e S 6sono ricorsivi in quanto niti. S1e ricorsivo perche la sua funzione caratteristica e computabile (deve stabilire se un numero e primo, il che e decidibile).S3non e ricorsivo per il teorema di Rice (all'insieme F=ffg, dovefe la funzione che stabilisce se il suo argomento e primo o meno, si applicano le condizioni del teorema). S5e ricorsivo. Si noti che avere un numero dispari di stati non e una proprieta della funzione calcolata dalla macchina, quindi non si puo applicare il teorema di Rice. Basta ispezionare il diagramma degli stati ricavato in questo modo per stabilire se il numero di stati e pari o dispari. Esercizio 2 (seconda variante)Per ciascuno dei seguenti insiemi si stabilisca, fornendo un'opportuna motivazione, se e ricorsivo. S 1= fijie un numero pari scrivibile con 10 bit in notazione binariag S 2= fijie un numero parig S 3= fijie un indice, scrivibile con 10 bit in notazione binaria, di una macchina di Turing con 2/6 un numero primo di stati g S 4= fijie l'indice di una macchina di Turing con un numero primo di statig S 5= fijie un indice, scrivibile con 10 bit in notazione binaria, di una macchina di Turing che stabilisce se il suo ingresso e un numero parig S 6= fijie l'indice di una macchina di Turing che stabilisce se il suo ingresso e un numero parig Soluzione S1, S 3e S 5sono ricorsivi in quanto niti. S2e ricorsivo perche la sua funzione caratteristica e computabile (deve stabilire se un numero e pari, il che e decidibile).S4e ricorsivo. Si noti che avere un numero primo di stati non e una proprieta della funzione calcolata dalla macchina, quindi non si puo applicare il teorema di Rice. Basta usare l'enumerazione algoritmica delle macchine di Turing e ispezionare il diagramma degli stati ricavato in questo modo per stabilire se il numero di stati e primo o meno.S6non e ricorsivo per il teorema di Rice (all'insieme F=ffg, dovefe la funzione che stabilisce se il suo argomento e pari o meno, si applicano le condizioni del teorema). 2 Algoritmi e strutture dati Esercizio 1 (prima variante) Calcolare i limiti di complessita asintotica per le seguenti ricorrenze: 1.T(n) = 16T(n2 ) + ( n2 ) 2.T(n) = 8T(n3 ) + ( n3 ) 3.T(n) =nT(n3) + (1) Soluzione 1.Si nota che la ricorrenza rispetta le ipotesi del Master theorem; logb( a) = log 2(16) = 4, si ha quindi chen4 " =n2 per"= 2 (Master theorem, caso 1, nessuna ipotesi aggiuntiva). La ricorrenza e quindi (n4 ). 2.Come sopra, la ricorrenza rispetta le ipotesi del Master theorem. logb( a) = log 3(8) 1;893, conf(n) =n3 , ci troviamo nel terzo caso. La condizione di regolarita e automaticamente rispettata poiche nella ricorrenza il terminef(n) e del tipo (nk ) (quik= 3). La ricorrenza e quindi (n3 ). 3.Con l'albero di ricorsione si arriva facilmente a osservareT(n) =O(n!), che poi si puo mostrare per induzione. Un limite piu stretto si puo ottenere espandendo la ricorrenza come 3/6 segue: T(n) =nT(n3) + (1) =n((n3)T(n6) + (1)) + (1) = (n2 3n)T(n6) + (n) + (1) = (n2 3n)((n6)T(n9) + (1)) + (n) + (1) = (n3 9n2 + 18n)T(n9) + (n2 ) + (n) + (1) La ricorsione e profondan=3 passi e a ogni passo si aumenta di 1 il grado del polinomio. La complessita nale eO(nn= 3 ). Esercizio 1 (seconda variante) Calcolare i limiti di complessita asintotica per le seguenti ricorrenze: 1.T(n) = 81T(n3 ) + ( n3 ) 2.T(n) = 6T(n2 ) + ( n3 ) 3.T(n) =nT(n4) + (1) Soluzione 1.Si nota che la ricorrenza rispetta le ipotesi del Master theorem; logb( a) = log 3(81) = 4, si ha quindi chen4 " =n3 per"= 1 (Master theorem, caso 1, nessuna ipotesi aggiuntiva). La ricorrenza e quindi (n4 ). 2.Come sopra, la ricorrenza rispetta le ipotesi del Master theorem. logb( a) = log 2(6) 2;58, conf(n) =n3 , ci troviamo nel terzo caso. La condizione di regolarita e automaticamente rispettata poiche nella ricorrenza il terminef(n) e del tipo (nk ) (quik= 3). La ricorrenza e quindi (n3 ). 3.Con l'albero di ricorsione si arriva facilmente a osservareT(n) =O(n!), che poi si puo mostrare per induzione. Un limite piu stretto si puo ottenere espandendo la ricorrenza come segue: T(n) =nT(n4) + (1) =n((n4)T(n8) + (1)) + (1) = (n2 4n)T(n8) + (n) + (1) = (n2 4n)((n8)T(n12) + (1)) + (n) + (1) = (n3 12n2 + 32n)T(n12) + (n2 ) + (n) + (1) La ricorsione e profondan=4 passi e a ogni passo si aumenta di 1 il grado del polinomio. La complessita nale eO(nn= 4 ). 4/6 Esercizio 2 (prima variante) Si consideri una matrice quadrata di numeri interi positivi, avente laton. La matrice contiene numeri interi ordinati in ordine crescente lungo ogni riga e ordinati in ordine decrescente lungo ogni colonna colonna.Si descriva un algoritmo di ricerca di un valore intero dato all'interno della matrice stessa, avente minime complessita temporale e spaziale. Soluzione E' possibile individuare il valore cercato, o determinare l' assenza, inO(n) tempo eO(1) spazio. La soluzione si basa sul fatto che che la matrice, ordinata in questo modo, ora la possibilita di eettuare una ricerca considerando che tutti gli elementi in una riga successiva siano minori del corrente, e tutti quelli in una colonna successiva maggiori di esso. 1# i n c l u d e < s t d i o . h > 2# i n c l u d e < s t d l i b . h > 3# d e f i n e N 3 4 5i n t m a i n ( i n t a r g c , c h a r * a r g v [ ] ) { 6 7i n t M [ N ] [ N ] = { { 7 , 8 , 1 5 } , 8{ 5 , 6 , 1 2 } , 9{ 1 , 4 , 9 } } ; 10 11i n t r i g a = 0 , c o l = 0 ; 12i n t t o _ f i n d ; 13t o _ f i n d = a t o i ( a r g v [ 1 ] ) ; 14w h i l e ( ( r i g a < N ) & & ( c o l < N ) ) { 15i f ( M [ r i g a ] [ c o l ] = = t o _ f i n d ) { 16p r i n t f ( " f o u n d a t ( % d , % d ) \ n " , r i g a , c o l ) ; 17r e t u r n 0 ; 18} 19i f ( t o _ f i n d > M [ r i g a ] [ c o l ] ) { 20c o l + + ; 21} e l s e { 22r i g a + + ; 23} 24} 25p r i n t f ( " N o t f o u n d \ n " ) ; 26r e t u r n 1 ; 27} Esercizio 2 (seconda variante) Si consideri una matrice quadrata di numeri interi positivi, avente laton. La matrice contiene numeri interi ordinati in ordine decrescente lungo ogni riga e ordinati in ordine crescente lungo ogni colonna colonna.Si descriva un algoritmo di ricerca di un valore intero dato all'interno della matrice stessa, avente minime complessita temporale e spaziale. 5/6 Soluzione E' possibile individuare il valore cercato, o determinare l' assenza, inO(n) tempo eO(1) spazio. La soluzione si basa sul fatto che che la matrice, ordinata in questo modo, ora la possibilita di eettuare una ricerca considerando che tutti gli elementi in una riga successiva siano minori del corrente, e tutti quelli in una colonna successiva maggiori di esso. 1# i n c l u d e < s t d i o . h > 2# i n c l u d e < s t d l i b . h > 3# d e f i n e N 3 4 5i n t m a i n ( i n t a r g c , c h a r * a r g v [ ] ) { 6 7i n t M [ N ] [ N ] = { { 7 , 8 , 1 5 } , 8{ 5 , 6 , 1 2 } , 9{ 1 , 4 , 9 } } ; 10 11i n t r i g a = 0 , c o l = 0 ; 12i n t t o _ f i n d ; 13t o _ f i n d = a t o i ( a r g v [ 1 ] ) ; 14w h i l e ( ( r i g a < N ) & & ( c o l < N ) ) { 15i f ( M [ r i g a ] [ c o l ] = = t o _ f i n d ) { 16p r i n t f ( " f o u n d a t ( % d , % d ) \ n " , r i g a , c o l ) ; 17r e t u r n 0 ; 18} 19i f ( t o _ f i n d > M [ r i g a ] [ c o l ] ) { 20r i g a + + ; 21} e l s e { 22c o l + + ; 23} 24} 25p r i n t f ( " N o t f o u n d \ n " ) ; 26r e t u r n 1 ; 27} 6/6