Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Prin Informatica Appello del 30 Giugno 2016 2 ore e 30 minuti . Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti . Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti . NB: i punti attribuiti ai singol i esercizi hanno senso solo con hanno valore puramente indicativo. Esercizio 1 (Punti 8) Tutte le volte che mangio del salame entro 24 ore mi vien e mal di pancia, a meno che, prima che sopraggiunga il mal di pancia, non prenda una pillola gastroprotettrice. Si supponga, per semplicità, che mangiare salame sia un evento isolato nel tempo e che non Suggerimento (non imposizione!) Si consiglia di far uso , non necessariemtne esclusivo, dei seguenti predicati , tutti parametrici rispetto alla variabile t : Salame(t) : mangio del salame al tempo t MalPancia(t): mi viene mal di pancia Pillola(t): assumo una pillola La variabile t può essere interpretata indifferentemente in un dominio discreto o continuo. Esercizio 2 (Punti 7) Siano L1, L2, .. Lk, k > 1 linguaggi definiti su un alfabeto , tali che valgano le seguenti proprietà: i j, Li Lj = , L1 L2 Lk = *, i, Li è semidecidibile. Si dica, giustificando brevemente la risposta se le seguenti affermazioni sono vere o false: Tutti i linguaggi L1, L2, .. Lk sono ricorsivi Tutti i linguaggi L1, L2, .. Lk sono necessariamente regolari Esercizio 3 (Punti 7) Si definisca una MT a k nastri che riconosca il linguaggio L = {www | w {0,1} +} e se ne valutino le c omplessità spaziale e temporale. Esercizio 4 (Punti 8) In un albero binario, il grado di sbilanciamento di un nodo può essere calcolato come valore assoluto del la differenza fra il numero di foglie presenti nei suoi due sottoalberi. A partire da tale valore calcolato per ogni nodo, è possibile ricavare un grado di sbilanciamento di un albero come il massimo tra i gradi di sbilanciamento calcolati per tutti i suoi nodi. Per esempio , dato il seguente albero binario, per il quale si riportano anche i gradi di sbilanciamento ( gs ) dei singoli nodi: il grado di sbilanciamento per l albero radicato in A è 2, poiché questa è la differenza massima del numero di foglie nei due sottoalberi di A (quella cioè calcolata per il sottoalbero radicato in C). Si definisca un algoritmo per il calcolo del grado di sbilanciamento di un albero binari o; se ne discuta quindi la complessità. Tracce di soluzioni Esercizio 1 Soluzione A I seguenti predicati allora formalizzata come segue: t (salame(t) t1( t < t 1