Loriano Storchi's HomePage


[Home] [CV and Research] [Any Other Business] [Where Contact Info] [Lecture Motes]

Della complessita' (2002)

Di seguito tentero' di illustrare brevemente alcuni aspetti del concetto di complessita', partendo dai concetti basilari, quali il concetto di alfabeto, per arrivare sino alla definizione di complessita' secondo Kolmogorov.

L'Alfabeto


In matematica avendo a che fare con oggetti differenti, questi possono essere identificati da una differente sequenza di caratteri o stringa, l'insieme dei caratteri costituisce appunto un alfabeto. In generale alfabeti differenti contengono un numero differente di caratteri o simboli. Indichiamo con l'alfabeto e con il numero di caratteri che costituiscono l'alfabeto dato. E' ovvio attendersi che, dato un certo numero N di oggetti che si vogliono rappresentare e dato l'afabeto, la lunghezza della stringa di caratteri necessaria a rappresentare uno qualsiasi degli N oggetti variera' in lunghezza a seconda del valore di n, oltre che ovviamente in dipendenza del metodo rappresentativo adottato. Maggiore e' n minore in media sara' la lunghezza delle stringhe necessarie a rappresentare gli N oggetti dati, il tutto ovviamente in dipendenza del metodo di rappresentazione adottato.

Dati dunque n (= numero di caratteri che compongono l'alfabeto) ed N (= numero di oggetti da arppresentare) parametri indichiamo con la lunghezza della piu' lunga stringa necessaria a rappresentare uno degli N oggetti dati. Indichiamo invece con il valore minimo di al variare della rappresentazione scelta. Esemplificando:

(1)


dove L rappresenta l'insieme delle massime lunghezze di stringa competenti alle varie rappresentazioni possibili dato l'afabeto e l'insieme degli oggetti. Ci siamo in questo modo svincolati dal metodo di rappresentazione, ed abbiamo identificato un numero caratteristico della lunghezza di stringa in realzione all'alfabeto.
TO BE COMPLETED AND CHECKED

[Home] [CV and Research] [Any Other Business] [Where Contact Info] [Lecture Motes]