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 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…
First page of the document.
