Le doverose premesse

Lo studio della "teoria della computazione", o come viene chiamata all'UniVe, Calcolabilità e Linguaggi Formali, riguarda tre argomenti:

  • Complessità
  • Calcolabilità
  • Automi

La complessità indaga i costi di esecuzione degli algoritmi, in particolare li suddivide in classi, le cui principali sono polinomiale ed esponenziale.

La calcolabilità riguarda quali problemi siano risolvibili da un computer: per esempio, se risolvi un problema la risposta è che si può, ma se per ora non riesci non puoi sapere se il motivo è che non hai elaborato abbastanza oppure se è proprio interminabile.

Gli automi definiscono quali sono le caratteristiche di una macchina in grado di calcolare.