Komplexitet

Komplexitet  är en egenskap som återspeglar svårighetsgraden för att förstå, skapa och verifiera ett system eller element i ett system [1] ; svårighetsgraden att förstå och lösa problem , uppgifter . Komplexiteten hos ett system eller systemelement kan uttryckas i termer av komplexiteten hos motsvarande problem och uppgifterna att förstå, skapa och verifiera dem.

Enligt Encyclopedia Britannica syftar den vetenskapliga teorin om komplexitet till att studera sådana beteendefenomen hos vissa system som inte kan förklaras genom att analysera elementen i dessa system. "Komplexitet" används vanligtvis för att karakterisera systemens framväxande beteende [2] . Samtidigt kan komplexiteten i systemets beteende avsevärt, polynomiellt med hög grad eller mer, överstiga summan av komplexiteten i beteendet hos de element som ingår i systemet [3] .

Från och med 2010 används flera tillvägagångssätt för att karakterisera begreppet komplexitet [4] . Neil Johnson hävdar att "även bland forskare finns det ingen enskild definition av komplexitet - och detta vetenskapliga koncept har traditionellt förklarats med specifika exempel." I slutändan accepterar Johnson definitionen av "vetenskapen om komplexitet" som en vetenskap som "studerar de fenomen som uppstår som ett resultat av interaktionen mellan en uppsättning objekt" [5] .

Oordnad och ordnad komplexitet

1948 skilde Warren Weaver mellan två former av komplexitet: oordnad komplexitet och ordnad komplexitet [6] . Fenomen av oordnad komplexitet hanteras med hjälp av sannolikhetsteori och statistisk mekanik , medan ordnad komplexitet handlar om fenomen som kräver övervägande av ett betydande antal faktorer samtidigt, relaterade till en sammanhängande helhet. Weavers arbete från 1948 påverkade efterföljande komplexitetsforskning [7] .

Ett av problemen med att ta itu med frågan om komplexitet är att formalisera den intuitiva distinktionen mellan system med ett stort antal slumpmässiga interaktioner och system där antalet interaktioner, även om det är stort, men själva interaktionerna sker inom vissa begränsningar och är förknippade med en korrelation mellan element. Weaver löste detta problem genom att skilja mellan oordnad och ordnad komplexitet.

Enligt Weaver uppstår oordnad komplexitet av att ett visst system har ett mycket stort antal delar. Även om växelverkan mellan delar i en situation med oordnad komplexitet kan ses som till stor del slumpmässiga, kan egenskaperna hos systemet som helhet förstås med hjälp av probabilistiska och statistiska metoder.

Ett utmärkt exempel på oordnad komplexitet är gasmolekyler i en behållare. Vissa föreslår att ett system av oordnad komplexitet kan jämföras med (relativa) enkelhet hos planetbanor - den senare kan förutsägas genom att tillämpa Newtons rörelselagar . Naturligtvis blir de flesta verkliga system, inklusive planetbanor, så småningom teoretiskt oförutsägbara även med hjälp av newtonsk dynamik, som upptäckts av modern kaosteori .

Ordnad komplexitet är enligt Weavers uppfattning den icke-slumpmässiga eller korrelerade interaktionen mellan delar. Dessa korrelerade interaktioner skapar en koordinerad struktur som, som ett system, kan interagera med andra system. Ett koordinerat system uppvisar egenskaper som inte är karakteristiska för dess delar. Man kan säga att den ordnade aspekten av detta system "framträder" utan någon "styrande hand".

Antalet delar behöver inte vara särskilt stort för att ett visst system ska ha framväxande egenskaper. Ett ordnat komplexitetssystem kan förstås genom dess egenskaper (beteende) genom modellering och simulering , i synnerhet datorsimulering . Ett exempel på ordnad komplexitet är ett stadskvarter som en levande mekanism, med dess invånare som delar av ett system [8] .

Källor och faktorer

Det finns vanligtvis principer som kan användas för att förklara uppkomsten av komplexitet i ett givet system.

Källan till oordnad komplexitet är det stora antalet delar i systemet och bristen på korrelation mellan dess element.

