Free Printable Informatica teorica

1.

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

a)

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

b)

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

c)

$O\left(5x\right)$

d)

$O\left(x\right)$

2.

la funzione $2x\log_2x$ è

a)

$\Theta\left(x\right)$

b)

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

c)

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

d)

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

3.

la funzione $x\log_2x$ è

a)

$O\left(x\right)$

b)

$O\left(1\right)$

c)

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

d)

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

4.

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

a)

La sequenza di numeri in input

b)

La cardinalità della sequenza di numeri in input

c)

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

d)

La sequenza di oggetti in input

5.

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

4 lines

6.

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

a)

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

b)

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

c)

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

d)

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

7.

Una macchina di Turing opera su

a)

Un nastro di memoria finito

b)

Un nastro di memoria infinito

c)

Dipende dall'algoritmo

d)

Nessuna delle altre risposte

8.

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

a)

Scrivere un simbolo sul nastro

b)

Spostarsi con la testina di una cella a destra/sinistra

c)

Procedere con la prossima istruzione (o bloccarsi)

d)

Nessuna delle altre risposte

9.

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

a)

Entrare in un stato di accettazione

b)

Entrare in un stato di rigetto

c)

Entrare in un loop infinito

d)

Nessuna delle altre risposte

10.

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

a)

S4

b)

S3

c)

S2

d)

S1

11.

Che complessità ha il caso peggiore dell'Insertion Sort?

a)

$\Theta\left(n\right)$

b)

$\Theta\left(n\log n\right)$

c)

$\Theta\left(n^2\right)$

d)

Nessuna delle altre risposte

12.

Che complessità ha il caso medio del Quick Sort?

a)

$\Theta\left(n\right)$

b)

$\Theta\left(n\log n\right)$

c)

$\Theta\left(n^2\right)$

d)

Nessuna delle altre risposte

13.

Che complessità ha il caso migliore del Merge Sort?

a)

$\Theta\left(n\right)$

b)

$\Theta\left(n\log n\right)$

c)

$\Theta\left(n^2\right)$

d)

Nessuna delle altre risposte

14.

Se avendo un array di $n$ elementi lo suddivido ad ogni passaggio in due parti uguali, dopo quanti passaggi arrivo a non avere più niente da dividere?

a)

$O\left(n\right)$

b)

$O\left(\log_2n\right)$

c)

$O\left(n^2\right)$

d)

$O\left(1\right)$

15.

Cos'è la funzione di transizione di una macchina di Turing?

4 lines

16.

Nell'array di input che rappresenta il caso medio per l'algoritmo Insertion Sort:

a)

ogni numero è lontano $1$ posizione dalla posizione desiderata

b)

ogni numero è lontano $n-1$ posizioni dalla posizione desiderata

c)

ogni numero è lontano $n/2$ posizioni dalla posizione desiderata

d)

ogni numero è già nella posizione desiderata

17.

Nell'algoritmo Merge Sort la complessità del caso peggiore e del caso migliore

a)

sono uguali

b)

la prima è più alta della seconda

c)

la seconda è più alta della prima

d)

dipende

18.

Per dimostrare che una funzione $f\left(n\right)\ =\ \Theta\left(g\left(n\right)\right)$ cosa devo fare?

4 lines

19.

Esattamente quante istruzioni vengono eseguite dall'Insertion Sort nel caso peggiore se n è la dimensione dell'array in input? Clicca sul programma per ingrandirlo.

a)

$1+2+3+4+5+...+n$

b)

$2\ +\ 4+6+...+n$

c)

$1+3+5+...+n$

d)

$1+1+1+1+1+...\ \left(n\ volte\right)$

20.

La complessità del caso medio di una algoritmo NON può essere

a)

uguale a quella del caso migliore

b)

uguale a quella del caso peggiore

c)

più bassa di quella del caso migliore

d)

più bassa di quella del caso peggiore

21.

Nel Quick Sort l'elemento pivot divide:

a)

gli elementi già ordinati da quelli non ancora ordinati

b)

gli elementi minori del pivot da quelli maggiori del pivot

c)

gli elementi da ordinare da quelli da non ordinare

d)

nessuna delle altre risposte

22.

Nel caso migliore del Quick Sort: ad ogni divisione della sequenza di n elementi in due sottosequenze, quanto sono grandi le due sottosequenze?

a)

1 e n-1

b)

n/2 e n/2

c)

n/4 e 3/4 n

d)

Varia ad ogni divisione

23.

Nel caso peggiore del Quick Sort: ad ogni divisione della sequenza di n elementi in due sottosequenze, quanto sono grandi le due sottosequenze?

a)

1 e n-1

b)

n/2 e n/2

c)

n/4 e 3/4 n

d)

Varia ad ogni divisione

24.

