Primo parziale di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Primo parziale di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Qualità dell’importazione: il testo è stato estratto direttamente dal documento originale.
Passaggi rappresentativi riconosciuti nelle diverse parti del materiale. Il testo completo resta presente nella pagina per la ricerca, mentre l’anteprima compatta rende più semplice la lettura.
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…
Prima pagina del documento.