När det gäller självorganiserande levande system uppstår användbar ordnad komplexitet från det faktum att muterade organismer väljs ut för överlevnad av sin miljö på grund av deras olika reproduktionsförmåga, eller åtminstone fördelar jämfört med mindre ordnade komplexa organismer [9] .

Komplexiteten hos ett objekt eller system är en relativ egenskap. Till exempel, för många funktioner (uppgifter) är beräkningskomplexiteten, såsom beräkningstiden, mindre när Turing- maskiner med flera band används än när Turing-maskiner med enkelband används. Maskiner med slumpmässig minnesåtkomst kan ytterligare minska tidskomplexiteten (Greenlaw och Hoover 1998: 226), medan Turing-induktiva maskiner till och med kan minska komplexitetsklassen för en funktion, ett språk eller en uppsättning (Burgin 2005). Detta visar att aktivitetsverktyg kan vara en viktig faktor för komplexitet.

Konkretisering av begreppet komplexitet inom olika vetenskapsområden

Inom olika vetenskapsområden används specialiserade, snävare definitioner av komplexitet:

Andra vetenskapsområden introducerar mindre precist definierade begrepp om komplexitet:

Utforskar

Komplexitet har alltid varit en del av vår miljö och därför handlar många vetenskapsområden om komplexa system och fenomen. Å ena sidan är något som är lite svårt - att visa variation utan slumpmässighet  - av störst intresse, med tanke på de resultat som hittats under forskningens gång.

Termen "komplex" förväxlas ofta med termen "förvirrande". I systemteorin är skillnaden mellan intrikat och komplex skillnaden mellan otaliga sammankopplande "rörelser" och effektiva "integrerade" lösningar, dvs "komplex" är motsats till "oberoende", och "entangled" är motsats till "enkla".

Även om specifika definitioner av komplexitet har föreslagits inom vissa vetenskapsområden, har det nyligen skett en rörelse för att omgruppera observationer från olika områden för att studera komplexitet som ett enda fenomen, oavsett om det är myrstackar , mänskliga hjärnor , aktiemarknader eller sociala system [16] ] . En sådan tvärvetenskaplig grupp av fält är relationell ordningsteori .

Forskningsämnen

Beteende

Det sägs ofta att beteendet hos ett komplext system är relaterat till uppkomst och självorganisering . Kaosteorin utforskade systemens känslighet för förändringar i initiala förhållanden som en av orsakerna till komplext beteende.

Mekanismer

Den senaste tidens utveckling inom artificiellt liv , evolutionär datoranvändning och genetiska algoritmer har lett till ett ökande fokus på komplexitet och komplexa adaptiva system .

Simuleringar

Inom samhällsvetenskap  , studiet av uppkomsten av makroegenskaper från mikroegenskaper, även känd inom sociologi som makro-mikrovision. Detta ämne kallas vanligen för social komplexitet , vilket ofta förknippas med användningen av datorsimuleringar inom samhällsvetenskap, såsom beräkningssociologi .

System

Systemteori har länge sysslat med studier av komplexa system (på senare tid har komplexitetsteori och komplexa system också använts som namn på fältet). Dessa system används i forskning inom en mängd olika discipliner, inklusive biologi , ekonomi , samhällsvetenskap och teknologi . På senare tid har komplexitet blivit ett naturligt ämne av intresse för verkliga socio-kognitiva system och ny forskning inom systemik . Komplexa system tenderar att ha många dimensioner , är icke-linjära och är svåra att modellera. Under vissa omständigheter kan de uppvisa lågdimensionellt beteende.

Data

Inom informationsteori handlar algoritmisk informationsteori om komplexiteten hos rader av data.

Komplexa strängar är svårare att komprimera. Även om intuitionen säger oss att detta kan bero på den codec som används för att komprimera strängen (en codec kan teoretiskt göras på vilket godtyckligt språk som helst, inklusive ett där ett mycket litet "X"-kommando kan få datorn att mata ut en mycket komplex sträng som t.ex. "18995316" ), alla två Turing-kompletta språk kan implementeras i varandra, vilket innebär att längden på två kodningar på olika språk inte kommer att variera mer än längden på "översättningsspråket", vilket slutar upp vara försumbar för tillräckligt långa datasträngar.

