Scheda di esercizi di Algoritmi e complessità con soluzioni

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

1. ACirca n
2. BCirca n²
3. CCirca log₂ n
4. DCirca n / 2

Il tempo di esecuzione di un algoritmo è O(n). Come si chiama questa crescita?

1. ACostante
2. BQuadratica
3. CLineare
4. DLogaritmica

Un algoritmo con due cicli annidati, ciascuno eseguito n volte, ha tipicamente quale complessità?

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

Qual è la complessità temporale dell'algoritmo standard di programmazione dinamica per la sottosequenza comune più lunga di stringhe di lunghezze m e n?

1. AO(mn)
2. BO(mn log n)
3. CO(m + n)
4. DO(2^m+n)

Quale affermazione su una funzione ricorsiva senza un caso base raggiungibile è corretta?

1. ARestituisce automaticamente 0
2. BIl compilatore la trasforma sempre in un ciclo che termina in modo sicuro
3. CContinua a chiamare se stessa finché lo stack delle chiamate va in overflow
4. DViene eseguita in tempo O(1)

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

1. AI logaritmi sono sempre arrotondati a interi
2. BTutti i logaritmi in informatica hanno base 10, quindi è sottintesa
3. CLogaritmi con basi diverse differiscono solo per un fattore costante
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. CIl problema della fermata diventerebbe decidibile
4. DTutti gli algoritmi a tempo esponenziale diventerebbero subito lineari

Che cosa ha stabilito il teorema di Cook–Levin?

1. AOgni problema NP si può risolvere in tempo esponenziale
2. BIl problema della soddisfacibilità booleana (SAT) è NP-completo
3. CP è diverso da NP
4. DIl problema della fermata è indecidibile