Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale notazione descrive un limite superiore della crescita?

1. AOmega grande (Big Omega)
2. BO grande (Big O)
3. CTheta grande (Big Theta)
4. DOmega piccolo (little omega)

Qual è la complessità temporale della ricerca binaria in un array ordinato?

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

Quale algoritmo di ordinamento scambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato?

1. AQuicksort
2. BMerge sort
3. CHeap sort
4. DBubble sort

Un algoritmo greedy (goloso):

1. AUsa solo la ricorsione
2. BFornisce sempre la soluzione ottima
3. CProva ogni soluzione possibile
4. DCompie la scelta localmente migliore a ogni passo

Qual è la complessità temporale di: for i = 1 to n: for j = 1 to i: lavoro O(1)?

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

Che cosa misura l'analisi ammortizzata?

1. AIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
2. BIl costo atteso su input casuali
3. CIl costo di un algoritmo sull'input migliore
4. DIl costo medio per operazione su una sequenza di operazioni nel caso peggiore

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

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

Come rileva l'algoritmo di Bellman–Ford un ciclo di peso negativo raggiungibile dalla sorgente?

1. AConta i cicli con una visita in profondità
2. BDopo V − 1 turni controlla se qualche arco può ancora essere rilassato
3. CControlla se qualche arco ha peso negativo
4. DEsegue due volte l'algoritmo di Dijkstra e confronta i due risultati delle distanze