Informatica teorica

la funzione  $3x^2\ +\ 5x\ +\ 9$  è

•  $O\left(3x^2\right)$  

•  $O\left(x^2\right)$  

•  $O\left(5x\right)$  

•  $O\left(x\right)$  

la funzione  $2x\log_2x$  è

•  $\Theta\left(x\right)$  

•  $\Theta\left(x\log_2x\right)$  

•  $\Theta\left(\log_2x\right)$  

•  $\Theta\left(2x\log_2x\right)$  

la funzione  $x\log_2x$  è

•  $O\left(x\right)$  

•  $O\left(1\right)$  

•  $O\left(x^2\right)$  

•  $O\left(\log_{ }x\right)$  

Qual è l'input della funzione della complessità computazionale di un qualsiasi algoritmo di sorting?

• La sequenza di numeri in input

• La cardinalità della sequenza di numeri in input

• La dimensione di ogni numero che compone la sequenza di numeri in input

• La sequenza di oggetti in input

Fai un esempio di un problema di decisione (che non sia quello della cricca definito sulle slide)

Se un problema P ha upper bound $O(n\log n)$ vuol dire che

• Tutti gli algoritmi finora scoperti che risolvono P terminano in tempo  $O(n\log n)$  

• Esiste almeno un algoritmo che risolve P che termina in tempo  $O(n\log n)$  

• Tutti gli algoritmi che potranno essere scoperti in futuro che risolvono P termineranno in tempo  $O\left(n\log n\right)$  

• E' impossibile che esista un algoritmo che risolve P che termina in tempo  $O\left(n\ \log n\right)$  

Una macchina di Turing opera su

• Un nastro di memoria finito

• Un nastro di memoria infinito

• Dipende dall'algoritmo

• Nessuna delle altre risposte

Cosa NON può fare una macchina di Turing dopo aver letto un simbolo sul nastro?

• Scrivere un simbolo sul nastro

• Spostarsi con la testina di una cella a destra/sinistra

• Procedere con la prossima istruzione (o bloccarsi)

• Nessuna delle altre risposte

Cosa NON può succedere ad una macchina di Turing mentre sta processando un input?

• Entrare in un stato di accettazione

• Entrare in un stato di rigetto

• Entrare in un loop infinito

• Nessuna delle altre risposte

In quale stato finisce la macchina di Turing qui rappresentata leggendo l'input  $aabacda$  ? Clicca sul diagramma per ingrandirlo.

• S4

• S3

• S2

• S1