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: , succ: } /* 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; } ----------