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 10 Settembre 2012 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 3 ore Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1, 2 e 3 in 1h e 45 min. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3,4 e 5 in 1h e 45 min. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 7/30-esimi) Si considerino le seguenti grammatiche e i linguaggi da esse generati; si indichi, per ognuna di esse, qual è il tipo di automa a potenza minima (all’interno delle “famiglie” tradizionali: a stati finiti, a pila deterministici, a pila nondeterministici, macchine di Turing) che riconosce il linguaggio. 1. S → a X b | b X a X → a X b | b X a | c 2. S → X | Y X → a Y b | ab Y → b X a | ba 3. S → a X b | b Y a X → a S b | ab Y → b S a | ba 4. S → X | Y X → a Y b | b Y a Y → b X a | a X b Esercizio 2 (punti 8/30-esimi) Dire se le seguenti funzioni sono calcolabili, motivando adeguatamente la risposta: 1) f(x,y) è indefinita, se la y-esima MT (sia essa a nastro singolo) termina e durante tutta la computazione con ingresso x non esce mai dalle celle utilizzate per memorizzare la stringa x e le due celle contenenti blank immediatamente prima e dopo x, altrimenti è pari a 0; 2) g(z) = 1 se la funzione calcolata dalla z-esima MT è diversa dalla f del punto 1, 0 altrimenti. Esercizio 3 (punti 3/30-esimi) Si descriva a grandi linee una MT che accetti il Linguaggio 3 dell’Esercizio 1 e se ne valuti la complessità temporale. La descrizione della macchina può essere anche informale ma sufficientemente precisa da permettere la valutazione della complessità…
Prima pagina del documento.
