Introduzione allo studio dell'informatica teorica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Barra di navigazione inferiore |
Teoria della complessità |
||
Riga 6:
}}
{| style="border: 1px solid black; height: 50px; margin-bottom: 20px; margin-top: 20px;"
| style="padding-left: 20px; padding-right: 20px;" | Corso: [[Materia:Informatica Teorica]]
| style="padding-left: 20px; padding-right: 20px;" |Prossima lezione: [[Automa a stati finiti deterministico]]
Riga 58:
La teoria della computabilità cerca di rispondere a questi interrogativi, offrendo una serie di strumenti concettuali utili per indagare le condizioni che portano all'esistenza di un algoritmo.
Il cuore della teoria della computabilità è il concetto di ''decidibilità'': sinteticamente si può dire che un problema è decidibile quando esiste un algoritmo in grado di risolverlo.
Questo argomento è stato affrontato con strategie differenti da due matematici di grande spessore: Alonzo Church ed Alan Turing. Il primo ha affrontato lo studio della computabilità impiegando un approccio molto formale basato, come vedremo, sulle funzioni ricorsive parziali; il secondo ha preferito immaginare un dispositivo concettuale in grado di implementare gli algoritmi, creando la famosa ''macchina di Turing''.
La teoria della computabilità si occupa esclusivamente dell'esistenza di un algoritmo e prescinde completamente dalle sue prestazioni, ossia non bada al modo in cui l'algoritmo in questione impiega le risorse a sua disposizione; questi aspetti saranno invece l'oggetto dello studio della teoria della complessità.
==La teoria della complessità==
In generale l'esistenza di un algoritmo non è sufficiente per renderlo utilizzabile: é possibile che richieda un quantitativo ingente di risorse o che fornisca i risultati in tempi troppo lunghi.
Affinché un algoritmo sia appetibile per le applicazioni pratiche deve fare un uso economico delle risorse a sua disposizione; in una parola, dev'essere efficiente.
L'attenzione all'efficienza porta con sé un'importante conseguenza: per analizzare l'impiego delle risorse è necessario anzitutto capire quali siano le risorse critiche per un algoritmo; è poi indispensabile trovare un modo per misurare il loro impiego.
La teoria della complessità cerca di dare una risposta a questi interrogativi, sviluppando strumenti utili per l'analisi degli algoritmi e per sviluppare previsioni ragionate sulle loro prestazioni in genere.
{| style="border: 1px solid black; height: 50px; margin-bottom: 20px;"▼
▲{| style="border: 1px solid black; height: 50px; margin-bottom: 20px; margin-top: 20px;"
| style="padding-left: 20px; padding-right: 20px;" | Corso: [[Materia:Informatica Teorica]]
| style="padding-left: 20px; padding-right: 20px;" |Prossima lezione: [[Automa a stati finiti deterministico]]
| |||