Strumenti Utente

Strumenti Sito


db:teoria_della_complessita_computazionale

Teoria della complessità computazionale

Approfondimenti

Info

Quest'argomento non è collegato ad altri approfondimenti correlati. Si consiglia, in ogni caso, di controllare sempre [ l'Indice ] degli Approfondimenti

Questa pagina è solo improntata in attesa di completamento da parte dei Collaboratori. Se sei interessato a collaborare attivamente con Extrapedia, leggi come fare [ Collabora ]

La Teoria della complessità computazionale si concentra sulla classificazione dei problemi computazionali in base alla loro difficoltà intrinseca e mette in relazione queste classi l'una con l'altra. Un problema computazionale è un compito risolto da un computer. Un problema di calcolo è risolvibile mediante l'applicazione meccanica di passi matematici, come un algoritmo.

Un problema è considerato intrinsecamente difficile se la sua soluzione richiede risorse significative, qualunque sia l'algoritmo utilizzato. La teoria formalizza questa intuizione, introducendo modelli matematici di computazione per studiare questi problemi e quantificare la loro complessità computazionale, cioè la quantità di risorse necessarie per risolverli, come il tempo e la conservazione. Sono anche utilizzate altre misure di complessità, come la quantità di comunicazione (utilizzata nella complessità della comunicazione), il numero di porte in un circuito (utilizzato nella complessità del circuito) e il numero di processori (usati nell'elaborazione parallela). Uno dei ruoli della Teoria della complessità computazionale è determinare i limiti pratici su ciò che i computer possono e non possono fare.

I campi strettamente connessi nell'informatica teorica sono l'analisi degli algoritmi e la Teoria della computabilità. Una distinzione fondamentale tra l'analisi degli algoritmi e la Teoria della complessità computazionale è che il primo è dedicato all'analisi della quantità di risorse necessarie per un determinato algoritmo onde risolvere un problema, mentre la seconda pone una domanda più generale su tutti i possibili algoritmi che potrebbero essere utilizzati per risolvere lo stesso problema. Più precisamente, la Teoria della complessità computazionale tenta di classificare i problemi che possono o non possono essere risolti con risorse appropriatamente limitate. A sua volta, imporre restrizioni sulle risorse disponibili è ciò che distingue la complessità computazionale dalla Teoria della computabilità: quest'ultima teoria chiede quale tipo di problemi possa, in linea di principio, essere risolto algoritmicamente.


Qualora alcuni link non funzionassero, si prega di comunicarlo allo Staff - staff@extrapedia.org


db/teoria_della_complessita_computazionale.txt · Ultima modifica: 13/04/2019 16:08 (modifica esterna)