Nome
                        		Cognome
                        		Matricola
          
Soluzione preappello 29/05/2025
DomandaRisposta
1

Scrivere un programma C che contiene tre variabili a, b e c. I valori di a e b sono entrambi uno. La variabile c contiene l'indirizzo di b.

Disegnare la memoria sia come uno scaffale numerato che con rettangoli e frecce, assumendo che gli indirizzi delle tre variabili siano 1, 5 e 7. 

int main() {
	int a, b;
	int *c;

	a = 1;
	b = 1;
	c = &b;
}


   +-----+
   |     | 0
   +-----+
 a |  1  | 1
   +-----+
   |     | 2
   +-----+
   |     | 3
   +-----+
   |     | 4
   +-----+
 b |  1  | 5
   +-----+
   |     | 6
   +-----+
 c |  5  | 7
   +-----+
   |     | 8
   +-----+
   |     |


   +-----+
 a |  1  |
   +-----+
   
   +-----+
 b |  1  | <--+
   +-----+    |
              |
   +-----+    |
 c |  O-------+
   +-----+

2

Convertire il numero decimale 12 e il numero esadecimale 1A in binario. Sommare i due numeri binari così ottenuti e convertire il risultato in ottale. 

12 / 2 = 6 resto 0
6 / 2 = 3 resto 0
3 / 2 = 1 resto 1
1 / 2 = 0 resto 1

I resti in ordine inverso sono il numero in binario: 12 → 1100.

Il numero esadecimale si può convertire in decimale (1A = 1 × 16 + 10 = 26) e poi in binario nello stesso modo. Ma si può anche convertire cifra per cifra. 

1 = 0001
A = 10 → 8 + 2 = 1010
1A = 0001 1010

Somma in binario: 

   11 
 00001100
 00011010
 --------
 00100110

La conversione in ottale si può effettuare mediante una prima conversione in decimale e poi in ottale, ma anche convertendo a gruppi di tre cifre. 

 00 100 110 → 0 4 4+2 → 046
3

Disegnare due grafi non orientati di cinque nodi e quattro archi ognuno. Uno dei due deve essere connesso, l'altro no. Fare in modo che entrambi abbiano una copertura di tre nodi. Oltre al disegno, scrivere l'espressione matematica dei grafi e delle loro coperture.

Il seguente è il grafo connesso, con evidenziata la copertura.

[connesso-02.fig]

Segue il grafo disconnesso, sempre con la sua copertura.

[disconnesso-02.fig]

Le loro espressioni matematiche, e quella della loro copertura:

connesso: ({1,2,3,4,5}, {(2,1), (1,3), (3,5), (5,4)})

disconnesso: ({1,2,3,4,5}, {(2,1), (4,3), (3,5), (5,4)})

copertura: {1,3,4}

4

Mostrare una stringa che collima con l'espressione regolare a[bc]a|a e cinque che non collimano.

L'espressione collima con stringhe che iniziano e terminano con a e hanno un singolo carattere b o c in mezzo. Collima anche con una singola a.

Le stringhe collimanti sono solo a, aba e aca.

Tutte le altre non collimano. Esempi sono: aaa, aa, ε, b, bacd.

5

Fornire un esempio di problema non decidibile. Scrivere un programma Python che lo risolve, oppure spiegare perché nessun programma Python lo può risolvere.

Un problema non decidibile è quello della fermata: decidere se un programma Python termina.

Non esiste nessun programma Python che lo risolve. Se esistesse, lo si potrebbe modificare nel modo seguente:

  • se il programma Python letto come input termina, allora il programma risolutivo entra in un ciclo infinito;
  • se il programma Python letto come input non termina, allora il programma risolutivo termina.

Facendo leggere al programma risolutivo il programma risolutivo stesso, si otterrebbe la contraddizione che il programma risolutivo termina se e solo se non termina.

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