Complessità Computazionale, Algoritmica e Tesi Di Church-Turing

Oggi in questo articolo distingueremo tra complessità computazionale (risorse) ed algoritmica (complessità descrittiva degli stessi).
I due concessi sono molto diversi e spesso vengono confusi dai non addetti ai lavori.


COMPLESSITA' COMPUTAZIONALE
La complessità computazionale identifica le risorse minime necessarie (tempo di esecuzione e quantità di memoria utilizzata inerenti le informazioni iniziali, intermedie e finali relative al problema da risolvere) per la risoluzione di un problema in funzione di un determinato tipo di input.
A cosa serve? Ci consente di capire quale algoritmo utilizzare e quando un algoritmo diventa più veloce o lento.
Possono assumere importanza anche la banda di comunicazione e il numero di porte logiche utilizzate, ma la risorsa che il più delle volte si è interessati a misurare è il tempo.
La complessità computazionale di un algoritmo è in stretta relazione con la difficoltà del problema. La difficoltà effettiva di un problema sarà data dalla complessità computazionale del miglior algoritmo che potrà essere scritto per risolvere il problema.
Il tempo di esecuzione di un algoritmo può essere misurato per ogni dato d'ingresso.
Il problema generale da risolvere deve essere scomposto in un insieme di operazioni elementari, poi va definito:

-il tempo necessario per eseguire ciascuna delle operazioni elementari

-trovare il numero di volte che ogni operazione elementare deve essere eseguita

Il tempo totale di esecuzione sarà: T totale = (T operazione elementare1 x N_numero di volte che si ripete1) + (T2 x N2)+…

Per trovare il tempo di esecuzione di un' operazione elementare vanno fatte delle ipotesi dipendenti dalla tecnologia utilizzata. Il modello deve descrivere le risorse utilizzate e il loro costo. E' consuetudine adottare un modello generico di macchina ad accesso casuale (alla memoria). In questo modello computazionale il tempo necessario per accedere a qualsiasi punto della memoria è costante (è sempre uguale).
Inoltre ogni operazione elementare richiede la stessa quantità di risorse, per essere eseguita. Queste ipotesi rendono relativamente più semplice l' analisi della complessità computazionale dell'Algoritmo.
Nel caso in cui l'analisi della complessità computazionale è fatta su tutti gli ingressi possibili e non su ingressi dati, le cose cambiano sostanzialmente.
Solitamente la complessità di un algoritmo viene "misurata" sul caso peggiore.
Il tempo di esecuzione nel caso peggiore di un algoritmo è il più lungo tempo di esecuzione su tutti gli ingressi di dimensione n. Analogamente, lo spazio di esecuzione nel caso peggiore è il più grande spazio richiesto su tutti gli ingressi di dimensione n.
Perchè? Conosce le risorse del caso "estremo" ci dà garanzia che non serviranno risorse maggiori (fa da limite superiore delle risorse che l'esecuzione dell'algoritmo richiederà).
Inoltre per alcuni algoritmi, il caso peggiore si verifica abbastanza spesso.
Per esempio, nella ricerca di un'informazione in databse, il caso peggiore dell'algoritmo si verificherà spesso se quell'informazione non è presente.
A volte la complessità è stimata considerando anche un "caso medio".
Il caso medio molto spesso è simile a quello peggiore. Solo quando è vero il contrario, cioè quando il caso peggiore è "raro" o improbabile, ha senso calcolare le risorse richieste nel caso medio.
Qui si parla di complessità temporale (i tempi affinchè l'algoritmo giunga alla soluzione sono: secondi, minuti, ore, giorni, settimane, mesi, etc).
L'algoritmo potrebbe anche richiedere una quantità di memoria eccessiva, tale da rendere impossibile la sua esecuzione (alcuni algoritmi possono funzionare per alcuni problemi e rivelarsi un buco nell'acqua per altri, proprio per quantità di memoria utilizzata).
Si misura in byte di memoria, necessari per immagazzinare le informazioni durante l'esecuzione dell'algoritmico.
Questa è una complessità spaziale.
Su internet ci sono centinaia di siti e documenti per approfondire, ad esempio: Complessità Computazionale


