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 Principi dell'Informatica Prima Prova in Itinere 25 Novembre 2014 Il tempo a disposizione è di 1 ora e 45 minuti. Esercizio 1 (punti 6/15 senza la parte facoltativa, 9 con la parte facoltativa) Si ricordi che la stringa inversa di una generica stringa w, qui denotata wR, è ottenuta da w scrivendo i suoi caratteri in ordine inverso, ad esempio abaabbR = bbaaba, aaabbbR = bbbaaa. L’operazione di inversione viene estesa dalle stringhe ai linguaggi nel modo naturale: LR = {wR | w ∈L } Si dica, con brevi spiegazioni, quali delle seguenti famiglie di linguaggi sono chiuse rispetto all’operazione di inversione: • Il linguaggi regolari • I linguaggi non contestuali • I linguaggi generati da grammatiche non ristrette • (Parte facoltativa) I linguaggi non contestuali deterministici NB: la parte facoltativa verrà valutata solo se nelle restanti parti si saranno ottenuti almeno 5 punti. Esercizio 2 (punti 7/15) Due macchine di Turing (MT) si dicono isomorfe se: • hanno lo stesso numero di nastri; • ad ogni mossa spostano le rispettive testine del nastro i-esimo alla stessa maniera (entrambe a destra o entrambe a sinistra o lasciano entrambe ferme); Si noti che di conseguenza due MT isomorfe usano esattamente le stesse celle di memoria. E' decidibile il fatto che due qualsiasi MT isomorfe siano equivalenti, ossia calcolino la stessa funzione o riconoscano lo stesso linguaggio? Giustificare brevemente la risposta Esercizio 3 (punti 5/15) Specificare in logica del prim’ordine il linguaggio L1 = { anbncn | n≥0 }. Nella specifica si possono usare esclusivamente i seguenti predicati e funzioni: • il predicato di appartenenza insiemistica ∈ • il predicato di uguaglianza = • la funzione di concatenazione ⋅ • le costanti dei caratteri alfabetici a, b, c e la stringa vuota ε •…
Prima pagina del documento.
