API 2020 02 18

Page 1

Algoritmi e Principi dell’Informatica Appello del 18 Febbraio 2020 Durata: 2 ore e 15 minuti. Esercizio 1 (7 punti) Sia L un qualunque linguaggio regolare costruito su un alfabeto A e sia a un simbolo di A. Il linguaggio L’ che consiste di tutte le stringhe di L che contengono la a è regolare? Motivare opportunamente la risposta. Esercizio 2 (8 punti) È decidibile il problema della soddisfacibilità di una formula MFO? Motivare adeguatamente la risposta. Esercizio 3 (4 punti per la prima parte e fino a un massimo di 6 punti –in caso di soluzione particolarmente brillante– per la seconda parte) Indicare la complessità asintotica della seguente funzione (si rammenta che in questo caso si fa riferimento al criterio di costo costante). F(n) 1 sum = 0 2 for (i = 1; i < n; i++) 3 for (j = 1; j < i * i; j++) 4 if (j % i == 0) 5 for (int k = 0; k < j; k++) 6 sum++ 7 return sum È possibile riscrivere la funzione F(n) in modo che, a parità di risultato calcolato, si abbassi la complessità? Esercizio 4 (8 punti) Si consideri un sistema di assegnazione di pacchi a corrieri presente in un centro smistamento. Il sistema gestisce pacchi caratterizzati da una data e ora di spedizione (il momento in cui il cliente ha consegnato il pacco da spedire) e da un livello di urgenza rappresentato da un intero positivo compreso tra 1 (meno urgente) e 10 (più urgente) e da un identificativo numerico unico. I pacchi sono acquisiti dal sistema già contrassegnati da una data/ora di spedizione e da un livello di urgenza assegnato. Il sistema di smistamento deve selezionare quali pacchi devono essere assegnati ad un corriere nel modo quanto più efficiente possibile considerando i seguenti vincoli: • Nessun pacco con urgenza x deve essere assegnato ad un corriere se ne esiste un altro nel sistema con…