Fondamenti di informatica per Biomedica - 14 maggio 2015
(revised: 20150604)

	===  PRIMA PARTE: Domanda a risposte multiple (soglia: 5 su 8) ===

-------------------------------------------------------------------
1. L'espressione booleana /A /C /D + B C equivale a:

	a)    A C D + /B /C

	b)    /A /B /C /D + A B C + B C D + /A B /D

	c)    B C + /A /C /D + B

	d)    / ( A C D + /B /C )

	e)    /A /B /C /D + /A /C /D + /A B D + B C D

-------------------------------------------------------------------
2. Quale colonna della seguente tabella di verita` realizza
   la funzione XOR ?

       i1  i0     a   b   c   d   e
    ----------------------------------
       0   0      1   1   1   0   0
       0   1      0   0   1   1   0
       1   1      0   1   0   0   0
       1   0      1   1   0   1   0

-------------------------------------------------------------------
3. Sia data una rete combinatoria che implementa il sommatore elementare
   in base 2, con ingressi x, y, c_i e uscite s, c_o.
   Quale colonna della tabella di verita` rappresenta l'uscita s ?

      x  y  c_i     a    b   c   d   e
    ------------------------------------
      0  0   0      0    0   0   0   0
      0  0   1      0    1   0   1   1
      0  1   0      1    1   1   1   1
      0  1   1      1    2   1   0   1
      1  0   0      1    1   0   1   1
      1  0   1      1    1   0   0   1
      1  1   0      0    2   1   0   1
      1  1   1      0    3   1   1   1

-------------------------------------------------------------------
4. Quante volte viene eseguito il corpo del for nel seguente
   frammento di codice Javascript:

	for (x = 2; x != 10; x = x + 1) { x += 3; }

	a) 1	b) 2	c) 3	d) 10	e) infinite

-------------------------------------------------------------------
5.  Nel codice precedente, quante volte viene eseguito  "x != 10"

	a) 1	b) 2	c) 3	d) 10	e) infinite

-------------------------------------------------------------------
6.  Quanto vale x dopo l'esecuzione del seguente codice Javascript

      var x, y, z = { alfa:1 };
      y = z;
      z.alfa = y.alfa + 2;
      x = y.alfa + z.alfa;

	a) 2	b) 3	c) 4	d) 5	e) 6 

-------------------------------------------------------------------
7. Una lista contiene elementi della forma { Nome: "...", Valore: XXX }
   La lista e` unidirezionale, con solo un puntatore alla testa,
   contiene N elementi ed e` ordinata per valori DECRESCENTI del Nome.

   Qual'e' la complessita` delle operazioni di ricerca del minimo
   Valore (Vmin), ricerca del massimo Valore (Vmax), ricerca
   di un Valore specifico (Vrnd)
   
	a)  Vmin: O(1), Vrnd: O(log N), Vmax: O(N)
	b)  Vmin: O(N), Vrnd: O(log N), Vmax: O(1)
	c)  Vmin: O(1), Vrnd: O(N),     Vmax: O(N)
	d)  Vmin: O(N), Vrnd: O(N),     Vmax: O(N)
	e)  Vmin: O(N), Vrnd: O(N),     Vmax: O(1)

-------------------------------------------------------------------
8. Nella lista precedente, qual'e' il costo delle ricerce del Nome
   minimo (Nmin), Nome massimo (Nmax), Nome specifico (nrnd)

	a)  Nmin: O(1), Nrnd: O(log N), Nmax: O(N)
	b)  Nmin: O(N), Nrnd: O(log N), Nmax: O(1)
	c)  Nmin: O(1), Nrnd: O(N),     Nmax: O(N)
	d)  Nmin: O(N), Nrnd: O(N),     Nmax: O(N)
	e)  Nmin: O(N), Nrnd: O(N),     Nmax: O(1)

-------------------------------------------------------------------

     =========== SECONDA PARTE - domande aperte =============

-------------------------------------------------------------------
1. Si vuole realizzare una LISTA CIRCOLARE contente dati della forma
      { Nome: "...", Cognome: " ..." , Anno: XXX, ... } /* DATO */
   Gli elementi della lista hanno i campi
      { x: <dato>, succ: <elemento successivo> } /* ELEMENTO */
   e alla lista si puo` accedere mediante riferimento a qualunque
   elemento della stessa.

   Scrivere le seguenti funzioni SPIEGANDO BENE come sono gestiti i
   vari casi limite (es. lista vuota, termine della scansione, ecc.)

   function ins(e /* ELEMENTO */, d /* DATO */)
	inserisce d nella lista, ritorna il riferimento a un
	qualunque elemento della lista

   function del(e /* ELEMENTO */, d /* DATO */)
        rimuove dalla lista tutti gli elementi che hanno nome uguale
        a d.Nome, ritorna riferimento a un qualunque elemento della lista

   function print(e /* ELEMENTO */, x /* RegExp */)
        ritorna un vettore con tutti i DATI per cui
        Cognome.match(x) == true (il cognome e` conforme
        alla regular expression)

-------------------------------------------------------------------
2. Data la lista precedente con N elementi, costruire una funzione
   che lascia nella lista, per ogni cognome, un solo elemento scelto
   a caso tra quelli con Anno piu` piccolo.

   Indicare prima l'algoritmo utilizzato, la sua complessita`,
   e poi mostrarne l'implementazione

     ===          ESEMPIO DI SOLUZIONE ======

Prima parte: domande aperte

1. RISPOSTA: b

   In questo caso la strada piu` semplice visto che la funzione ha
   poche variabili consiste nell'enumerare i casi e costruire
   la tabella di verita` delle varie funzioni, identificando
   cosi` la risposta esatta


2. RISPOSTA: d
 
   Deriva dalla definizione di or esclusivo

3. RISPOSTA: d

   Anche questa deriva dalla definizione della funzione del
   sommatore elementare

4. RISPOSTA: b

   Simulando il comportamento del codice si vede che x viene
   incrementato di 4 ad ogni esecuzione del ciclo, per cui il
   corpo viene eseguito 2 volte prima di terminare

5. RISPOSTA: c

   La condizione viene verificata una volta in piu` rispetto alle
   esecuzioni del corpo

6. RISPOSTA: e

   Ricordando che per gli oggetti si assegnano riferimenti,
   l'operazione y = z fa si che entrambe le variabili riferiscano
   lo stesso oggetto quindi y.alfa e z.alfa coincidono.

7. RISPOSTA: d

   La lista e` ordinata per Nome ma la ricerca e` per Valore quindi
   tutte le operazioni hanno costo proporzionale al numero di
   elementi della lista

8. RISPOSTA: e

   In questo caso la ricerca e` effettuata sulla chiave di ordinamento,
   per cui la ricerca del massimo richiede tempo costante, mentre le
   altre operazioni hanno costo lineare


Esercizio 1

In una lista circolare non esiste una testa o una coda, ma tutti
gli elementi sono equivalenti e da un qualunque elemento si raggiunge
tutto il resto della lista.

Rappresenteremo la lista vuota con il valore null.

Per l'inserimento, nel caso ci venga passata una lista vuota
restituiamo l'elemento inserito che costituisce la nuova lista.
Negli altri casi, inseriamo il nuovo elemento dopo quello passato
alla funzione, e possiamo restituire un elemento arbitrario

    function ins(e, d) {
        var n = { x: d, succ: null}; /* nuovo elemento */
        if (e == null) {
            n.succ = n;
        } else {
            n.succ = e.succ;
            e.succ = n;
        }
        return n;
    }

La cancellazione si effettua navigando sulla lista con due puntatori,
all'elemento precedente e a quello corrente, e ricordando il punto
di partenza in modo da sapere quando fermarsi nella scansione.

    function del(e, d) {
        var prev, cur;
        if (e == null) { return null; }
        prev = e;
	cur = e.succ;
        while (cur != e) {
            if (cur.x.Nome == d.Nome) { /* elimina */
                prev.succ = cur.succ;
                cur = cur.succ;
            } else { /* avanza */
	        prev = cur;
		cur = cur.succ;
            }
        }
        /* gestisci ultimo elemento */
	if (cur.x.Nome == d.Nome) { /* elimina */
            if (cur.succ == cur) /* ultimo rimasto */
                return null;
            } else {
                prev.succ = cur.succ;
            }
        }
        return prev;
    }

La funzione print() effettua una scansione della lista, ricordando
il punto di partenza.

    function print(e, x) {
        var cur = e, ris = [];
        if (e != null) {
             do {
                 if (e.x.Cognome.match(x)) {
                     ris.push(e.x);
                 }
                 cur = cur.succ;
             } while (cur != e);
        }
        return ris;
    }

----------
Esercizio 2

Per identificare gli elementi da lasciare nella lista bisogna fare
una scansione completa della stessa, e conviene sfruttare una mappa
per tener traccia del piu` piccolo per ogni cognome.

Organizzeremo quindi il programma in due passi: nel primo, si scandisce
la lista identificando gli elementi da MANTENERE (e memorizzandone
i riferimenti in una mappa che usa il Cognome come chiave),
nel secondo elimineremo gli elementi dalla lista.
Entrambi i passi hanno complessita` O(N) che e` la migliore
soluzione possibile.

    function filtra(e) {
        var m = {}, c, prev, cur = e;

        if (e == null) { return e; }

        /* prima passata */
        do {
            c = cur.x.Cognome;
            if (m{c} == undefined || cur.x.Anno < m{c}.x.Anno) {
                m{c} = cur; /* memorizza candidato */
            }
            cur = cur.succ;
        } while (cur != e);

        /* seconda passata */
        prev = e;
        cur = e.succ;
        while (cur != e) {
            if (m{cur.x.Cognome} != cur) { /* nodo da eliminare */
                prev.succ = cur.succ;
                cur = cur.succ;
            } else {
                prev = cur;
                cur = cur.succ;
            }
        }
        /* ultimo elemento */ 
	if (m{cur.x.Cognome} != cur) { /* nodo da eliminare */
            if (cur.succ == cur) { /* unico nella lista */
                prev = null; /* lista vuota */
            } else {
                prev.succ = cur.succ;
            }
        }
        return prev;
    }
----------