Qual è la complessità di questo algoritmo se n è la dimensione dell'array?

a)

$O\left(n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(\log_{ }n\right)$

d)

$O\left(n\ \log_{ }n\right)$

25.

Se ho un algoritmo A implementato mediante una funzione ricorsiva, qual è la complessità di A?

a)

è quella della prima esecuzione della funzione

b)

è la somma di tutte le esecuzioni ricorsive della funzione

c)

è la media di tutte le esecuzioni ricorsive della funzione

d)

è quella di un'esecuzione qualsiasi della funzione

26.

In un automa a stati finiti completo, se so che quando è nello stato S l'automa non leggerà mai l'input i (e anche se lo leggesse non avrebbe nessun effetto sull'automa):

a)

non creo la transizione corrispondente

b)

creo la transizione corrispondente verso un altro stato qualsiasi

c)

creo la transizione corrispondente verso S stesso (loop)

d)

creo la transizione corrispondente verso uno stato che aggiungo appositamente (ad es. stato di errore)

27.

Qual è la complessità del problema dello zaino (Knapsack problem)?

a)

$O\left(n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(n^k\right)\$ con k molto alto

d)

Non polinomiale

28.

Il problema di controllare le fonti di una notizia per capire se è fake è un problema di

a)

decisione

b)

ricerca

c)

enumerazione

d)

ottimizzazione

29.

Il problema di trovare e pubblicare le notizie del giorno è un problema di

a)

decisione

b)

ricerca

c)

enumerazione

d)

ottimizzazione

30.

Il problema di trovare la notizia n. 1 nei trend topics (cioè la più discussa) è un problema di

a)

decisione

b)

ricerca

c)

enumerazione

d)

ottimizzazione

31.

Se un problema non è né in P né in NP

a)

non è computabile

b)

è computabile in tempo polinomiale da una MTND

c)

è computabile in tempo più che polinomiale da una MTND

d)

non è computabile in tempo polinomiale da una MT normale o da una MTND

32.

Quale delle seguenti affermazioni è vera riguardo un qualsiasi problema S?

a)

Se S è in P allora è anche in NP

b)

Se S è in NP allora è anche in P

c)

Se S è in P allora è non è in NP

d)

Se S è in NP allora è non è in P

33.

Cosa è possibile in una macchina di Turing non deterministica (MTND) che non è possibile in una macchina di Turing normale?

a)

Da uno stato possono uscire più transizioni che leggono lo stesso simbolo sul nastro

b)

Da uno stato possono uscire più transizioni che vanno verso lo stesso stato di destinazione

c)

Da uno stato possono uscire più transizioni che scrivono lo stesso simbolo sul nastro

d)

Da uno stato possono uscire più transizioni che spostano la testina nella stessa direzione

34.

Qual è l'ipotesi corrente riguardo alla relazione tra P e NP?

a)

$P\ \subset NP$

b)

$NP\subset P$

c)

$P\ \equiv NP$

d)

Non c'è nessuna ipotesi al riguardo

35.

Come posso definire la differenza tra un problema in P ed uno in NP in maniera informale? (Senza riferirsi alle macchine di Turing)

4 lines

36.

L'Halting problem è

a)

in P

b)

fuori da P ma dentro NP

c)

fuori da NP ma dentro l'insieme dei problemi decidibili

d)

fuori dall'insieme dei problemi decidibili

37.

Perché il modello della macchina di Turing è importante ancora oggi nell'ambito della computabilità?

4 lines

38.

Un problema è trattabile se

a)

è in P

b)

é in NP

c)

è computabile

d)

è risolvibile da un calcolatore moderno

39.

Il problema di trovare tutti i fattori di un numero è

a)

trattabile ma non decidibile

b)

decidibile ma non trattabile

c)

decidibile e trattabile

d)

non decidibile e non trattabile

40.

Tra le funzioni di complessità fattoriale, polinomiale, esponenziale, costante: qual è la più costosa?

a)

costante

b)

polinomiale

c)

fattoriale

d)

esponenziale

41.

Tra le funzioni di complessità fattoriale, polinomiale, esponenziale, costante: qual è la meno costosa?

a)

costante

b)

polinomiale

c)

fattoriale

d)

esponenziale

42.

A1 e A2 sono due algoritmi che risolvono lo stesso problema, ma:

A1 è $\Theta\left(2^x\right)$ mentre A2 è $\Theta\left(x!\right)$

Quindi:

a)

A1 è più veloce di A2

b)

A2 è più veloce di A1

c)

hanno un costo equiparabile per grandi input

d)

Nessuna delle atre risposte

43.

Quali conseguenze avrebbe la scoperta che $P\ \equiv\ NP$ ?

4 lines

Informatica teorica

Total questions: 43

Worksheet time: 40mins

Similar Resources on Wayground