Nome
                        		Cognome
                        		Matricola
          
Soluzione preappello 31/05/2024
DomandaRisposta
1

Dire qual è la differenza fra le seguenti due istruzioni, in generale e in un caso di esempio. 

  b = a;
  b = &a;

La prima istruzione memorizza il valore di a nella variabile b. La seconda ci memorizza il suo indirizzo.

Un caso di esempio è il seguente.

[memoria-01.fig]

La prima istruzione copia il contenuto di a in b, quindi 744.

[memoria-02.fig]

La seconda istruzione copia l'indirizzo di a, quindi il suo numero di ripiano. In questo esempio, il numero è 2.

[memoria-03.fig]

2

Convertire i numeri decimali 37 e 15 in binario, senza segno. Sommarli in binario e convertire il risultato in esadecimale. 

37 / 2 = 18 resto 1
18 / 2 = 9 resto 0
 9 / 2 = 4 resto 1
 4 / 2 = 2 resto 0
 2 / 2 = 1 resto 0
 1 / 2 = 0 resto 1
    ⇒ 100101

15 / 2 = 7 resto 1
 7 / 2 = 3 resto 1
 3 / 2 = 1 resto 1
 1 / 2 = 0 resto 1
    ⇒ 1111

100101 +
  1111 =
--------
     0     somma   1+1=10   →  0 riporto 1
    0      somma 1+0+1=10   →  0 riporto 1
   1       somma 1+1+1=11   →  1 riporto 1
  0        somma 1+0+1=10   →  0 riporto 1
 1         somma 1+0+0= 1   →  1
1          somma   1+0= 1   →  1
--------
110100

Conversione a blocchi di cifre: 110100 = 00110100 = 0011 0100 = 3 4 ⇒ numero in esadecimale: 34.

Alternativa: conversione prima in decimale, poi in esadecimale. 

110100 =
   1 × 25 1 × 24 0 × 23 1 × 22 0 × 21 0 × 20 = 
   1 × 32 + 1 × 16 + 1 × 4 =
   52

52 / 16 = 3 resto 4
 3 / 16 = 0 resto 3
    ⇒ 34
3

Scrivere la rappresentazione del grafo in figura mediante insiemi di successori.

[grafo.fig]

Successori:

1
{2}
2
{1}
3
{1,4}
4
{1,2}

La rappresentazione come liste di successori è quindi: 

({1,2,3,4}, {(1,{2}), (2,{1}), (3,{1,4}), (4,{1,2})})
4

Scrivere l'espressione regolare che collima con le stringhe di lettere minuscole che contengono almeno due lettere a.

Le stringhe da cercare devono avere la forma …a…a…, quindi due a intervallate da altre lettere. Le lettere minuscole sono [a-z]. L'espressione regolare complessiva è quindi la seguente. 

[a-z]*a[a-z]*a[a-z]*
5

Fornire la definizione di NP-hard, e di due problemi NP-hard.

Un problema è NP-hard se per ogni altro problema in NP esiste un programma che converte l'altro problema in quello NP-hard, e questi programmi impiegano tempo polinomiale.

Due esempi sono la soddisfacilità proposizionale e la copertura dei nodi di un grafo.

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