Nome
                        		Cognome
                        		Matricola
          
Esame gg/mm/aaaa
1

Mostrare un esempio in cui un programma Java che genera un errore in compilazione, ma non succederebbe se Java avesse la tipizzazione ad anatra.

(linguaggi di programmazione)

2

Il numero 345 potrebbe essere in binario? In base cinque? In base sette? Se sì quanto vale in decimale?

(rappresentazioni numeriche o logica applicata)

3

Scrivere la rappresentazione insiemistica del grafo mostrato in figura. 

   +-+
   | v
    0 ------> 1
    |        /^
    |      /  |
    |    /    |
    V  <      |
    2 --------+

(grafi)

4

Dire quali stringhe sono generate dalla seguente grammatica, dove X è il simbolo iniziale e le maiuscole indicano i simboli non terminali. 

X → Y
X → Z
Y → X
Z → ab
Z → a

(linguaggi formali)

5

Dire quale delle seguenti affermazioni è corretta. Spiegare perchè la altre sono errate.

  1. una macchina di Turing esegue programmi Python
  2. ogni problema che si può risolvere con un programma Python ha una macchina di Turing che lo risolve
  3. una macchina di Turing ha un programma fisso
  4. non esiste nessuna macchina di Turing che risolve il problema di soddisfacibilità proposizionale
  5. le macchine di Turing nondeterministiche impiegano sempre tempo polinomiale

(calcolabilità e complessità)

NOTA: risposte prive di esauriente motivazione (es. i passaggi delle operazioni numeriche) verranno considerate nulle.