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 12 Luglio 2019 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (8 punti) Un linguaggio L viene detto senza prefissi se non contiene alcuna stringa che sia un prefisso proprio di un’altra stringa di L. È decidibile il problema di stabilire se un generico automa a stati finiti A riconosca un linguaggio senza prefissi? Cambierebbe la risposta se, al posto di un automa a stati finiti, fosse data una generica macchina di Turing? Esercizio 2 (8 punti) Si consideri la seguente grammatica G1: S -> ab A b | S b | abb A -> ab S b 1) Si descriva formalmente, come insieme di stringhe, il linguaggio L(G1). 2) È possibile rendere il precedente linguaggio regolare, aggiungendo una sola produzione a G1? In caso negativo, si motivi esaurientemente la risposta; in caso positivo, si indichi tale produzione e si definisca il linguaggio risultante usando una grammatica o automa a potenza espressiva minima. Esercizio 3 (7 punti) Si consideri una funzione f(n) tale che 𝑙𝑖𝑚$→&𝑓(𝑛)𝑛+=0 dove c è una costante positiva arbitraria. Si può concludere che f(n) = O(nc-e), per una qualche costante positiva e < c? Motivare opportunamente la risposta. Esercizio 4 (9 punti) Siano dati k BST (Binary search tree, o alberi binari di ricerca), ciascuno contenente un numero ni di nodi, anche fortemente variabile tra i vari alberi. Si descriva in modo chiaro, sintetico e preciso,…
First page of the document.
