Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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 complessità spaziale e temporale. Esercizio 4 (Punti 8) In un albero binario, il grado di sbilanciamento di un nodo può essere calcolato come valore assoluto della differenza fra il numero di foglie presenti nei suoi due sottoalberi. A partire da tale valore…
First page of the document.
