Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Tema d'esame del 20 Gennaio 2022 Esercizio 1 (8 punti). Si consideri la seguente grammatica: G=8 > > > > < > > > > :S !C BSjC SjBSja C B!BC C C!c BB!b a)Che tipo di grammatica eG? b)Che linguaggio generaG? c)Si scriva un automa a potenza minima che accetti il linguaggio generato daG. Soluzione a)La grammatica e di tipo non ristretto. b)Il linguaggio generato daGe regolare; in particolare e quello rappresentato dall'espressione regolare (bjc) a. c)L'automa a potenza minima che riconosceL(G) e il seguente automa a stati niti:q 0q 1a b,c Esercizio 2 (8 punti). Si consideri una macchina di Turing universaleMssata, a nastro singolo. Sia  l'alfabeto del nastro diM. a) E calcolabile la funzionef:( 1 seM(s)6 =? 0 seM(s) =?che riceve in ingresso una qualunque stringa s2S 100 i=0i ? b) E calcolabile la funzioneg:( 1 seM(s)6 =? ?seM(s) =?che riceve in ingresso una qualunque stringa s2S i=2k;k2Ni ? Soluzione 1/3 a)S. Il dominio della funzione da calcolare e nito, quindi essa e rappresentabile da una ta- bella di dimensioni nite, contenente la corrispondenza ingresso-uscita tra la stringased il comportamento della macchinaMquandosviene data in ingresso. b)S, in particolaregpuo essere calcolata emulandoM(s) sino alla sua eventuale terminazione. SeM(s) termina, alloragrestituisce 1, risultando cos conforme al comportamento richiesto. Esercizio 3 (8 punti) Si consideri un vettore dininteri. Si descriva in pseudocodice la procedura che ordina il vettore in ordine crescente in base al valore del resto della divisione di ognuno degli elementi per 4. Elementi con lo stesso valore di resto della divisione possono trovarsi in qualunque ordine tra loro. Il vettore ordinato avra quindi alla sua estrema sinistra tutti gli elementi con resto nullo rispetto alla divisione per quattro, seguiti da tutti quelli aventi resto 1, a loro volta seguiti da tutti quelli aventi resto 2, ed inne da tutti gli elementi aventi resto 3. La procedura di ordinamento deve avere complessita temporaleO(n) e complessita spaziale O(1). Soluzione 1v o i d o r d i n a _ m o d _ 4 ( i n t * a , i n t l e n ) { 2i n t d s t _ i d x = 0 , t m p ; 3f o r ( i n t r e s t o = 0 ; r e s t o < 3 ; r e s t o + + ) { 4f o r ( i n t p o s = 0 ; p o s < l e n ; p o s + + ) { 5i f ( a [ p o s ] % 4 = = r e s t o ) { 6t m p = a [ p o s ] ; 7a [ p o s ] = a [ d s t _ i d x ] ; 8a [ d s t _ i d x ] = t m p ; 9d s t _ i d x + + ; 10} 11} 12} 13} Esercizio 4 (8 punti). Si voglia indicare con la notazionef(O(n)) l'insieme di funzioniff(g(n))jg(n)2 O(n)g. Si valuti la validita di ciascuna delle seguenti espressioni, giusticando le proprie risposte: a)log(O(n)) =O(log(n)) b)2O (n) =O(2n ) c)(O(n))k =O(nk ) Soluzione a)Falsa. Si consideri ad esempiof(n) = 2 log(n). Abbiamo chiaramente chef(n)2 O(log(n)). Tuttaviaf(n)= 2log(O(n)), cioe non e vero chef(n) e una funzione della forma log(g(n)), con g(n)2 O(n); infattif(n) = log(n2 ) en2 = 2 O(n). 2/3 b)Falsa. Si prenda f(n) = 2n: certamentef(n)2 O(n), quindi 2f (n) 22O (n) , ma 2f (n) = 22 n = 2 O(2n ). c)Vera. L'insiemeO(n) e dato dalle funzionigper cui esistonoc >0; n 0> 0 tali cheg(n)cnper n > n0. Anche ( g(n))k 2 O(nk ) devono allora esisterec0 >0; n0 0> 0 tali che (g(n))k c0
nk pern > n0 0, che e senz'altro vericata per c0 opportuno en0 0= n 0. Infatti, per n > n 0, g(n)cn e quindi (g(n))k (cn)k c0
nk sec0 > ck . L'altra direzione e analoga: siahuna funzione inO(nk ), cioe tale per cui esistonoc >0; n 0> 0 tali cheh(n)cnk pern > n 0. Anche valga h(n)2 O(n)k si deve mostrare che esiste una funzioneg(n)2 O(n) tale che valeh(n) =g(n)k . Tale funzione ek ph (n): si ha infatti che k ph (n)2 O(n), poichek ph (n)k pcn pern > n 0. 3/3