Dessa algoritmiska komplexitetsmått tilldelar vanligtvis höga värden till slumpmässigt brus . Men de som studerar komplexa system ser inte slumpmässighet som komplexitet.

Informationsentropi används också ibland inom informationsteorin som ett mått på komplexitet, men entropin är också hög när det inte handlar om komplexitet utan om slumpmässighet. Inom informationsteori betraktas slumpmässighet inte som en sorts komplexitet, och dess definition av komplexitet är användbar i många tillämpningar.

Det senaste arbetet inom maskininlärning har utforskat datakomplexitet eftersom det påverkar prestandan hos övervakade klassificeringsalgoritmer. Ho och Basu presenterar en uppsättning komplexitetsmått för binära klassificeringsproblem [ 17] .

Komplexitetsmått omfattar i allmänhet:

Instanshårdhetsanalys är ett nytt tillvägagångssätt som främst syftar till att identifiera fall som kan ha blivit felklassificerade (eller, med andra ord, identifiera fall som kan vara svårast) .  Egenskaper för fall som kan ha blivit felklassificerade mäts sedan utifrån "svårighetspoäng". "Svårighetsmått" baseras på flera övervakade inlärningsmetoder, som att mäta antalet inkompatibla grannar eller sannolikheten för att korrekt tilldela en klassetikett givna indataegenskaper. Informationen från svårighetsmåtten undersöks för användning i meta -learning för att avgöra för vilka datauppsättningar filtrering (eller avlägsnande av misstänkta bullriga fall från träningsuppsättningen) som är mest lovande [19] och kan utökas till andra områden .

I molekylär igenkänning

En färsk studie baserad på molekylär modellering och korrespondenskonstanter beskriver molekylär igenkänning som ett organisationsfenomen [20] . Även för små molekyler som kolhydrater kan igenkänningsprocessen inte förutsägas eller konstrueras, inklusive att anta att styrkan hos varje enskild vätebindning är exakt känd.

Applikationer

Beräkningskomplexitetsteori behandlar studiet av komplexiteten i att lösa problem. Beräkningskomplexitet kan närma sig ur olika perspektiv. Denna komplexitet hos ett problem kan mätas genom mängden tid, minne eller andra resurser som krävs för att lösa det. Tid och rum är två av de viktigaste och mest använda parametrarna vid analys av komplexitetsproblem.

Problem klassificeras i en svårighetsklass baserat på den tid det tar för en algoritm – vanligtvis ett datorprogram – att lösa utifrån problemets storlek. Vissa problem är svåra att lösa, andra är lätta. Så det finns problem vars lösning, i enlighet med algoritmen, inte kan slutföras på kortare tid än exponentiellt beroende på problemets storlek. Ett exempel på ett sådant problem är resandeförsäljarproblemet , som löses i tid (där n  är storleken på nätverket som ska besökas - antalet städer som säljaren måste besöka exakt en gång). När nätverkets storlek växer ökar tiden det tar att hitta en rutt (mer än) exponentiellt.

Även om problemet i teorin kan lösas med hjälp av beräkningar, men på grund av alltför stora tids- eller utrymmesbehov blir lösningen praktiskt taget omöjlig. Sådana problem kallas praktiskt taget olösliga .

Det finns en annan form av komplexitet som kallas hierarkisk . Denna form av komplexitet speglar den hierarkiska aspekten av system, uppgifter och problem och är ortogonal mot de tidigare diskuterade formerna av komplexitet, som följaktligen kan kallas horisontella former av komplexitet.

Se även

