Scheda di esercizi di Algoritmi e complessità con soluzioni

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

1. ALeggi, calcola, scrivi
2. BIndovina, verifica, ripeti
3. CDividi, risolvi (impera), combina
4. DOrdina, cerca, restituisci

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

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

Che cos'è un algoritmo?

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

Un algoritmo greedy (goloso):

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

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ANo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione
2. BNo, perché per n grande n³ è minore di n²
3. CSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
4. DSì, ma solo se n è minore di 100

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

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

Quale definizione della classe NP è corretta?

1. AProblemi che non si possono risolvere in tempo polinomiale
2. BProblemi che non sono polinomiali
3. CProblemi che nessun algoritmo può risolvere
4. DProblemi decisionali le cui risposte sì possono essere verificate in tempo polinomiale dato un certificato

Il problema della fermata dimostra che:

1. AI cicli andrebbero evitati
2. BNessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma
3. COgni programma prima o poi si ferma
4. DAlcuni programmi girano più velocemente su computer più veloci, quindi la terminazione dipende dall'hardware