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 21 Settembre 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 7) Si consideri il linguaggio seguente: L1 = {a,b,c}* - a*.b* dove il – indica la differenza insiemistica. Si costruiscano una macchina astratta che riconosca L1 e una grammatica che lo generi; è fortemente raccomandato che entrambi i formalisimi siano a “potenza minima” ossia appartenenti alla categoria di automi/grammatiche a minor potenza riconoscitiva/generativa possibile. Esercizio 2 (Punti 8) Si consideri, oltre al linguaggio L1 dell’esercizio 1, anche il linguaggio L2 seguente: L2 = {a,b}* - {anbn | n > 0} Si dica, motivando brevemente la risposta, quali dei seguenti problemi sono decidibili e quali no: 1. Stabilire se un generico automa a stati finiti riconosce L1 2. Stabilire se un generico automa a stati finiti riconosce L2 3. Stabilire se una generica macchina di Turing riconosce L1 4. Stabilire se una generica macchina di Turing riconosce L2 Esercizio 3 (Punti 7) Si consideri il linguaggio L = {wcwcw | w ∈ {a,b}+}. Si descriva una macchina RAM che riconosca L, minimizzando la complessità spaziale sia a criterio di costo costante che logaritmico. Esercizio 4 (Punti 8) Sia dato un array A di n interi che assumono valori nell'intervallo [0, …, n+1]. L’array non contiene valori duplicati; i valori in esso contenuti saranno quindi tutti…
Prima pagina del documento.