Anteckningar

  1. ↑ ISO/IEC/IEEE 24765:2017 System- och mjukvaruteknik - Ordförråd
  2. ↑ Komplexitet (vetenskaplig teori  ) . — artikel från Encyclopædia Britannica Online . Tillträdesdatum: 14 januari 2021.
  3. ↑ Johnson, Steven. Emergence: Myrors, hjärnor, städers sammankopplade liv . - New York : Scribner, 2001. - P. 19. - ISBN 978-3411040742 .
  4. ↑ JM Zayed, N. Nouvel, U. Rauwald, OA Scherman. Kemisk komplexitet — supramolekylär självmontering av syntetiska och biologiska byggstenar i vatten . Chemical Society Reviews, 2010, 39, 2806-2816 http://pubs.rsc.org/en/Content/ArticleLanding/2010/CS/b922348g
  5. ↑ 1 2 Johnson, Neil F. Kapitel 1: Tvås företag, tre är komplexitet // Helt enkelt komplexitet: En tydlig guide till komplexitetsteori. - Oneworld Publications, 2009. - P. 3. - ISBN 978-1780740492 .
  6. ↑ Weaver, Warren (1948). "Vetenskap och komplexitet" (PDF) . Amerikansk vetenskapsman . 36 (4): 536-44. PMID  18882675 . Hämtad 2007-11-21 .
  7. ↑ Johnson, Steven. Emergence: myrors, hjärnor, städers och mjukvaras uppkopplade liv . — New York: Scribner, 2001. — S.  46 . - ISBN 978-0-684-86875-2 .
  8. ↑ Jacobs, Jane. De stora amerikanska städernas död och liv . — New York: Random House, 1961.
  9. ↑ Ulanowicz, Robert, "Ecology, the Ascendant Perspective", Columbia, 1997
  10. ↑ Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Notices of the Russian Academy of Sciences, v.25, No. 3, sid. 19-23
  11. ↑ Crutchfield, JP (1989). "Att sluta sig till statistisk komplexitet". Fysiska granskningsbrev . 63 (2): 105-108. Bibcode : 1989PhRvL..63..105C . DOI : 10.1103/PhysRevLett.63.105 . PMID  10040781 .
  12. ↑ Crutchfield, JP (1999). "Termodynamiskt djup av kausaltillstånd: Objektiv komplexitet via minimala representationer". Fysisk granskning E. 59 (1): 275-283. Bibcode : 1999PhRvE..59..275C . DOI : 10.1103/PhysRevE.59.275 .
  13. ↑ Grassberger, P. (1986). "Mot en kvantitativ teori om självgenererad komplexitet". International Journal of Theoretical Physics . 25 (9): 907-938. Bibcode : 1986IJTP...25..907G . doi : 10.1007/ bf00668821 .
  14. ↑ Prokopenko, M. (2009). "En informationsteoretisk grundbok om komplexitet, självorganisering och framväxt". komplexitet . 15 (1): 11-28. Bibcode : 2009Cmplx..15a..11P . DOI : 10.1002/cplx.20249 .
  15. ↑ Ett exempel från teorin om komplexa nätverk: " Komplexa strukturer och internationella organisationer " ( Grandjean, Martin (2017). "Analisi e visualizzazioni delle reti in story. L'esempio della cooperazione intellettuale della Società delle Nazioni". Memoria e Ricerca ( 2): 371-393 DOI : 10.14647/87204 .Se även: fransk version ).
  16. ↑ Bastardas-Boada, Albert. "Komplexik som ett meta-transdisciplinärt fält" . Congres Mondial Pour la Pensee Complexe. Les Défis d'Un Monde Globalisé. (Paris, 8-9 december). unesco .
  17. ↑ Ho, T.K.; Basu, M. (2002). " Komplexitetsmått för övervakade klassificeringsproblem ". IEEE Transactions on Pattern Analysis and Machine Intelligence 24(3), sid 289-300.
  18. ^ Smith, M.R.; Martinez, T.; Giraud-Carrier, C. (2014). " En instansnivåanalys av datakomplexitet ". Machine Learning, 95(2): 225-256.
  19. ↑ Sáez, José A. (2013). "Förutsäga brusfiltreringseffektivitet med datakomplexitetsåtgärder för klassificering av närmaste granne." mönsterigenkänning . 46 : 355-364. DOI : 10.1016/j.patcog.2012.07.009 .
  20. ↑ Jorg Grunenberg (2011). "Komplexitet i molekylärt igenkänning". Phys. Chem. Chem. Phys . 13 (21): 10136-10146. Bibcode : 2011PCCP...1310136G . DOI : 10.1039/c1cp20097f . PMID  21503359 .

Litteratur

Länkar