Secondo 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.
Secondo 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 Seconda prova in itinere −− −− 24 Gennaio 2012, Sezione Pradella Avvisi importanti I punteggi attribuiti ai singoli esercizi hanno val ore solo per chi sostiene la II prova completa del corso integrato. Per chi deve sostenere solo il modulo di Informatic a 3 o l’intero appello (riservato ai laureandi) il punteggio sarà diverso e valutato caso per caso. Chi deve sostenere solo l’esame di Informatica 3 de ve risolvere gli esercizi 2, 3, 4 in 2 ore. Chi deve sostenere la II prova del corso integrato deve risolvere gli esercizi 1, 2, 3, 4 in 2 ore e 15 minuti. Chi deve sostenere l’intero appello deve risolvere tutti gli esercizi in 3 ore e 30 minuti. Su ogni foglio consegnato devono essere indicati chiaramente: Cognome, nome, numero di matricola Quale dei tre tipi di prova di cui sopra si sta sostenendo Esercizio 1 (punti 4/18-esimi) Si dica, giustificando brevemente ma precisamente l a risposta, se la seguente funzione f è calcolabile: Per i compreso tra 1 e 1000, j compreso tra 1 e 100 00, f(i, j) = 1 se la i-esima MT si ferma computando il dato j, 0 altrimenti. Esercizio 2 (punti 6/18-esimi) 1. Si descrivano, mediante opportuno pseudocodice, due algoritmi che simulino il comportamento di due rispettivi automi a pila che riconoscano i seguenti linguaggi: a. L1 = { a n bn } ∪ { an b2n }| n ≥ 1 b. L2 = {ww R | w ∈ {a,b}*} ( wR indica, al solito, la stringa speculare di w) NB1: gli algoritmi non devono semplicemente decidere s e una stringa appartiene al linguaggio dato, ma simulare completamente il comportamento dell’automa, ossia ripercorrere –senza necessariamente fornirle in out put- le stesse computazioni che eseguirebbe l’automa. NB2 : si può assumere che l’input dell’algoritmo sia un a stringa di caratteri seguita da un…
Prima pagina del documento.
