Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Tema d’esame del 29 Giugno 2021 1 Informatica teorica Esercizio 1 (8 punti) a)Scrivere una grammatica a potenza minima che generi il linguaggio seguente: L1= {(bc)m |m≥2} b)Sfruttando la risposta al punto precedente, scrivere una grammatica a potenza minima chegeneri il linguaggio seguente: L2= {bk aℓ (bc)m an bp |k > p,2ℓ=n, m≥2} Soluzione a)` E sufficiente una grammatica regolare, doveS 0`e l’assioma. S0→ bS 1 S1→ cS 2 S2→ bS 3 S3→ c|cS 2 b)` E sufficiente una grammatica non contestuale. Il linguaggio pu`o infatti anche essere pensato nel modo seguente: L2= {bs bp aℓ (bc)m (aa)ℓ bp |s≥1, p≥0, ℓ≥0, m≥2} S→U V U→bU|b1 o pi`ub V→bV b|Wgeneriamopletterebda ambo i lati W→aW aa|S 0generiamo ℓlettereaa sx e 2ℓa dx doveS 0`e il simbolo iniziale della grammatica per L 1. Esercizio 2 (8 punti) SiaL 1un linguaggio ricorsivamente enumerabile, L 2un linguaggio regolare e L=L 1∩ L 2la loro intersezione. Per ciascuna delle seguenti classi di linguaggi, si argomenti seLpu`o farne parte, deve necessariamente farne parte o non pu`o farne parte: a)linguaggi regolari; b)linguaggi ricorsivi;c)linguaggi ricorsivamente enumerabili. Motivare opportunamente e fornire esempi laddove appropriato. Soluzione 1/3 a)Pu`o farne parte: se L 1`e regolare allora anche L`e regolare (chiusura rispetto a intersezione); ad esempio, seL 1= ∅abbiamoL=∅. Pu`o non farne parte: seL 1non `e regolare e L 2= A∗ , dove A`e l’alfabeto, alloraLnon `e regolare. b)In modo simile al punto precedente, seL 1`e ricorsivo allora anche L`e ricorsivo (chiusura rispetto a intersezione), altrimenti potrebbe non esserlo. La ragione `e cheL 2, essendo regolare, `e anche ricorsivo. c)L`e certamente ricorsivamente enumerabile in quanto intersezione di due linguaggi ricorsiva- mente enumerabili (chiusura rispetto a intersezione), dato cheL 2, essendo regolare, `e anche ricorsivamente enumerabile. 2 Algoritmi e strutture dati Esercizio 3 (8 punti) Si consideri un albero binario di ricercaTcontenentennodi. Si implementino in pseudocodice le seguenti procedure, e se ne analizzi la complessit`a temporale. a)simmetrico(T): La procedura controlla se l’albero ha struttura simmetrica rispetto all’asse verticale passante per la radice. b)gemelli(T): La procedura controlla se i sottoalberi figli della radice hanno la stessa struttura, ovvero se i sottoalberi sono sovrapponibili con una traslazione orizzontale rigida. c)stampastrati(T) : La procedura stampa il contenuto dell’albero per livelli, a partire dalla radice, stampando i nodi di ogni livello da sinistra a destra. Soluzione a)simmetrico(T){ return visitas(T.left,T.right) } visitas(L,R){ if ((L == NIL) and (R == NIL))return true if ((L == NIL) or (R == NIL))return false return visitas(L.left,R.right) and visitas(L.right,R.left) } Complessit`a temporale Θ(n). b)gemelli(T){ return visitag(T.left,T.right) } visitag(L,R){if ((L == NIL) and (R == NIL)) return true 2/3 if ((L == NIL) or (R == NIL)) return false return visitag(L.left,R.left) and visitag(L.right,R.right) } Complessit`a temporale Θ(n). c)stampa_strati(T){ if (not (T == NIL)) Q.enqueue(T) while(not Q.is_empty())E = Q.dequeue() print(E) if (not (E.left == NIL)) Q.enqueue(E.left) if (not (E.right == NIL))Q.enqueue(E.right) } Complessit`a temporale Θ(n). Esercizio 4 (8 punti) Si consideri una tabella hash di 1024 elementi, organizzata con indirizzamento aperto. La funzione di hash utilizzata `eh(k) = 4kmod 1024, la sequenza di ispezione `eh′ (k, i) = (4k+ 2i) mod 1024. a)Qual `e il numero massimo di elementi inseribili nella tabella? b)Qual `e la complessit`a attesa di accesso ad un elemento dopo l’inserimento di 256 elementi? (siassuma che la sequenza di ispezione sia tale da rispettare l’ipotesi di hashing uniforme rispetto ai bucket che possono essere raggiunti da essa). Soluzione a)512; la funzione di hash emette unicamente chiavi multiple di 4 e la sequenza di ispezione procedea passo 2. Tutti i bucket della tabella con indice dispari saranno sicuramente inutilizzati. b)Data la funzione di hash e sequenza di ispezione, la tabella `e equivalente ad una con 512bucket. Abbiamo quindi che il numero di tentativi medi prima di accedere ad un elemento `e (256512 )− 1 log(11 −256512 ) ≈1,38. 3/3