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