18 / 24
www.
edises
.it
8
Parte Prima
Competenze disciplinari
25) La cardinalità dell’insieme di tutti i sottoinsiemi dell’insieme A è:
A. ||A||
B. ||A||
2
C. 2
||A||
D. 2
||A||–1
26) L’algoritmo A ha una complessità di tempo nel caso peggiore pari
a O(
n
log
n
), mentre l’algoritmo B ha una complessità di tempo nel caso
peggiore pari a O(6
n
log
n
): quale delle seguenti affermazioni è corretta?
A. L’algoritmo A gira sempre più velocemente dell’algoritmo B
B. L’algoritmo A è più efficiente dell’algoritmo B
C. L’algoritmo B è più efficiente dell’algoritmo A
D. L’algoritmo A e l’algoritmo B sono equivalenti quanto a complessità di tempo
27) Che cosa significa che un problema è “indecidibile”?
A. Che non esiste un algoritmo che lo risolve in un tempo polinomiale
B.
Che si conoscono solo algoritmi che lo risolvono in un tempo esponenziale
C.
Che si conoscono solo algoritmi che lo risolvono in un tempo polinomiale
D. Che non può essere risolto in un tempo finito da alcun algoritmo
28) Si consideri la seguente definizione in BNF di un linguaggio:
<tree> ::= <leaf> | “(“<children>”)”
<children>::= <tree> | <tree>, <children>
<leaf> ::= “a” | “b” | “c”
Quale delle seguenti espressioni fa parte del linguaggio?
A. a, (b, c)
B. (a, (a, b))
C. a, b, c
D. b (c d)
29) Quanta informazione contiene un dato che può assumere n configu-
razioni equiprobabili?
A. n
B. log (1/n)
C. log n
D. n!
30) A quale concetto matematico è strettamente collegata la ricorsione?
A. All’induzione
B. Ai numeri reali