Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
