API 2016 09 15

Page 1

Algoritmi e Principi dell’Informatica Appello del 15 Settembre 2016 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 eser cizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (8 punti) In matematica, si definiscono numeri primi gemelli due numeri primi che differiscano tra loro di 2. La congettura dei numeri primi gemelli afferma che esistono infinite coppie di numeri primi gemelli. Specificare tale congettura mediante una formula di logica del prim’ordine. Nella specifica è consentito utilizzare:  come funzioni, le usuali quattro operazioni aritmetiche;  come costanti, i numeri naturali 0, 1, 2, …;  come predicati, il predicato di uguaglianza (=), i comparatori (<, >, , ) e un predicato unario nat che indica che il suo argomento è un numero naturale. È inoltre possibile, e consigliabile, specificare dei predicati ausiliari per render più agevole la scrittura e la comprensione della formula; tuttavia la semantica di tali predicati dovrà essere esplicitamente definita mediante opportune formule che facciano riferiment o ai simboli base di cui sopra. Esercizio 2 (9 punti) Punto a) Ad oggi, la più grande coppia di numeri primi gemelli trovata è 3756801695685 · 2666669 ± 1 . Si tratta di numeri con ben 200700 cifre, ma non è ancora stato dimostrato l’enunciato della congettura, che potrebbe quindi anche essere falsa. Che cosa si può concludere in merito alla decidibilità dell’enunciato della congettura? Punto b) Sia f…