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 Soluzioni al Tema d’esame 12 luglio 2022 Informatica teorica - Tempo a disposizione: 1 ora Esercizio 1 (8 punti) Si costruisca una grammatica o automa o formula logica a potenza minima per il seguente linguaggio: {a2nΣ+b3n | n > 0} ∪ {Σ+b3n | n > 0}, con Σ = {a, b}. Soluzione Il linguaggio ` e aperiodico (o “star-free”), in quanto {a2nΣ+b3n | n > 0} ⊂ { Σ+b3n | n > 0} = Σ+.b3. Si pu` o dunque esprimere con la seguente formula MFO: ∃y(y > 0 ∧ b(y) ∧ b(y + 1) ∧ b(y + 2) ∧ last(y + 2)). Esercizio 2 (8 punti). Chi ha diritto alla riduzione del 30% della prova svolga solo il punto 3. 1. Dire se ` e decidibile il problema di stabilire se due programmi, uno scritto in C e uno scritto in Java, calcolano la stessa funzione. 2. Dire se ` e decidibile il problema di stabilire se due programmi, entrambi scritti in C, sono identici, salvo per il fatto che i nomi delle variabili usate sono diversi tra un programma e l’altro. 3. Dire se ` e decidibile il problema di stabilire se, dato un programma C che fa uso di puntatori, esiste un’esecuzione in cui, ad un certo punto, due variabili puntano entrambe allo stesso indirizzo (fenomeno dell’aliasing). Soluzione 1. L’equivalenza di programmi C e Java ` e indecidibile, si pu` o vedere riducendo il problema dell’equivalenza tra due programmi C a quella tra un programma C e un programma Java: ogni programma C pu` o essere trasformato in un equivalente programma Java, e se fosse decidibile l’equivalenza tra programma Java e programma C, allora potremmo anche decidere l’equivalenza tra programmi C, che non ` e possibile. 1/4 2. Il problema ` e decidibile, in quanto si tratta di leggere i 2 programmi parola per parola. Laddove si trovano dichiarazioni di variabili (che devono essere in corrispondenza una…
Prima pagina del documento.
