Utente:AmaliaSantocchio/sandbox

Tempo e Spazio nella Computazione

La teoria della complessità

La teoria della complessità analizza le risorse necessarie a risolvere un problema; le più importanti sono:

• tempo, cioè il numero di passaggi in un calcolo prima che la macchina si fermi;
• spazio, cioè la capacità di immagazzinare dati di un calcolatore e, in un macchina di Turing, il numero di celle visitate.

Un altro approccio consiste nella misura della complessità di un oggetto in base alla grandezza del più piccolo programma che è in grado di descriverlo.

Notazioni tecniche

Definiamo:

• $\mathrm {A}$ un alfabeto finito
• $\mathrm {A} ^{*}$ il numero finito di elementi di $\mathrm {A}$
• Problema un sottoinsieme di $\mathrm {A} ^{*}$
• Istanza un elemento di $\mathrm {A} ^{*}$
• Grandezza di un istanza $s$, e la indichiamo con $|s|$, la sua lunghezza
• $M$ una macchina di Turing
• $f$ una funzione da $\mathrm {A} ^{*}$ in $\mathrm {A} ^{*}$; la funzione è calcolabile da $M$ se per ogni stringa $s$ appartenente ad $\mathrm {A} ^{*}$, $M$ si arresta sul valore $f(s)$
• $P$ problema risolvibile se esiste un $M$ tale da riuscire a calcolare $f_{P}$, la funzione caratteristica di $P$

Computabilità

I problemi risolvibili possono essere classificati in base al tempo e allo spazio richiesti per la loro risoluzione. Sia $f_{1}$una funzione calcolabile, $s_{1}$ una stringa ed $M_{1}$ una macchina di Turing in grado di calcolarla; si dice che $f_{1}$ è calcolabile in un tempo $T(n)$dopo un certo numero di passaggi indicato con $O(T(|s|))$ e calcolato moltiplicando una costante $c$e $T(|s|)$. Quindi $f_{1}$è una funzione calcolabile se esiste una macchina di Turing tale che data una stringa $s$ si fermi dopo $O(T(|s|))$ riquadri sul suo nastro.

Sia $P_{1}$un problema; si dice che esso sia risolvibile:

• in un tempo $T(n)$ se la sua funzione caratteristica è calcolabile in un tempo $T(n)$;
• in uno spazio $S(n)$se la sua funzione caratteristica è calcolabile in un tempo $S(n)$.

Esempi

Siano $\mathrm {A} _{1}$un alfabeto composto da due simboli $\mathrm {A} _{1}=\{a;b\}$, $\mathrm {A} _{1}^{*}$l'insieme finito delle stringhe composte di $a$e $b$, $PAL$il problema definito lasciando le stringhe palindrome di $\mathrm {A} _{1}^{*}$; questo problema è risolvibile in un tempo $n^{2}$controllando che la prima e l'ultima lettera siano uguali ed eliminandole fino ad azzerare le lettere o lasciarne solo una. Un algoritmo necessita di un numero di passaggi pari a $cn^{2}$ per risolvere il problema, per qualche $c>0$.

La tabella della verità è risolvibile in uno spazio $n$e nel tempo $2^{n}$.

Problemi risolvibili in un tempo polinomiale

La classe dei problemi risolvibili in un tempo polinomiale è una tra le più complesse.

Una funzione $f_{2}$ è calcolabile in un tempo polinomiale se esiste un polinomio $p$ per cui $f_{2}$ è calcolabile in un tempo $p(n)$.

un problema è risolvibile in un tempo polinomiale se se la sua funzione caratteristica è calcolabile in un tempo polinomiale.