API 2022 06 28

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 28 giugno 2022 Informatica teorica - Tempo a disposizione: 1 ora Esercizio 1 (8 punti) Si definisca un automa a potenza minima per il linguaggio {xcy | x, y ∈ {a, b}+, |x| = 2|y| oppure 2|x| = |y|}. Soluzione Si tratta di un automa a pila non-deterministico – se ne allega la versione JFLAP (si ricorda che Z sta per Z0 e λ per ε). Esercizio 2 (8 punti). Chi ha diritto alla riduzione del 30% della prova svolga unica- mente il punto 2.1. 1. Siano dati due automi a pila deterministici con linguaggi L1 e L2: ` e ricorsivo il linguaggio L1 ∩ L2? 2. Siano dati due automi a pila deterministici con linguaggi L1 e L2 e una macchina di Turing M: ` e decidibile seM calcola L1 ∩ L2? Soluzione 1/4 1. S` ı, basta simulare i due APD con una MT e vedere se entrambi accettano la stringa in ingresso. 2. No, per il teorema di Rice: si tratta del consueto problema di determinare la correttezza di una generica macchina M. 2/4 Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 28 giugno 2022 Algoritmi e strutture dati - Tempo a disposizione: 1 ora Esercizio 3 (8 punti) Si consideri il problema di stampare, senza duplicati, gli elementi di un array a non ordinato di n interi strettamente positivi. Per ciascuno dei casi seguenti, si fornisca una soluzione che garantisca la migliore complessit` a asintotica:a) caso ottimo; b) caso medio; c) caso pessimo. Per ciascuna delle soluzioni presentate, si specifichino le complessit` a nei tre casi. Soluzione Nel caso ottimo, basta una semplice scansione con due cicli nidificati: 1 ottimo ( a ) 2 b := [ true , ... , true ] // array di n booleani 3 for i := 1 to a . length 4 if b [ i ] 5 print a [ i ] 6 if i +1 <= a . length 7 for j := i +1 to a . length 8 if a [ i ] = a [ j ] 9…