API 2020 01 24

Pagina 1

Algoritmi e Principi dell’Informatica Appello del 24 Gennaio 2020 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) Dimostrare che la famiglia di insiemi semidecidibili è chiusa rispetto all’intersezione, cioè, dati due insiemi qualunque S1 e S2, entrambi semidecidibili, la loro intersezione S12 = S1 Ç S2 è pure semidecidibile. A questo scopo, si risponda alle seguenti domande: 1. Delineare una procedura semDecS12 che “semidecide” S12, cioè tale che per xÎS12 semDecS12(x) termini e restituisca “vero”, mentre per xÏS12 semDecS12(x) non termini; si può assumere l’esistenza di simili procedure semDecS1 e semDecS2 che semidecidono S1 e S2. 2. Delineare una procedura che enumeri S12. 3. Con l’assunzione che S12 ¹ Æ, scrivere una definizione della funzione generatrice gS12 di S12 (con questo termine si intende la funzione totale e calcolabile la cui immagine sia S12). Suggerimento: sfruttare il fatto che le funzioni generatrici gS1 di S1 e gS2 di S2 esistono; assicurarsi che gS12 sia totale e computabile e che la sua immagine coincida con S12. Esercizio 2 (8 punti) Sia dato un alfabeto S. Date due stringhe qualunque x,yÎ S*, diciamo che y è una sottostringa di x se e solo se y può essere ottenuta da x rimuovendo alcuni caratteri (anche nessuno o tutti). Dunque, ad esempio, tutte e sole le sottostringhe di x = abaa sono: e, a, b, ab, ba, aa, aba, aaa, baa, abaa. Dato un qualunque linguaggio L di…