Esame completo 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.
Esame completo 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 Appello del 2 Marzo 2015 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 8) Una macchina di Turing si dice n-generatrice se, quando riceve 0 in ingresso, termina entro n+1 passi scrivendo il numero n in uscita (n≥0). Fissata una qualsiasi enumerazione algoritmica E delle macchine di Turing, il generatore minimo di un numero n, indicato con gm(n), è il più piccolo indice, secondo E, di macchina di Turing n-generatrice. Si risponda alle seguenti domande fornendo brevi ma chiare spiegazioni per le risposte date: a) La funzione gm è totale? b) La funzione gm è computabile? Esercizio 2 (punti 9) Si consideri il seguente linguaggio: L = {anb3n | n ≥ 0} ∪ {an(bbbc)n | n ≥ 0} Si forniscano: a) Una grammatica, preferibilmente a potenza generativa minima, che generi L b) Un automa, preferibilmente a potenza minima tra le famiglie tradizionali a stati finiti, a pila (deterministici o no), macchine di Turing, che riconosca L c) Una rete di Petri che riconosca L Esercizio 3 (punti 9) Si consideri il seguente linguaggio: L = {an1ban2b…ank | 1 ≤ k ≤ 100, ∀ 1 ≤ i ≤ k.(ni ≥ 1), ∃ 1 ≤ i < j ≤ k.(ni = nj)} Si descrivano a grandi linee, ma in maniera sufficientemente precisa, una MT e una RAM che riconoscano L e se ne valutino le complessità temporali, nel caso della RAM sia a criterio di costo costante che a criterio logaritmico. Sono…
Prima pagina del documento.
