INFORMATICA - COMPLESSITA' DI KOLMOGOROV

Considerando una sequenza numerica binaria definita è possibile riprodurla in diversi modi. Uno dei più semplici e copiarla così com'è. Un altro è trovare un algoritmo (diverso dalla copia bit x bit) che la generi. Se ad esempio si studia
010101010101010101010101...
l'algoritmo che la genera è abbastanza semplice, basta che alterni 0 ed 1 regolarmente. Al contrario, per la sequenza
011011011111001101010101111001101011...
potrebbe non risultare così semplice trovare un algoritmo elementare che la descriva.

La complessità di Kolmogorov (anche detta complessità algoritmica) K di una sequenza binaria S è (semplificando un poco) la dimensione in bit dell'algoritmo a dimensione minima che riproduce S.

La prima sequenza
010101010101010101010101...
ha dimensione infinita ma l'algoritmo che la genera può essere descritto in maniera finita, ad esempio:
a) make_s(X) = write(X) and make_s(not(X));
b) loop_forever(write(01));

Si può dimostrare che se esiste un algoritmo che genera la sequenza S la complessità di Kolmogorov di S può essere calcolata a meno di un parametro additivo dipendente dal linguaggio di programmazione usato. Per una sequenza binaria finita S = s1, s2, s3,..., sn questo è molto semplice da applicare dato che l'algoritmo banale (di copia) che genera S è write(s1),write(s2), write(s3)...,write(sn).

marcomattiucci.it

Informatica:

Sistemi complessi: