Kompleksitet - Complexity

For bruk i informatikk, se Computational complexity . For annen bruk, se Kompleksitet (disambiguation) .

Kompleksitet kjennetegner oppførselen til et system eller en modell hvis komponenter interagerer på flere måter og følger lokale regler, noe som betyr at det ikke er noen rimelig høyere instruksjon for å definere de forskjellige mulige interaksjonene.

Begrepet brukes vanligvis for å karakterisere noe med mange deler der disse delene samhandler med hverandre på flere måter, og som kulminerte med en høyere fremvekstrekkefølge større enn summen av delene. Studiet av disse komplekse koblingene i forskjellige skalaer er hovedmålet med komplekse systemteorier .

Vitenskap fra 2010 tar en rekke tilnærminger til å karakterisere kompleksitet; Zayed et al. gjenspeiler mange av disse. Neil Johnson uttaler at "selv blant forskere er det ingen unik definisjon av kompleksitet - og den vitenskapelige forestillingen har tradisjonelt blitt formidlet ved hjelp av bestemte eksempler ..." Til syvende og sist vedtar Johnson definisjonen av "kompleksitetsvitenskap" som "studiet av fenomenene som komme ut av en samling interagerende objekter ".

Oversikt

Definisjoner av kompleksitet er ofte avhengig av begrepet et " system " - et sett med deler eller elementer som har relasjoner mellom dem differensiert fra forhold til andre elementer utenfor relasjonsregimet. Mange definisjoner har en tendens til å postulere eller anta at kompleksitet uttrykker en tilstand av mange elementer i et system og mange former for relasjoner mellom elementene. Det man ser som komplekst og det man ser som enkelt, er imidlertid relativt og endres med tiden.

Warren Weaver stilte i 1948 to former for kompleksitet: uorganisert kompleksitet og organisert kompleksitet. Fenomener med 'uorganisert kompleksitet' behandles ved hjelp av sannsynlighetsteori og statistisk mekanikk, mens 'organisert kompleksitet' omhandler fenomener som slipper unna slike tilnærminger og konfronterer "å håndtere samtidig et betydelig antall faktorer som henger sammen i en organisk helhet". Weavers papir fra 1948 har påvirket påfølgende tankegang om kompleksitet.

Tilnærmingene som legemliggjør begreper om systemer, flere elementer, flere relasjonsregimer og statlige rom kan oppsummeres som at det antyder at kompleksitet oppstår fra antall skillbare relasjonsregimer (og tilhørende tilstandsrom) i et definert system.

Noen definisjoner relaterer seg til det algoritmiske grunnlaget for uttrykk for et komplekst fenomen eller modell eller matematisk uttrykk, som senere beskrevet her.

Uorganisert vs. organisert

Et av problemene for å løse kompleksitetsproblemer har vært å formalisere det intuitive konseptuelle skillet mellom det store antallet avvik i relasjoner som eksisterer i tilfeldige samlinger, og det til tider store, men mindre, antall forhold mellom elementer i systemer der begrensninger (relatert til korrelasjon av ellers uavhengige elementer) reduserer samtidig variasjonene fra elementuavhengighet og skaper regimer med mer ensartede eller korrelerte relasjoner eller interaksjoner.

Weaver oppfattet og tok opp dette problemet, i det minste på en foreløpig måte, ved å trekke et skille mellom "uorganisert kompleksitet" og "organisert kompleksitet".

Etter Weavers syn skyldes uorganisert kompleksitet at det spesielle systemet har et veldig stort antall deler, si millioner av deler, eller mange flere. Selv om interaksjonene mellom delene i en "uorganisert kompleksitet" -situasjon kan sees på som stort sett tilfeldige, kan egenskapene til systemet som helhet forstås ved bruk av sannsynlighet og statistiske metoder.

Et godt eksempel på uorganisert kompleksitet er en gass i en beholder, med gassmolekylene som delene. Noen vil antyde at et system med uorganisert kompleksitet kan sammenlignes med den (relative) enkelheten til planetbaner - sistnevnte kan forutsies ved å anvende Newtons bevegelseslover . Selvfølgelig blir de fleste virkelige systemer, inkludert planetbaner, etter hvert teoretisk uforutsigbare selv ved bruk av newtonsk dynamikk; som oppdaget av moderne kaosteori .

