Complexitate

Complexitatea  este o caracteristică care reflectă gradul de dificultate pentru înțelegerea, crearea și verificarea unui sistem sau element al unui sistem [1] ; gradul de dificultate în înțelegerea și rezolvarea problemelor , sarcinilor . Complexitatea unui sistem sau element de sistem poate fi exprimată în termeni de complexitate a problemelor corespunzătoare și a sarcinilor de înțelegere, creare și verificare a acestora.

Potrivit Encyclopedia Britannica , teoria științifică a complexității are ca scop studierea unor astfel de fenomene comportamentale ale unor sisteme care nu pot fi explicate prin analiza elementelor acestor sisteme. „Complexitatea” este folosită în mod obișnuit pentru a caracteriza comportamentul emergent al sistemelor [2] . În același timp, complexitatea comportării sistemului poate depăși semnificativ, polinomial cu un grad ridicat sau mai mult, suma complexităților comportării elementelor incluse în sistem [3] .

Din 2010, mai multe abordări sunt folosite pentru a caracteriza conceptul de complexitate [4] . Neil Johnson susține că „chiar și printre oamenii de știință nu există o definiție unică a complexității – iar acest concept științific a fost explicat în mod tradițional cu exemple specifice”. În cele din urmă, Johnson acceptă definiția „științei complexității” ca știință care „studiază fenomenele care apar ca urmare a interacțiunii unui set de obiecte” [5] .

Complexitate neordonată și ordonată

În 1948, Warren Weaver a făcut distincția între două forme de complexitate: complexitatea neordonată și complexitatea ordonată [6] . Fenomenele de complexitate neordonată sunt tratate folosind teoria probabilității și mecanica statistică , în timp ce complexitatea ordonată se ocupă de fenomene care necesită luarea în considerare a unui număr semnificativ de factori în același timp, interrelaționați într-un întreg coerent. Lucrarea lui Weaver din 1948 a influențat cercetarea ulterioară a complexității [7] .

Una dintre problemele în abordarea problemei complexității este formalizarea distincției intuitive între sistemele cu un număr mare de interacțiuni aleatorii și sisteme în care numărul de interacțiuni, deși mare, dar interacțiunile în sine apar în cadrul anumitor restricții și sunt asociate cu un corelație între elemente. Weaver a rezolvat această problemă făcând distincția între complexitatea neordonată și ordonată.

Potrivit lui Weaver, complexitatea dezordonată apare din faptul că un anumit sistem are un număr foarte mare de părți. Deși interacțiunile părților într-o situație de complexitate dezordonată pot fi privite ca în mare măsură aleatorii, proprietățile sistemului în ansamblu pot fi înțelese folosind metode probabilistice și statistice.

Un prim exemplu de complexitate dezordonată sunt moleculele de gaz dintr-un recipient. Unii sugerează că un sistem de complexitate dezordonată poate fi comparat cu simplitatea (relativă) a orbitelor planetare - aceasta din urmă poate fi prezisă prin aplicarea legilor mișcării lui Newton . Desigur, majoritatea sistemelor reale, inclusiv orbitele planetare, devin în cele din urmă imprevizibile din punct de vedere teoretic chiar și folosind dinamica newtoniană, așa cum a descoperit teoria haosului modern .

Complexitatea ordonată, în viziunea lui Weaver, este interacțiunea non-aleatorie sau corelată între părți. Aceste interacțiuni corelate creează o structură coordonată care, ca sistem, poate interacționa cu alte sisteme. Un sistem coordonat prezintă proprietăți care nu sunt caracteristice părților sale. Se poate spune că aspectul ordonat al acestui sistem „iese la iveală” fără nicio „mână călăuzitoare”.

Numărul de părți nu trebuie să fie foarte mare pentru ca un anumit sistem să aibă proprietăți emergente . Un sistem de complexitate ordonat poate fi înțeles prin proprietățile (comportamentul) prin modelare și simulare , în special prin simulare pe calculator . Un exemplu de complexitate ordonată este un bloc ca mecanism viu, cu locuitorii săi ca părți ale unui sistem [8] .

Surse și factori

Există de obicei principii care pot fi folosite pentru a explica originea complexității într-un sistem dat.

Sursa complexității neordonate este numărul mare de părți din sistem și lipsa corelației dintre elementele sale.

