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 Principi dell’Informatica Appello del 27 Settembre 2012 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 3 ore. Chi deve sostenere solo il modulo di Informatica te orica deve svolgere l’Esercizio 1 e l’Esercizio 2 in 1 ora e 30 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere l’Esercizio 3 e l’Esercizio 4 in 1 ora e 30 minuti. NB: i punti attribuiti ai singoli esercizi hanno se nso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 7/30-esimi se si compilano solo le prime 3 righe, 9/30 se si compilano tutte le righe) Si considerino i seguenti linguaggi: L1 = {a nbn| n ≥ 1} ∪ {a nb2n | n ≥ 1} L2 = {1a nbn| n ≥ 1} ∪ {2anb2n | n ≥ 1} L3 = {a n1bn| n ≥ 1} ∪ {a n2b2n | n ≥ 1} L4 = {a nbn1| n ≥ 1} ∪ {a nb2n 2| n ≥ 1} e le seguenti famiglie di macchine astratte, usate come riconoscitori di linguaggi: AF: automi a stati finiti APD: automi a pila determinstici APN: automi a pila nondeterministici ARP: reti di Petri Si riempia la seguente tabella indicando in ogni ca sella se la famiglia indicata nella riga è in grado di riconoscere il linguaggio indicato nella c orrispondente colonna; giustificare brevemente le risposte. L1 L2 L3 L4 AF APD APN ARP Esercizio 2 (punti 9/30-esimi) All’inizio di ogni anno accademico ogni studente de ve compilare il proprio piano di studi. Si formalizzino mediante formule del prim’ordine le se guenti regole (semplificate) relative alla compilazione del proprio piano di studi da parte degli studenti. • Il piano di studi di uno studente consiste in un nu mero di insegnamenti non inferiore a 3 e non superiore a 10 tra quelli ancora disponibil i nel proprio corso di studi (si assuma che esista una tabella con l’elenco degli in segnamenti che…
First page of the document.
