Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Soluzioni al Tema d'esame8 febbraio 2022 Informatica teorica Esercizio 1 (8 punti) Si consideri il linguaggio sull'alfabeto  =fa; b; c; dgcomposto da tutte e sole le stringhe in cui: 1.compare al piu una solaco una solad, mai entrambe, 2.se compare unac, il numero diaa sinistra dellace uguale a quello diba sinistra dellac; idem a destra dellac; 3.se compare unad, il numero diaa sinistra dellade uguale al doppio di quello delleba sinistra dellad; idem a destra dellad; 4.Nel caso in cui non compaianocod, il numero diaebe arbitrario. Si fornisca una grammatica a potenza minima che genera il linguaggio descritto. Soluzione Una grammatica a potenza minima (libera dal contesto) che genera il linguaggio e la seguente:S!AjBjC A!aAjbAj" B!B0 cB0 B0 !aB0 bB0 jbB0 aB0 j" C!C0 dC0 C0 !aC0 aC0 bC0 jaC0 bC0 aC0 jbC0 aC0 aC0 j" Esercizio 2 (8 punti) Uno statoqdi una macchina di TuringMviene dettoutilese esiste una stringawtale per cuiqviene raggiunto durante l'esecuzione diMquandowsi trova in ingresso, ovvero, dettoq 0lo stato iniziale diM,qe utile se9w; x; y;  1; : : :  k;  1; : : : ;  kh q 0; "w;"Z 0; : : : ; "Z 0i ` Mh q; x"y;  1"  1; : : : ;  k"  ki , conx
y=w. 1. E decidibile stabilire, data una macchina di TuringMe un suo statoq, seqsia utile? 2. E semidecidibile il problema di cui sopra? Soluzione 1.Il problema e indecidibile. Se fosse decidibile potremmo infatti decidere anche il problema dellaemptiness(cioe il problema di stabilire se il linguaggio accettato e vuoto) per una generica macchinaM; la emptiness e notoriamente indecidibile (e se ne puo ricavare immediatamente l'indecidibilita anche mediante il teorema di Rice). Infatti, basterebbe decidere se lo stato nale diMe utile (o almeno uno degli stati nali diM, nel caso ce ne sia piu di uno) per stabilire se Maccetta almeno una stringa o meno. 2.Il problema e semidecidibile, poiche, mediante una enumerazione diagonale (dovetailing) di tutte le possibili coppiehw; ii(dovewe la stringa in ingresso eie il numero di passi di esecuzione 1/2 di Mtestati, ad esempio, mediante emulazione), ci si puo accorgere se, prima o poi, lo statoq venga raggiunto. Algoritmi e strutture dati Esercizio 3 (8 punti) Si consideri il seguente linguaggio su alfabeto  =fa; b; cg: L=fw:w:c:xjw2 fa; bg+ ;jwj 49; x2+ g: Si descriva una MT a nastro singolo che lo accetti, valutandone le complessita spaziali e temporali. Soluzione Il linguaggio e regolare, essendowdi lunghezza limitata. La MT potra usare l'organo di controllo per assicurarsi che i primi 98 caratteri (al piu) della stringa siano compatibili con il linguaggio, dovra poi controllare che vi sia unacseguita da un carattere qualunque per accettare. Quindi la macchina fara al piu 100 passi, cioeT(n) = (1);S= (n), visto che comunque la memoria sara occupata dalla stringa in ingresso. Esercizio 4 (8 punti) Si considerino le seguenti funzioni: 1f u n c 1 ( n ) 2k : = 0 3i : = 0 4w h i l e in 5k : = k + 1 6i : = i + k 7( * ) 8r e t u r n k1 f u n c 2 ( m ) 2i f m1 3r e t u r n m 4j : = 1 5w h i l e jm 6j : = j * 3 7r e t u r n f u n c 2 ( m / 3 ) + f u n c 2 ( m / 3 ) Si calcoli la complessita difunc1(n)quando al posto di(*)si trovano le seguenti istruzioni: 1.func2(105 ); 2.func2(n). Soluzione Il valore diiall'inizio dellaj-esima iterazione del ciclo infunc1non e mai in uenzato dall'e- secuzione della funzionefunc. Esso e pari a 1 + 2 + 3 + 4 + 5 +:::+ (j1), e quindi e dell'ordine dij2 . Quindi, il ciclo viene eseguito un numero di volte pari apn . Calcoliamo innanzi tutto la complessita difunc2(m). Essa e data dalla seguente ricorsione: T(m) = 2T(m3 ) + log 3( m). La ricorsione si risolve tramite il Master Theorem, in quanto log 3( m) e polinomialmente piu piccola dimlog 3(2) . Siamo quindi nel caso 1 del Master Theorem, e la complessita difunc2(m)e (mlog 3(2) ). Nel caso 1 l'istruzione(*)ha costo costante, indipendente dan. Quindi, in questo caso la compessita del codice e data dal numero di iterazioni del ciclo, ed e dell'ordine dipn . Nel caso 2 a ogni iterazione del ciclo il costo dell'istruzione(*)e dell'ordine dinlog 3(2) , quindi il costo totale e dell'ordine din( 12 + log 3(2)) . 2/2