Introduzione allo studio dell'informatica teorica: differenze tra le versioni

La scomposizione del presente corso in tre moduli ci permette di strutturare la presentazione in tre parti: la prima centrata sul concetto di formalismo, la seconda sulle idee riguardanti la computabilità e la terza sulla complessità computazionale.

 

Indubbiamente, la necessità di valutare le qualità di un procedimento pensato per affrontare una computazione presuppone l'esistenza di un metodo che permetta di analizzarlo.

 

La seconda caratteristica, ossia la funzionalità all'analisi, richiede una profonda conoscenza di cosa si intenda per caratteristiche e per prestazioni degli algoritmi e sarà premura di questo corso trattare tali aspetti.

 

Sebbene gli automi non siano gli unici formalismi possibili bisogna ammettere che questa categoria merita un discorso a parte.

 

# un ''programma'' che coordina le attività dell'automa.

 

Il concetto di ''computazione'' è indissolubilmente legato a quello di ''problema''; la sequenza delle azioni che si compiono durante una computazione può infatti essere interpretata come il procedimento seguito durante la soluzione di un problema.

 

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à.

 

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.