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)


Tutti i marchi registrati e i nomi dei prodotti menzionati appartengono ai rispettivi proprietari.

Inviare a camuso@bigfoot.com un messaggio di posta elettronica contenente domande o commenti su questo sito Web.

Aggiornato il: 04-11-07.