Esame completo di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Esame completo di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Qualità dell’importazione: il testo è stato estratto direttamente dal documento originale.
Passaggi rappresentativi riconosciuti nelle diverse parti del materiale. Il testo completo resta presente nella pagina per la ricerca, mentre l’anteprima compatta rende più semplice la lettura.
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…
Prima pagina del documento.