În cazul sistemelor vii auto-organizate, complexitatea ordonată utilă decurge din faptul că organismele mutante sunt selectate pentru supraviețuire de către mediul lor datorită capacității lor de reproducere diferențiate, sau cel puțin avantajelor față de organismele complexe mai puțin ordonate [9] .

Complexitatea unui obiect sau a unui sistem este o proprietate relativă. De exemplu, pentru multe funcții (sarcini), complexitatea de calcul, cum ar fi timpul de calcul, este mai mică atunci când sunt utilizate mașini Turing cu mai multe benzi decât atunci când sunt utilizate mașini Turing cu o singură bandă. Mașinile cu acces aleatoriu la memorie pot reduce și mai mult complexitatea timpului (Greenlaw și Hoover 1998: 226), în timp ce mașinile inductive Turing pot chiar reduce clasa de complexitate a unei funcții, limbaj sau set (Burgin 2005). Acest lucru arată că instrumentele de activitate pot fi un factor important de complexitate.

Concretizarea conceptului de complexitate în diverse domenii ale științei

În diferite domenii ale științei, sunt utilizate definiții specializate, mai restrânse ale complexității:

Alte domenii ale științei introduc concepte de complexitate mai puțin precis definite:

Explorând

Complexitatea a făcut întotdeauna parte din mediul nostru și, prin urmare, multe domenii ale științei se ocupă de sisteme și fenomene complexe. Pe de o parte, ceva care este oarecum dificil - afișarea variației fără aleatorie  - este de cel mai mare interes, având în vedere rezultatele găsite în cursul cercetării.

Termenul „complex” este adesea confundat cu termenul „confuz”. În teoria sistemelor, diferența dintre complex și complex este diferența dintre nenumăratele „mișcări” de conectare și soluții „integrate” eficiente, adică „complex” este opus „independent”, iar „încurcat” este opus „simplu”.

Deși în unele domenii ale științei au fost propuse definiții specifice ale complexității, recent a existat o mișcare de regrupare a observațiilor din domenii diferite pentru a studia complexitatea ca un singur fenomen, fie că este vorba de furnici , creier uman , piețe de valori sau sisteme sociale [16]. ] . Un astfel de grup interdisciplinar de domenii este teoria ordinii relaționale .

Subiecte de cercetare

Comportament

Se spune adesea că comportamentul unui sistem complex este legat de apariție și auto-organizare . Teoria haosului a explorat sensibilitatea sistemelor la schimbările în condițiile inițiale ca una dintre cauzele comportamentului complex.

Mecanisme

Evoluțiile recente în viața artificială , calculul evolutiv și algoritmii genetici au condus la o atenție sporită asupra complexității și sistemelor adaptative complexe .

Simulări

În științele sociale  , studiul apariției macro-proprietăților din micro-proprietăți, cunoscut și în sociologie ca macro-microviziune. Acest subiect este denumit în mod obișnuit complexitate socială , care este adesea asociată cu utilizarea simulărilor pe computer în științele sociale, cum ar fi sociologia computațională .

Sisteme

Teoria sistemelor s-a preocupat de mult timp de studiul sistemelor complexe (mai recent, teoria complexității și sistemele complexe au fost, de asemenea, folosite ca denumire a domeniului). Aceste sisteme sunt utilizate în cercetare într-o varietate de discipline, inclusiv biologie , economie , științe sociale și tehnologie . Recent, complexitatea a devenit un subiect natural de interes pentru sistemele socio-cognitive din lumea reală și pentru noi cercetări în sistemică . Sistemele complexe tind să aibă multe dimensiuni , sunt neliniare și sunt dificil de modelat. În anumite circumstanțe, ele pot prezenta un comportament de dimensiuni reduse.

Date

În teoria informației, teoria informației algoritmice se ocupă de complexitatea rândurilor de date.

Corzile complexe sunt mai greu de comprimat. Deși intuiția ne spune că acest lucru poate depinde de codecul utilizat pentru a comprima șirul (un codec ar putea fi teoretic realizat în orice limbaj arbitrar, inclusiv unul în care o comandă „X” foarte mică ar putea determina computerul să scoată un șir foarte complex, cum ar fi "18995316"), oricare două limbi Turing-complete pot fi implementate unul în celălalt, ceea ce înseamnă că lungimea a două codificări în limbi diferite nu va varia cu mai mult decât lungimea "limbii de traducere", care ajunge să fie fiind neglijabilă pentru șiruri de date suficient de lungi.

