API 2015 11 23

Page 1

Algoritmi e Principi dell'Informatica Prima Prova in Itinere (modulo Informatica teorica) 23 Novembre 2015 Il tempo a disposizione è di 1 ora e 45 minuti. Esercizio 1 (punti 7 senza la parte c, 8 con la parte c) Parte a. Si consideri il gioco della roulette. Un giocatore adotta la seguente strategia: • inizialmente punta 1€ sul rosso; • a ciascuna estrazione successiva punterà sempre sul rosso; • in particolare, se esce il nero, il giocatore perde la posta e al prossimo turno raddoppierà la puntata; altrimenti vince il doppio di quanto ha puntato e al prossimo turno punterà tutta la vincita. Modellare il comportamento del giocatore con un automa a potenza minima (tra le classi FSA, DPDA, NDPDA e TM) che riceva in ingresso una stringa costruita sull’alfabeto {R,N} (dove R indica che è uscito il rosso e N che è uscito il nero) e che la accetti se e solo se il giocatore che abbia puntato secondo la strategia indicata nelle estrazioni corrispondenti ai simboli in ingresso è in attivo (ossia le vincite superano gli importi complessivamente puntati). Parte b. Qual è il linguaggio accettato da tale automa? Parte c. Cambierebbe la classe dell’automa richiesto se la strategia fosse modificata in modo che, quando esce il rosso, al turno successivo il giocatore punti solo 1€? Esercizio 2 (Punti 5) Il predicato binario succ indica che i suoi argomenti sono numeri naturali tali per cui il secondo è il successore del primo. Ad esempio, succ(1,2) è vero mentre succ(2,6) è falso. Si specifichi in logica del prim’ordine il predicato ternario somma, che indica che il terzo argomento è la somma dei primi due. Ad esempio, somma(2,3,5) è vero mentre somma(3,6,2) è falso. Nella specifica del predicato somma non si può fare uso di predicati diversi da succ e dal predicato di uguaglianza.…