Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Prima Prova in Itinere (modulo Informatica teorica) 27 Aprile 2018 Il tempo a disposizione è di 1 or a e 30 minuti. Esercizio 1 ( Punti 6/15 ) a. Si progetti un automa o una grammatica (solo uno dei due!) a potenza minima che riconosca/generi il linguaggio L 1 = { (1 2n 0 2n 1 n 0 n ) m | n=1, m>0 } . b. Si consideri ora il linguaggio L 2 = { (1 2n 0 2n 1 n 0 n ) m | n>0, m>0 } , che comprende, ad esempio, le stringhe 110010 , 110010110010 e 111100001100111100001100, mentre non comprende le stringhe 1 0 101 1 0 01 1 0 0 , 110010111100001100 e 11110000110011001010 . S i indichi, motivando opportunamente la risposta, l a classe di automi/grammatiche a potenza minima che riconosca/generi L 2 . Non serve for nire l’automa o la grammatica. Esercizio 2 (Punti 6 /15 ) Si consideri un segnale su tempo continuo ad onde quadre "semiperiodico" a valore 0 o 1. Per semiperiodico si intende che esso alterna onde di durata T ad onde di durata T/2. Più precisamente, la fo rma del segnale è esemplificata nella figura 1 sottostante. Figura 1: segnale a forma quadra a periodo T (per onde dispari) o T/2 (per onde pari) . Le onde dispari hanno durata T, in cui la prima semionda, di durata T/2, vale 1 e la seconda 0 . Le onde pari hanno periodo T/2 e sono anch'esse divise in due semionde di uguale durata T/4. Si specific h i il comportamento del segnale così descritto mediante una formula logica del prim'ordine. Sono consentiti i seguenti simboli , da non specificare ulte riormente : • la funzione S ( t ) , che restituisce il valore del segnale (0 o 1) al tempo t ; • il predicato int ( n ) , che specifica che il va lore della variabile n è un intero non negativo ; • la costante T ; • costanti intere (0, 1, …), operazioni aritmetiche (+, - , ⋅ , / ) e comparatori (< , =, £ , …) . Esercizio 3 (punti 6 /15 ) 1. Si consideri la funzione g(y ) = if f y (y) = y then y+1 else f y (y) . Si dica se g è totale e se è calcolabile, motivando adeguatamente la risposta. 2. Sia A un insieme semidecidibile e B un insieme decidibile. E' facile verificare che l'insieme C = A - B è un insieme semidecidibile: si fornisca all'uopo una funzione calcolabile (eventualmente anche parziale) che abbia come immagine C. � �� �� �� � � �/�� /�� /�� /�� /�� /�� /�� /�� /�� /� Tracce di soluzioni Esercizio 1 Il linguaggio L 1 è generato dalla seg uente grammatica regolare: S - > 1A A - > 1B B - > 0C C - > 0D D - > 1E E - > 0S | 0 e riconosciuto dal seguente automa a stati finiti: Nel caso di L 2 , invece, n è arbitrario e occorre ricontarlo più di una volta, come nel caso del lin g uaggio a n b n c n . Come noto, per questi linguaggi è richiesta la potenza di una macchina di Turing (o di una grammatica generale). E sercizio 2 " t ( " n ( int ( n ) Ù t = n ⋅ 3 / 2 ⋅ T ) ® ( " t 1 ( t < t 1 £ t + T / 2 ® S ( t 1 ) = 1) Ù " t 1 ( t +T / 2 < t 1 £ t + T ® S ( t 1 ) = 0)) Ù ( " t 1 ( t + T < t 1 £ t + 5/ 4 ⋅ T ® S ( t 1 ) = 1) Ù " t 1 ( t + 5 / 4 ⋅ T < t 1 £ t + 3 / 2 ⋅ T ® S ( t 1 ) = 0)) ) Esercizio 3 1) g è parziale e calcolabile: basta simulare la MT y con y in ingresso. Se essa termina, si controlla il risultato t e, se esso è y, si somma 1; altrimenti va bene t, anche se non dovesse essere definito. 2) g C (x) = if c B (g A (x)) = 0 then g A (x) else ^ q 0 q 1 q 2 q 3 q 4 q F1100q 5101