Organisert kompleksitet, etter Weavers syn, ligger ikke i noe annet enn den ikke-tilfeldige eller korrelerte interaksjonen mellom delene. Disse korrelerte forholdene skaper en differensiert struktur som som system kan samhandle med andre systemer. Det koordinerte systemet manifesterer egenskaper som ikke bæres eller dikteres av individuelle deler. Det organiserte aspektet ved denne formen for kompleksitet overfor andre systemer enn fagsystemet kan sies å "dukke opp", uten noen "styrende hånd".

Antall deler trenger ikke å være veldig stort for at et bestemt system skal ha nye egenskaper. Et system med organisert kompleksitet kan forstås i dets egenskaper (oppførsel blant eiendommene) gjennom modellering og simulering , spesielt modellering og simulering med datamaskiner . Et eksempel på organisert kompleksitet er et bynabolag som en levende mekanisme, med nabolagsfolket blant systemets deler.

Kilder og faktorer

Det er generelt regler som kan påberopes for å forklare opprinnelsen til kompleksiteten i et gitt system.

Kilden til uorganisert kompleksitet er det store antallet deler i systemet av interesse, og mangelen på sammenheng mellom elementer i systemet.

Når det gjelder selvorganiserende levende systemer, kommer en nyttig organisert kompleksitet fra at velgjørende muterte organismer blir valgt til å overleve av omgivelsene på grunn av deres differensielle reproduksjonsevne eller i det minste suksess over livløse stoffer eller mindre organiserte komplekse organismer. Se f.eks. Robert Ulanowicz 'behandling av økosystemer.

Kompleksiteten til et objekt eller system er en relativ egenskap. For eksempel, i mange funksjoner (problemer), for eksempel en beregningskompleksitet som tidspunktet for beregningen er mindre når multitape turingmaskin blir brukt enn når Turing maskiner med ett bånd blir benyttet. Random Access Machines tillater en enda mer redusert tidskompleksitet (Greenlaw og Hoover 1998: 226), mens induktive Turing -maskiner kan redusere kompleksitetsklassen til en funksjon, språk eller sett (Burgin 2005). Dette viser at aktivitetsverktøy kan være en viktig kompleksitetsfaktor.

Varierte betydninger

