Soluzione esame 19/07/2024

Nome Cognome Matricola

Domanda Risposta

Dire la differenza fra valore di una variabile e indirizzo di una variabile, con un esempio in cui sono diversi. Fare anche un esempio in cui una variabile contiene il suo stesso indirizzo, con le istruzioni C che realizzano questa condizione.

Ogni variabile occupa un certo spazio di memoria. Le posizioni di memoria si possono considerare numerate: l'indirizzo di una variabile è il numero della prima posizione di memoria.

Il valore di una variabile è invece quello che si trova all'interno di queste posizioni.

Dato che il valore di una variabile intera è un numero, e che gli indirizzi sono numeri, è possibile che il valore di una variabile coincida con il suo indirizzo. Un esempio in cui questo accade:

int *a;

a = &a;

Dire quale fra i seguenti numeri richiede più di cinque bit per venire rappresentato in binario: 25, 31, 41, 91 e 90.

Il massimo numero di cinque bit in binario è 11111, che convertito in decimale vale:

11111 = 2⁴ + 2³ + 2² + 2¹ + 2⁰ = 16 + 8 + 4 + 2 + 1 = 31

I numeri 41, 90 e 91 sono maggiori di 31, quindi richiedono più di cinque bit.

Disegnare un grafo connesso e uno non connesso di tre nodi l'uno, che contengono almeno un arco l'uno. Scrivere le loro matrici di adiacenza.

Un esempio di grafo connesso di tre nodi. Dato che ogni nodo deve essere raggiungbile da ogni altro, sono necessari almeno tre archi.

La matrice di adiacenza è analoga a una tabella pitagorica, ma invece del prodotto di due numeri contiene la presenza di un arco fra due nodi.

Per esempio, l'arco fra il nodo 1 e il nodo 2 è rappresentato dalla X nella riga 1, colonna 2.

	1	2	3
1		X
2			X
3	X

Segue un esempio di grafo non connesso che contiene un arco. L'arco può essere in posizione qualsiasi, ma almeno uno dei nodi non deve essere raggiungibile dagli altri, in questo caso 3.

Matrice di adiacenza del grafo non connesso:

	1	2	3
1		X
2
3

Dire quali stringhe genera la seguente grammatica. Le lettere minuscole sono i simboli terminali.

X -> YYY
Y -> Z
Z -> xZ
Z -> x
Y -> y

Le derivazioni iniziano sempre rimpiazzando X con YYY. Ogni Y puè venire rimpiazzata in due modi:

con il solo simbolo terminale y
con il simbolo non terminale Z, e allora la derivazione prosegue con xZ ↠ xxZ ↠ xxxZ ↠ xxxx

Viene quindi generata una stringa che contiene tre sottostringhe, di cui ognuna è y oppure una sequenza non vuota di x.

Spiegare il ruolo dell'automa interno di una macchina di Turing. In particolare, dire cosa fa la macchina di Turing che ha il seguente automa interno. Su quali stringhe termina? Cosa scrive sul nastro?

L'automa riceve il carattere sotto la testina e decide cosa scrivere, in che direzione spostare la testina e se terminare o meno.

Nel caso specifico, se il carattere sul nastro è uno, l'automa scrive zero e sposta la testina a destra; se è zero, scrive zero e termina. Quindi l'automa rimpiazza gli uno consecutivi con zero e termina appena questa sequenza consecutiva di uno è finita. Quindi termina se sul nastro c'è almeno uno zero.

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