API 2019 07 12

Pagina 1

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,…