På flere vitenskapelige felt har "kompleksitet" en presis betydning:

  • I Kompleksitetsteori , de mengder ressurser som kreves for gjennomføring av algoritmer er studert. De mest populære beregningskompleksitetene er tidskompleksiteten til et problem lik antall trinn det tar å løse en forekomst av problemet som en funksjon av størrelsen på inngangen (vanligvis målt i biter), ved å bruke den mest effektive algoritmen, og romkompleksiteten til et problem som er lik volumet i minnet som brukes av algoritmen (f.eks. cellene på båndet) som det tar for å løse en forekomst av problemet som en funksjon av størrelsen på inngangen (vanligvis målt i biter), ved hjelp av den mest effektive algoritmen. Dette tillater klassifisering av beregningsproblemer etter kompleksitetsklasse (som P , NP , etc.). En aksiomatisk tilnærming til beregningskompleksitet ble utviklet av Manuel Blum . Det gjør det mulig å utlede mange egenskaper ved konkrete beregningsmessige kompleksitetstiltak, for eksempel tidskompleksitet eller romkompleksitet, fra egenskaper til aksiomatisk definerte mål.
  • I algoritmisk informasjonsteori , den Kolmogorov kompleksitet (også kalt beskrivende kompleksitet , algoritmiske kompleksitet, eller algoritmisk entropi ) av en streng er lengden av den korteste binære program som utganger strengen. Minste meldingslengde er en praktisk anvendelse av denne tilnærmingen. Ulike typer Kolmogorov-kompleksitet studeres: uniform kompleksitet, prefiks-kompleksitet, monoton kompleksitet, tidsavgrenset Kolmogorov-kompleksitet og rombegrenset Kolmogorov-kompleksitet. En aksiomatisk tilnærming til Kolmogorov -kompleksitet basert på Blum -aksiomer (Blum 1967) ble introdusert av Mark Burgin i avisen som ble presentert for publisering av Andrey Kolmogorov . Den aksiomatiske tilnærmingen omfatter andre tilnærminger til Kolmogorov -kompleksiteten. Det er mulig å behandle forskjellige typer Kolmogorov -kompleksitet som spesielle tilfeller av aksiomatisk definert generalisert Kolmogorov -kompleksitet. I stedet for å bevise lignende setninger, for eksempel den grunnleggende invarians -setningen, for hvert bestemt mål, er det mulig å enkelt utlede alle slike resultater fra ett tilsvarende teorem som er påvist i aksiomatisk setting. Dette er en generell fordel med den aksiomatiske tilnærmingen i matematikk. Den aksiomatiske tilnærmingen til Kolmogorov -kompleksiteten ble videreutviklet i boken (Burgin 2005) og anvendt på programvaremålinger (Burgin og Debnath, 2003; Debnath og Burgin, 2003).
  • I informasjonsteori er informasjonsfluktuasjonskompleksitet fluktuasjonen av informasjon om informasjonsentropi . Det er avledet fra svingninger i overvekt av orden og kaos i et dynamisk system og har blitt brukt som et mål på kompleksitet på mange forskjellige felt.
  • I informasjonsbehandling er kompleksitet et mål på det totale antallet eiendommer som overføres av et objekt og oppdages av en observatør . En slik samling av eiendommer blir ofte referert til som en stat .
  • I fysiske systemer , er kompleksitet et mål for sannsynligheten av den tilstandsvektor til systemet. Dette skal ikke forveksles med entropi ; det er et distinkt matematisk mål, et der to forskjellige stater aldri blir sammenblandet og betraktet som like, slik det gjøres for begrepet entropi i statistisk mekanikk .
  • I dynamiske systemer måler statistisk kompleksitet størrelsen på minimumsprogrammet som statistisk kan reprodusere mønstrene (konfigurasjonene) i datasettet (sekvensen). Mens den algoritmiske kompleksiteten innebærer en deterministisk beskrivelse av et objekt (den måler informasjonsinnholdet i en individuell sekvens) , innebærer den statistiske kompleksiteten, i likhet med å forutsi kompleksitet , en statistisk beskrivelse og refererer til et ensemble av sekvenser generert av en bestemt kilde. Formelt sett rekonstruerer den statistiske kompleksiteten en minimal modell som omfatter samling av alle historier som deler en lignende sannsynlig fremtid, og måler entropien om sannsynlighetsfordelingen til statene i denne modellen. Det er et beregningsbart og observatøruavhengig mål som bare er basert på systemets interne dynamikk, og har blitt brukt i studier av fremvekst og selvorganisering .
  • I matematikk er Krohn - Rhodos kompleksitet et viktig tema i studiet av endelige semigrupper og automater .
  • I nettverksteorien er kompleksitet et produkt av rikdom i forbindelsene mellom komponenter i et system, og definert av en svært ulik fordeling av visse tiltak (noen elementer er sterkt tilkoblede og noen svært få, se komplekse nettverk ).
  • I programvareteknikk er programmeringskompleksitet et mål på samspillet mellom de forskjellige elementene i programvaren. Dette skiller seg fra beregningskompleksiteten beskrevet ovenfor ved at det er et mål på utformingen av programvaren.
  • I abstrakt forstand - Abstrakt kompleksitet, er basert på visuelle strukturer oppfatning Det er kompleksiteten til binær streng definert som et kvadrat med funksjoner tall dividert med antall elementer (0 og 1). Funksjoner omfatter her alle særegne arrangementer av 0 og 1. Selv om funksjonsnummeret alltid må tilnærmes, er definisjonen presis og oppfyller intuitivt kriterium.

Andre felt introduserer mindre presist definerte forestillinger om kompleksitet:

  • Et komplekst adaptivt system har noen eller alle av følgende attributter:
    • Antall deler (og typer deler) i systemet og antall relasjoner mellom delene er ikke-trivielt-det er imidlertid ingen generell regel for å skille "trivielt" fra "ikke-trivielt";
    • Systemet har minne eller inkluderer tilbakemelding ;
    • Systemet kan tilpasse seg i henhold til sin historie eller tilbakemelding;
    • Forholdet mellom systemet og dets miljø er ikke-trivielt eller ikke-lineært;
    • Systemet kan påvirkes av, eller kan tilpasse seg, omgivelsene;
    • Systemet er svært følsomt for innledende forhold.