COMPLESSITA' ALGORITMICA
La complessità algoritmica venne descritta per la prima volta da Kolmogorov, Chaitin e Solomonoff, per questa è nota anche come teoria K-C-S.
Per algoritmo classico si fa riferimento alla macchina di Turing: ad ogni programma di un calcolatore corrisponde una macchina di Turing, ma è anche possibile definirne una universale che simula il comportamento di ogni altra.
La macchina universale è equivalente a qualsiasi calcolatore reale.
La classe degli algoritmi così come anche le classi dei dati su cui essi operano e i risultati che producono devono essere numerabili.
Un algoritmo è quindi un meccanismo di calcolo di una funzione da ℕ su ℕ (cioè dai naturali sui naturali).
Nel decennio tra il 1960 e il 1970 si giunse alla conclusione che la misura più significativa dell'efficienza di un algoritmo è l'espressione matematica del tempo che esso richiede in funzione della dimensione dei dati d'ingresso. Gli algoritmi si divisero in efficienti e inefficienti a seconda che il tempo richiesto fosse polinomiale o esponenziale.
La macchina di Turing invece è una macchina astratta di dimensioni finite, dotata di un sistema che esegue operazioni di lettura e scrittura e di un controllo che determina, attraverso l'evoluzione tra diversi stati, la sequenza di operazioni relative al problema da risolvere. Nella sua forma di base la macchina rappresenta un algoritmo di risoluzione di un problema specifico su dati d'ingresso rappresentati all'inizio sul nastro. Le condizioni di arresto dipendono dal tipo di algoritmo eseguito. Se è richiesto un risultato più complesso di una semplice decisione, la macchina si arresta quando raggiunge uno stato finale rappresentando il risultato sul nastro.

Se la macchina deve risolvere un problema di decisione, il risultato è indicato dallo stato raggiunto all'arresto.
La complessità C(x) di un problema x (o di una stringa) è la lunghezza del più piccolo programma p che eseguito da un elaboratore universale U risolve (o produce) x.

Esempio: la stringa di bit 01010101010101 è semplice, una casuale del tipo 01110101010010 è complessa (ma nulla ci vieta di pensare sia stata ottenuta da una certa regola)
Esempio: l’insieme di Mandelbrot (immagini frattali) è certamente più complesso di un immagine casuale, ma il programma che lo descrive è estremamente più sintetico

La complessità di Kolmogorov definisce invece una misura di casualità (randomness).
Essa può essere misurata anche dalla regolarità delle strutture e in questo caso sono considerati semplici i problemi caratterizzati da estrema regolarità o casualità perché c’è poco o nulla da descrivere (le immagini uniformi o casuali).
Sono complessi i problemi caratterizzati da strutture regolari "lunghe" da descrivere (le immagini frattali).
Per approfondire: Cos'è Un Algoritmo e Come Costruirlo, Una Chiacchierata Sulla Complessità Algoritmica e la Teoria Dell'Informazione e Shannon e La Teoria Dell'Informazione (Entropia, Ridondanza, Codifiche)


TESI DI CHURCH-TURING E TEST DI TURING
La nota tesi di Church afferma:

-"I problemi matematici possono essere risolti solo da operazioni matematiche"

Prima dell'avvento delle macchine (test di Turing), tutti i problemi venivano risolti dagli esseri umani, che inevitabilmente eseguivano operazioni matematiche, per cui almeno in parte la macchina e l'uomo svolgevano le stesse operazioni.
Turing completò quella tesi, affermando che:

-"Ciò che può essere calcolato da un essere umano può essere calcolato anche da una macchina"

-"Ciò che può essere calcolato da una macchina è calcolabile con cicli di operazioni e/o con funzioni ricorsive o parzialmente ricorsive"

-"Ciò che può essere calcolato da un essere umano è calcolabile con cicli e/o funzioni ricorsive o parzialmente ricorsive"

Questa tesi di Church-Turing non è dimostrabile come un teorema matematico ma è semplicemente un'ipotesi sui procedimenti usati dal cervello umano per risolvere i problemi.
Questi assunti ci suggeriscono che se riusciamo a risolvere un problema, esisterà un programma elaborato da una macchina, che lo potrebbe risolvere al posto nostro. Ma soprattutto fa sorgere il dubbio se sia possibile estendere il ragionamento non solo ai problemi matematici, ma anche a tutti gli altri e quindi se sia possibile realizzare una macchina pensante.

Ma cos'è il test di Turing? Esso idealmente prevede tre stanze comunicanti tra loro solamente con un dispositivo che permetta uno scambio domande/risposte senza vedere l'interlocutore o ascoltare la sua voce, insomma senza sapere nulla dell'altro se non il contenuto dei suoi messaggi. In una delle stanze ci sarà un giudice e nelle altre due (isolate tra di loro) un essere umano e l'ipotetica macchina pensante.
Se dopo un certo numero di scambi di messaggi il giudice sbagli nel dire quale sia la macchina e quale l'uomo, ci si troverà di fronte alla prima macchina intelligente.
Per maggiori informazioni: Test Di Turing
I più popolari algoritmi di apprendimento per le reti feed-forward (che calcolano il problema molto velocemente) sono: Perceptron, Adaline, Madeline, Cognitron, Neo-Cognitron, Competition, Boltzman, Harmony, Counter Propagation e Back Propagation.
Tutti gli algoritmi di apprendimento hanno un identico obbiettivo: ottenere una configurazione interna di pesi che permette alla rete feed-forward di svolgere una determinata funzione.
Le regole matematiche sono basate sulla teoria di Hebb o su alcune sue varianti regola di Hebb, regola Delta e regola Back Propagation.
Per approfondire: Cosa Sono Le Reti Neurali Artificiali (Intelligenza Artificiale) e Teoria Delle Reti Neurali.