Scheda di esercizi di Algoritmi e complessità con soluzioni

Quali sono i tre passi di un algoritmo divide et impera?

1. ADividi, risolvi (impera), combina
2. BLeggi, calcola, scrivi
3. CIndovina, verifica, ripeti
4. DOrdina, cerca, restituisci

Quale di queste cresce più lentamente quando n diventa grande?

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

Che cos'è un algoritmo?

1. AUna struttura dati che memorizza numeri
2. BUn linguaggio di programmazione progettato per scrivere formule matematiche
3. CUna sequenza finita di passi ben definiti che risolve un problema
4. DQualsiasi programma con un'interfaccia grafica

Una funzione esegue un ciclo di n iterazioni e poi, separatamente, un altro ciclo di n iterazioni. Qual è la sua complessità temporale?

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

Che cosa significa che un problema ha una sottostruttura ottima?

1. AOgni sottoproblema ha la stessa dimensione
2. BUna soluzione ottima può essere costruita da soluzioni ottime dei suoi sottoproblemi
3. CIl problema si può risolvere in tempo costante
4. DIl problema ha esattamente una soluzione ottima, condivisa da ogni sottoproblema

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

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

Quale di questi problemi di soddisfacibilità è noto per essere risolvibile in tempo polinomiale?

1. ASAT generale su formule in forma normale congiuntiva
2. B2-SAT, in cui ogni clausola ha al massimo due letterali
3. C3-SAT, in cui ogni clausola ha esattamente tre letterali
4. DLa soddisfacibilità dei circuiti

Quale tecnica garantisce al quicksort un tempo di esecuzione atteso O(n log n) su qualsiasi input?

1. AOrdinare l'input prima di eseguire il quicksort
2. BScegliere sempre il primo elemento
3. CUsare la ricorsione solo sul lato sinistro
4. DScegliere il pivot in modo uniformemente casuale