Studere

Kompleksitet har alltid vært en del av miljøet vårt, og derfor har mange vitenskapelige felt behandlet komplekse systemer og fenomener. Fra ett perspektiv er det som på en eller annen måte er komplekst - å vise variasjon uten å være tilfeldig - mest verdig interesse gitt belønningene som finnes i undersøkelsens dyp.

Bruken av begrepet kompleks forveksles ofte med begrepet komplisert. I dagens systemer er dette forskjellen mellom utallige tilkoblende "komfyrrør" og effektive "integrerte" løsninger. Dette betyr at kompleks er det motsatte av uavhengig, mens komplisert er det motsatte av enkelt.

Selv om dette har ført til at noen felt har kommet med spesifikke definisjoner av kompleksitet, er det en nyere bevegelse for å omgruppere observasjoner fra forskjellige felt for å studere kompleksitet i seg selv, enten det vises i maurtuer , menneskelige hjerner eller aksjemarkeder , sosiale systemer. En slik tverrfaglig gruppe felt er relasjonelle ordensteorier .

Emner

Oppførsel

Atferden til et komplekst system sies ofte å skyldes fremvekst og selvorganisering . Kaosteorien har undersøkt systemers følsomhet for variasjoner i innledende forhold som en årsak til kompleks oppførsel.

Mekanismer

Nyere utvikling i kunstig liv , evolusjonær beregning og genetiske algoritmer har ført til en økende vekt på kompleksitet og komplekse adaptive systemer .

Simuleringer

I samfunnsvitenskap studerte studien om fremveksten av makroegenskaper fra mikroegenskapene, også kjent som makro-mikrosyn i sosiologi . Temaet er ofte anerkjent som sosial kompleksitet som ofte er relatert til bruk av datasimulering i samfunnsvitenskap, dvs.: beregningssosiologi .

Systemer

Hovedartikkel: Kompleks system

Systemteori har lenge vært opptatt av studiet av komplekse systemer (i nyere tid har kompleksitetsteori og komplekse systemer også blitt brukt som navn på feltet). Disse systemene er til stede i forskningen innen en rekke disipliner, inkludert biologi , økonomi , samfunnsfag og teknologi . Nylig har kompleksitet blitt et naturlig domene for sosiokognitive systemer i virkeligheten og fremvoksende systemforskning . Komplekse systemer har en tendens til å være høydimensjonale , ikke-lineære og vanskelige å modellere. Under spesifikke omstendigheter kan de oppvise lavdimensjonal oppførsel.

Data

I informasjonsteori er algoritmisk informasjonsteori opptatt av kompleksiteten i datastrenger.

Komplekse strenger er vanskeligere å komprimere. Selv om intuisjon forteller oss at dette kan avhenge av kodeken som brukes til å komprimere en streng (en kodek kan teoretisk opprettes på et vilkårlig språk, inkludert et der den svært lille kommandoen "X" kan føre til at datamaskinen sender ut en veldig komplisert streng som "18995316")), kan alle to Turing-komplette språk implementeres i hverandre, noe som betyr at lengden på to kodinger på forskjellige språk maksimalt vil variere med lengden på "oversettelsesspråket"-noe som vil ende opp med å være ubetydelig for tilstrekkelig store datastrenger.

Disse algoritmiske målingene av kompleksitet har en tendens til å tildele høye verdier til tilfeldig støy . Imidlertid vil de som studerer komplekse systemer ikke betrakte tilfeldighet som kompleksitet.

Informasjonsentropi brukes også noen ganger i informasjonsteorien som indikasjon på kompleksitet, men entropi er også høy for tilfeldighet. Informasjonsfluktuasjonskompleksitet , fluktuasjoner av informasjon om entropi, anser ikke tilfeldighet som kompleks og har vært nyttig i mange applikasjoner.

