Kolmogorovi keerukus

Allikas: Vikipeedia
Jump to navigation Jump to search
Pildil on osa Mandelbroti fraktalist. Selle pildi kõigi pikslite (täismõõtmetes 3200 × 2400 px) värviinformatsiooni edasiandmiseks kuluks 23 MB (kui iga piksli tarbeks eraldada 24 bitti ehk 8 bitti igale RGB komponendile). Samas oleks võimalik genereerida see pilt lühikese arvutiprogrammi abil, kui ette anda selle fraktali moodustamise reeglid ja pildinurkade koordinaadid. Seega on selle pildi Kolmogorovi keerukus märgatavalt väiksem kui 23 MB

Kolmogorovi keerukus väljendab lõpliku bitijada genereerimise algoritmilist keerukust. See põhineb arusaamal, et mõnede asjade puhul on lõpptulemusest märgatavalt lihtsam ära kirjeldada selle saavutamiseks vajalikke reegleid.

See on nimetatud vene teadlase Andrei Kolmogorovi järgi, kes avaldas sel teemal esimese artikli 1963. aastal. Iseseisvalt jõudis sama teooriani ka Argentina-Ameerika teadlane Gregory Chaitin, kelle auks on seda nimetatud ka Kolmogorov-Chaitini keerukuseks.

Välislingid[muuda | muuda lähteteksti]