DOMANDE SULLA COMPLESSITA' COMPUTAZIONALE DEGLI ALGORITMI
Clicca sull'icona con la nota per ASCOLTARE le risposte!!
01 Di cosa si occupa lo studio della complessità computazionale degli
algoritmi? 
02 Quali sono i due aspetti che dovremmo considerare per la complessità di un
algoritmo? Uno dei due viene ignorato. Quale e perchè.
03 Qual'è l'obiettivo dello studio della complessità computazionale?
04 Quale unità di misura è stata scelta per la complessità
computazionale?
05 Perchè non ha senso misurare il tempo di esecuzione di un algoritmo per
stimare la sua complessità? (la risposta è contenuta in quella alla domanda 04)
06 Com'è possibile determinare il tempo di esecuzione di un algoritmo nota la
sua complessità computazionale?
07 Cosa rappresenta la 'n' nella notazione C(n) che indica la complessità
computazionale di un algoritmo?
08 Perchè si parla di complessità asintotica?
09 In riferimento ad un algoritmo di solito non c'è una sola complessità ma
bisogna ragionare per casi. Quali?
10 Che cosa significa quando si afferma che la C(n) di un algoritmo è 'o grande'
di n2 ? E 'o piccolo' ?
11 Quali categorie di complessità computazionali esistono?
12 Cosa si intende per complessità polinomiale? E non polinomiale? (vedi domanda precedente)
13 Quali conclusioni si possono trarre dal confronto tra complessità polinomiali
e non polinomiali?
14 Cosa sono i problemi 'intrattabili'? Come li possiamo gestire?
15 Che cosa si intende per operazione significativa?
16 Fa un esempio di problema intrattabile (risposta: quello del commesso viaggiatore o quello dello zaino)
17 Descrivi il problema del commesso viaggiatore (vedi dispense)
18 Descrivi il problema del 'knapsack' (zaino)
(vedi dispense)