Aceste măsuri de complexitate algoritmică atribuie de obicei valori mari zgomotului aleatoriu . Cu toate acestea, cei care studiază sisteme complexe nu văd aleatorietatea ca complexitate.

Entropia informațională este, de asemenea, uneori folosită în teoria informației ca măsură a complexității, dar entropia este, de asemenea, mare atunci când nu este vorba despre complexitate, ci despre aleatoriu. În teoria informației, aleatorietatea nu este considerată un fel de complexitate, iar definiția sa a complexității este utilă în multe aplicații.

Lucrările recente în învățarea automată au explorat complexitatea datelor, deoarece afectează performanța algoritmilor de clasificare supravegheați . Ho și Basu prezintă un set de măsuri de complexitate pentru probleme de clasificare binară [17] .

Măsurile de complexitate acoperă în general:

Analiza durității instanței este o nouă abordare care vizează în primul rând identificarea cazurilor care ar fi putut fi clasificate greșit (sau, cu alte cuvinte, identificarea cazurilor care pot fi cele mai dificile) .  Caracteristicile cazurilor care ar fi putut fi clasificate greșit sunt apoi măsurate pe baza „scorurilor de dificultate”. „Măsurile de dificultate” se bazează pe mai multe metode de învățare supravegheată, cum ar fi măsurarea numărului de vecini incompatibili sau probabilitatea de a atribui corect o etichetă de clasă dată de caracteristicile de intrare. Informațiile furnizate de măsurile de dificultate sunt explorate pentru a fi utilizate în meta -learning pentru a determina pentru care seturi de date filtrarea (sau eliminarea cazurilor suspecte zgomotoase din setul de antrenament) este cea mai promițătoare [19] și poate fi extinsă în alte domenii. .

În recunoașterea moleculară

Un studiu recent bazat pe modelarea moleculară și pe constante de corespondență descrie recunoașterea moleculară ca un fenomen de organizare [20] . Chiar și pentru moleculele mici, cum ar fi carbohidrații , procesul de recunoaștere nu poate fi prezis sau proiectat, inclusiv presupunând că puterea fiecărei legături individuale de hidrogen este cunoscută cu precizie.

Aplicații

Teoria complexității computaționale se ocupă cu studiul complexității rezolvării problemelor. Complexitatea computațională poate fi abordată din diferite perspective. Această complexitate a unei probleme poate fi măsurată prin cantitatea de timp, memorie sau alte resurse necesare pentru a o rezolva. Timpul și spațiul sunt doi dintre cei mai importanți și mai des utilizați parametri în analiza problemelor de complexitate.

Problemele sunt clasificate într-o clasă de dificultate în funcție de timpul necesar pentru rezolvarea unui algoritm - de obicei un program de calculator - în funcție de dimensiunea problemei. Unele probleme sunt greu de rezolvat, altele sunt ușor. Deci, există probleme, a căror soluție, în conformitate cu algoritmul, nu poate fi finalizată într-un timp mai puțin decât exponențial dependent de dimensiunea problemei. Un exemplu de astfel de problemă este problema vânzătorului ambulant , care se rezolvă în timp (unde n  este dimensiunea rețelei de vizitat - numărul de orașe pe care vânzătorul trebuie să le viziteze exact o dată). Pe măsură ce dimensiunea rețelei crește, timpul necesar pentru a găsi o rută crește (mai mult decât) exponențial.

Deși, teoretic, problema poate fi rezolvată cu ajutorul calculelor, totuși, din cauza cerințelor excesiv de mari de timp sau spațiu, rezolvarea ei devine practic imposibilă. Astfel de probleme sunt numite practic de nerezolvat .

Există o altă formă de complexitate numită ierarhică . Această formă de complexitate reflectă aspectul ierarhic al sistemelor, sarcinilor și problemelor și este ortogonală cu formele de complexitate discutate anterior, care pot fi numite, în consecință, forme orizontale de complexitate.

Vezi și