Nyere arbeid med maskinlæring har undersøkt kompleksiteten til dataene, da det påvirker ytelsen til klassifiseringsalgoritmer under tilsyn . Ho og Basu presenterer et sett med kompleksitetstiltak for binære klassifiseringsproblemer .

Kompleksitetstiltakene dekker stort sett:

  • overlappene i funksjonsverdier fra forskjellige klasser.
  • klassens separasjon.
  • mål på geometri, topologi og tetthet av manifolder . Forekomsthardhet er en annen tilnærming som søker å karakterisere datakompleksiteten med målet om å bestemme hvor vanskelig et datasett er å klassifisere riktig og er ikke begrenset til binære problemer.

Forekomsthardhet er en bottom-up-tilnærming som først søker å identifisere forekomster som sannsynligvis vil bli feilklassifisert (eller, med andre ord, hvilke tilfeller som er de mest komplekse). Egenskapene til tilfellene som sannsynligvis vil bli feilklassifisert måles deretter basert på produksjonen fra et sett med hardhetsmål. Hardhetstiltakene er basert på flere overvåket læringsteknikker som måling av antall uenige naboer eller sannsynligheten for den tildelte klassemerket gitt inputfunksjonene. Informasjonen fra kompleksitetstiltakene er undersøkt for bruk i metalæring for å avgjøre for hvilke datasett filtrering (eller fjerning av mistenkte støyende forekomster fra treningssettet) er den mest fordelaktige og kan utvides til andre områder.

I molekylær anerkjennelse

En nylig studie basert på molekylære simuleringer og samsvarskonstanter beskriver molekylær anerkjennelse som et fenomen av organisering. Selv for små molekyler som karbohydrater , kan gjenkjennelsesprosessen ikke forutsies eller utformes, selv om vi antar at hver enkelt hydrogenbindings styrke er nøyaktig kjent.

Loven om nødvendig kompleksitet

Boisot og McKelvey drev fra loven om nødvendig variasjon og formulerte 'Law of Requisite Complexity', som mener at for å være effektivt tilpasningsdyktig må den interne kompleksiteten til et system matche den eksterne kompleksiteten det konfronterer. Søknaden i prosjektledelse av lov om nødvendig kompleksitet er analysen av positiv, passende og positiv kompleksitet .

I prosjektledelse

Prosjektkompleksitet er egenskapen til et prosjekt som gjør det vanskelig å forstå, forutse og holde kontroll over den generelle oppførselen, selv når den får rimelig fullstendig informasjon om projektsystemet.

applikasjoner

Computational complexity theory er studiet av kompleksiteten til problemer - det vil si vanskeligheten med å løse dem. Problemer kan klassifiseres etter kompleksitetsklasse i henhold til tiden det tar for en algoritme - vanligvis et dataprogram - å løse dem som en funksjon av problemstørrelsen. Noen problemer er vanskelige å løse, mens andre er enkle. Noen vanskelige problemer trenger for eksempel algoritmer som tar eksponentiell tid i forhold til størrelsen på problemet å løse. Ta for eksempel den reisende selgerproblemet . Det kan løses i tide (hvor n er størrelsen på nettverket du skal besøke - antall byer den reisende selgeren må besøke nøyaktig en gang). Etter hvert som størrelsen på nettverket av byer vokser, vokser tiden som trengs for å finne ruten (mer enn) eksponentielt.

Selv om et problem i prinsippet kan løses beregningsmessig, er det i praksis ikke så enkelt. Disse problemene kan kreve store mengder tid eller overdreven plass. Beregningskompleksitet kan tilnærmes fra mange forskjellige aspekter. Beregningskompleksitet kan undersøkes på grunnlag av tid, minne eller andre ressurser som brukes til å løse problemet. Tid og rom er to av de viktigste og mest populære betraktningene når kompleksitetsproblemer analyseres.

Det finnes en viss klasse problemer at selv om de i prinsippet er løselige krever de så mye tid eller plass at det ikke er praktisk å prøve å løse dem. Disse problemene kalles uoverkommelige .

Det er en annen form for kompleksitet som kalles hierarkisk kompleksitet . Den er ortogonal til de former for kompleksitet som er diskutert så langt, som kalles horisontal kompleksitet.

Se også

Referanser

Videre lesning

Eksterne linker