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? ![](../../images/mp3.jpg)
02 Quali sono i due aspetti che dovremmo considerare per la complessità di un
algoritmo? Uno dei due viene ignorato. Quale e perchè. ![](../../images/mp3.jpg)
03 Qual'è l'obiettivo dello studio della complessità computazionale? ![](../../images/mp3.jpg)
04 Quale unità di misura è stata scelta per la complessità
computazionale? ![](../../images/mp3.jpg)
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? ![](../../images/mp3.jpg)
07 Cosa rappresenta la 'n' nella notazione C(n) che indica la complessità
computazionale di un algoritmo? ![](../../images/mp3.jpg)
08 Perchè si parla di complessità asintotica? ![](../../images/mp3.jpg)
09 In riferimento ad un algoritmo di solito non c'è una sola complessità ma
bisogna ragionare per casi. Quali? ![](../../images/mp3.jpg)
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? ![](../../images/mp3.jpg)
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? ![](../../images/mp3.jpg)
14 Cosa sono i problemi 'intrattabili'? Come li possiamo gestire? ![](../../images/mp3.jpg)
15 Che cosa si intende per operazione significativa? ![](../../images/mp3.jpg)
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)
|