Note

  1. ↑ ISO/IEC/IEEE 24765:2017 Ingineria sistemelor și software - Vocabular
  2. ↑ Complexitatea (teoria științifică  ) . — articol din Encyclopædia Britannica Online . Data accesului: 14 ianuarie 2021.
  3. ↑ Johnson, Steven. Apariția: viețile conectate ale furnicilor, creierelor, orașelor . - New York : Scribner, 2001. - P. 19. - ISBN 978-3411040742 .
  4. ↑ JM Zayed, N. Nouvel, U. Rauwald, OA Scherman. Complexitatea chimică - auto-asamblare supramoleculară a blocurilor de construcție sintetice și biologice în apă . Chemical Society Reviews, 2010, 39, 2806-2816 http://pubs.rsc.org/en/Content/ArticleLanding/2010/CS/b922348g
  5. ↑ 1 2 Johnson, Neil F. Chapter 1: Two's company, three is complexity // Simply complexity: A clear guide to complexity theory. - Oneworld Publications, 2009. - P. 3. - ISBN 978-1780740492 .
  6. ^ Weaver, Warren (1948). „Știință și complexitate” (PDF) . om de știință american . 36 (4): 536-44. PMID  18882675 . Consultat 2007-11-21 .
  7. ↑ Johnson, Steven. Apariția: viețile conectate ale furnicilor, creierului, orașelor și software-ului . — New York : Scribner, 2001. — P.  46 . - ISBN 978-0-684-86875-2 .
  8. ↑ Jacobs, Jane. Moartea și viața marilor orașe americane . — New York: Random House, 1961.
  9. ↑ Ulanowicz, Robert, „Ecology, the Ascendant Perspective”, Columbia, 1997
  10. ↑ Burgin, M. (1982) Complexitatea și dualitatea generalizată a Kolmogorov în teoria calculelor, Notices of the Russian Academy of Sciences, v.25, nr. 3, pp. 19-23
  11. ↑ Crutchfield, JP (1989). „Deducerea complexității statistice”. Scrisori de revizuire fizică . 63 (2): 105-108. Cod biblic : 1989PhRvL..63..105C . DOI : 10.1103/PhysRevLett.63.105 . PMID 10040781 . 
  12. ↑ Crutchfield, JP (1999). „Profunzimea termodinamică a stărilor cauzale: complexitatea obiectivă prin reprezentări minime”. Analiza fizică E. 59 (1): 275-283. Cod biblic : 1999PhRvE..59..275C . DOI : 10.1103/PhysRevE.59.275 .
  13. ↑ Grassberger, P. (1986). „Spre o teorie cantitativă a complexității autogenerate”. Jurnalul Internațional de Fizică Teoretică . 25 (9): 907-938. Cod biblic : 1986IJTP ...25..907G . doi : 10.1007/ bf00668821 .
  14. ↑ Prokopenko, M. (2009). „Un primer teoretic informațional despre complexitate, auto-organizare și apariție”. complexitate . 15 (1): 11-28. Cod biblic : 2009Cmplx..15a..11P . DOI : 10.1002/cplx.20249 .
  15. ↑ Un exemplu din teoria rețelelor complexe: „ Complex Structures and International Organizations ” ( Grandjean, Martin (2017). „Analisi e views delle reti in storia. L’esempio della cooperazione intellettuale della Società delle Nazioni”. Memoria e Ricerca ( 2): 371-393 DOI : 10.14647/87204 .Vezi și: versiunea franceză ).
  16. ↑ Bastardas-Boada, Albert. „Complexica ca domeniu meta-transdisciplinar” . Congres Mondial Pour la Pensee Complexe. Les Défis d'Un Monde Globalisé. (Paris, 8-9 decembrie). unesco .
  17. ↑ Ho, T.K.; Basu, M. (2002). „ Măsuri de complexitate a problemelor de clasificare supravegheate ”. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(3), pp. 289-300.
  18. ↑ Smith, M.R.; Martinez, T.; Giraud-Carrier, C. (2014). „ O analiză la nivel de instanță a complexității datelor ”. Machine Learning, 95(2): 225-256.
  19. ↑ Sáez, José A. (2013). „Predicția eficacității filtrării zgomotului cu măsuri de complexitate a datelor pentru clasificarea celui mai apropiat vecin.” recunoașterea modelelor . 46 : 355-364. DOI : 10.1016/j.patcog.2012.07.009 .
  20. ↑ Jorg Grunenberg (2011). „Complexitatea recunoașterii moleculare”. Fiz. Chim. Chim. Fiz . 13 (21): 10136-10146. Cod biblic : 2011PCCP ...1310136G . DOI : 10.1039/c1cp20097f . PMID  21503359 .

Literatură

Link -uri