Complexitatea Kolmogorov

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În teoria informației algoritmice , complexitatea Kolmogorov (numită după matematicianul rus AN Kolmogorov ) a unui obiect (presupunând că poate fi reprezentată ca o secvență de biți, de exemplu o bucată de text), este lungimea celui mai scurt program informatician ( într-un limbaj de programare dat) care produce obiectul ca ieșire. O definiție alternativă este: cantitatea de informații conținute într-o secvență dată x exprimată ca lungimea celui mai scurt program care imprimă x și se oprește. [1]

Concept general

O parte din fractala Mandelbrot este reprezentată în această imagine. Stocarea informațiilor de culoare cu adâncime de 24 de biți ale fiecărui pixel ar necesita 1,62 milioane de octeți, dar un program de calculator simplu poate reproduce aceste 1,62 milioane de octeți folosind definiția matematică a setului Mandelbrot și coordonatele colțurilor imaginii. Prin urmare, complexitatea Kolmogorov a fișierului de program care codifică această imagine este semnificativ mai mică de 1,62 milioane de octeți.

Să presupunem că vi se dă un șir ca 111111 ... mergând de o sută de ori înainte în același mod, lungimea șirului ar fi de 100 de caractere, dar puteți scrie un program scurt care îl generează foarte ușor:

 repetați 100 
 tipărește „1” 
sfârșit repetă

Acum luați în considerare șirul „231048322087232 ..” și așa mai departe pentru o sută de cifre. Să presupunem că este un șir aleatoriu, atunci ar fi dificil să creăm un program mai scurt decât șirul în sine care l-ar putea imprima. Cu alte cuvinte, nu există nici o modalitate de a specifica acest șir cu aspect aleatoriu, altfel decât prin citarea lui cifră cu cifră. Această observație a diferenței dintre aceste două șiruri este ceea ce duce la ideea de complexitate a lui Kolmogorov. Primul șir poate fi generat de un program cu aproximativ 30 de caractere și, prin urmare, se poate spune că are 30 de octeți de informații, dar al doilea șir necesită un program de cel puțin o sută de caractere pentru a cita toate cifrele ca literal și astfel are informații de la 100 de octeți. [2] În mod clar, numărul de octeți necesari pentru un program care tipărește o sută nu este un număr bine definit, depinde de limbajul de programare utilizat. Cu toate acestea, în orice limbaj de programare putem defini complexitatea Kolomogorov ca lungimea celui mai mic program care generează șirul în cauză. Deci complexitatea este definită în raport cu un anumit limbaj de descriere. Pentru șiruri infinite lucrurile sunt puțin mai interesante, deoarece dacă nu aveți un program care va genera șirul, practic nu aveți șirul în niciun sens practic. Adică, fără un program care generează cifrele unei secvențe infinite, nu puteți defini efectiv șirul.

Notă

  1. ^ Nicolò Cesa-Bianchi, The Information and Transmission Theory - Complexity by Kolmogorov ( PDF ), on cesa-bianchi.di.unimi.it , 1 mai 2016 (arhivat din original la 24 martie 2018) .
  2. ^ (EN) Mike James, Kolmogorov Complexity , pe i-programmer.info, 2 septembrie 2013 (depus de „Original url 21 iunie 2018).

Elemente conexe

Alte proiecte

Adus de la „ https://it.wikipedia.org/w/index.php?title=Complessità_di_Kolmogorov&oldid=116626543 ”