Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
Algoritmi e Principi dell'Informatica Prima Prova in Itinere 25 Novembre 2013 Avvisi importanti Il tempo a disposizione è di 1 ora e 30 minuti. Se non verranno r isolti in maniera soddisfacente gli esercizi 1, 2, 3 (ossia ottenendo almeno 2 punti in ognuno di essi) non si procederà alla correzione dell'esercizio 4. Chi otterrà una valutazione inferiore a 6/15 -esimi non potrà sostenere la seconda prova e potrà iscriversi soltanto al secondo appello della sessione invernale. Esercizio 1 (punti 3/15-esimi) Dire se esiste un automa a stati finiti che riconosce il seguente linguaggio: L = {anbncn | n > 2} {a*b*c*} Spiegare brevemente la risposta. Esercizio 2 (punti 3/15-esimi) Quale delle seguenti formule definisce correttamente i numeri di Fibonacci? (si ricorda che l -esimo numero di Fibonacci -1)- -2)-esimo, per n > 1, mentre per n = 0 o 1 ha in valore convenzionale 0 e 1, rispettivamente.) ) n((n=0 fib(n) = 0) (n=1 fib(n) = 1) (n > 1 fib(n) = fib (n-1) + fib(n-2))) ) n((n=0 fib(n) = 0) (n=1 fib(n) = 1) (n > 1 fib(n) = fib (n-1) + fib(n-2))) Spiegare brevemente la risposta, preferibilmente fornendo esempi opportuni di valori di n e fib(n) che soddisfino o non soddisfino le formule ) e ): per esempio , se m è n-esimo numero di F ibonacci e ) è la formula corretta, la coppia n, m deve soddisfare ) ma non Esercizio 3 (punti 3/15-esimi) Si consideri il seguente (frammento) di programma: while (x >= 0) { x = x*x - 2*x; } E' decidibile il problema di sta bilire se la sua esecuzione termina qualsiasi sia il valore iniziale della variabile x all'inizio del ciclo? Spiegare brevemente la risposta. Esercizio 4 (punti 8/15-esimi) Si consideri la seguente macchina astratta MA, descritta informalmente nel modo seguente: MA è dotata di un nastro di ingresso e uno di uscita; è dotata…
First page of the document.
