Scheda di esercizi di Algoritmi e complessità con soluzioni

Come si chiama una crescita O(2ⁿ)?

1. ALogaritmica
2. BEsponenziale
3. CLineare
4. DPolinomiale

Come funziona il selection sort?

1. ADivide l'array a metà e le fonde
2. BInserisce ogni elemento in una parte ordinata crescente spostando gli altri
3. CTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
4. DScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato

Che cosa richiede la ricerca binaria al suo input?

1. AL'array non deve avere più di 1000 elementi
2. BLa lunghezza dell'array deve essere una potenza di due
3. CL'array deve essere ordinato
4. DL'array deve contenere solo numeri positivi

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + O(1)?

1. AO(n)
2. BO(n²)
3. CO(n log n)
4. DO(log n)

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

1. AO(log n)
2. BO(n²)
3. CO(n log n)
4. DO(n)

Perché nell'O grande la base del logaritmo di solito si omette, come in O(log n)?

1. ALogaritmi con basi diverse differiscono solo per un fattore costante
2. BI logaritmi sono sempre arrotondati a interi
3. CTutti i logaritmi in informatica hanno base 10, quindi è sottintesa
4. DLa base conta solo per n piccolo

Che cosa seguirebbe se qualcuno trovasse un algoritmo in tempo polinomiale per un problema NP-completo?

1. AOgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
2. BSolo quel problema passerebbe in P
3. CTutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
4. DIl problema della fermata diventerebbe decidibile

Per dimostrare che un nuovo problema X è NP-difficile, che cosa devi fare?

1. ARidurre in tempo polinomiale un problema NP-difficile noto a X
2. BDimostrare che X si può verificare in tempo polinomiale
3. CRidurre in tempo polinomiale X a un problema NP-difficile noto
4. DDimostrare che X non ha un algoritmo polinomiale per input piccoli