Složitost

Složitost  je charakteristika, která odráží míru obtížnosti pochopení, vytvoření a ověření systému nebo prvku systému [1] ; stupeň obtížnosti porozumění a řešení problémů , úkolů . Složitost systému nebo systémového prvku lze vyjádřit jako složitost odpovídajících problémů a úkolů jejich pochopení, vytváření a ověřování.

Podle Encyclopedia Britannica je vědecká teorie složitosti zaměřena na studium takových behaviorálních jevů některých systémů , které nelze vysvětlit analýzou prvků těchto systémů. „Složitost“ se běžně používá k charakterizaci emergentního chování systémů [2] . Složitost chování systému přitom může výrazně, polynomiálně s vysokou mírou i více, převyšovat součet složitostí chování prvků obsažených v systému [3] .

Od roku 2010 se k charakterizaci konceptu složitosti používá několik přístupů [4] . Neil Johnson tvrdí, že „ani mezi vědci neexistuje jediná definice složitosti – a tento vědecký koncept byl tradičně vysvětlován na konkrétních příkladech“. Johnson nakonec akceptuje definici „vědy o složitosti“ jako vědu, která „studuje jevy, které vznikají jako výsledek interakce souboru objektů“ [5] .

Neuspořádaná a uspořádaná složitost

V roce 1948 Warren Weaver rozlišoval mezi dvěma formami složitosti: neuspořádanou složitostí a uspořádanou složitostí [6] . Jevy neuspořádané složitosti jsou řešeny pomocí teorie pravděpodobnosti a statistické mechaniky , zatímco uspořádaná složitost se zabývá jevy, které vyžadují zohlednění značného počtu faktorů současně, vzájemně propojených do koherentního celku. Weaverova práce z roku 1948 ovlivnila následný výzkum složitosti [7] .

Jedním z problémů při řešení otázky složitosti je formalizovat intuitivní rozlišení mezi systémy s velkým počtem náhodných interakcí a systémy, ve kterých je počet interakcí sice velký, ale samotné interakce se vyskytují v rámci určitých omezení a jsou spojeny s určitým počtem interakcí. korelace mezi prvky. Weaver tento problém vyřešil rozlišením mezi neuspořádanou a uspořádanou složitostí.

Podle Weavera neuspořádaná složitost vzniká ze skutečnosti, že určitý systém má velmi velký počet částí. Přestože na interakce částí v situaci neuspořádané složitosti lze pohlížet jako na do značné míry náhodné, vlastnosti systému jako celku lze pochopit pomocí pravděpodobnostních a statistických metod.

Ukázkovým příkladem neuspořádané složitosti jsou molekuly plynu v nádobě. Někteří navrhnou, že systém neuspořádané složitosti může být přirovnán k (relativní) jednoduchosti planetárních drah - druhá může být předpovídána aplikováním Newtonových zákonů pohybu . Samozřejmě, že většina skutečných systémů, včetně planetárních drah, se nakonec stane teoreticky nepředvídatelnou i za použití newtonovské dynamiky, jak objevila moderní teorie chaosu .

Uspořádaná složitost je z pohledu Weavera nenáhodná nebo korelovaná interakce mezi částmi. Tyto korelované interakce vytvářejí koordinovanou strukturu, která jako systém může interagovat s jinými systémy. Koordinovaný systém vykazuje vlastnosti, které nejsou charakteristické pro jeho části. Dá se říci, že uspořádaný aspekt tohoto systému „vzniká“ bez jakékoli „vodící ruky“.

Počet dílů nemusí být příliš velký, aby konkrétní systém měl emergentní vlastnosti. Systém uspořádané složitosti lze porozumět jeho vlastnostem (chování) prostřednictvím modelování a simulace , zejména počítačové simulace . Příkladem uspořádané složitosti je městský blok jako živý mechanismus, jehož obyvatelé jsou součástí systému [8] .

Zdroje a faktory

Obvykle existují principy, které lze použít k vysvětlení původu složitosti v daném systému.

Zdrojem neuspořádané složitosti je velký počet částí v systému a chybějící korelace mezi jeho prvky.

V případě samoorganizujících se živých systémů užitečná uspořádaná složitost vyplývá ze skutečnosti, že mutované organismy jsou vybírány pro přežití svým prostředím kvůli jejich rozdílné reprodukční schopnosti nebo alespoň výhodám oproti méně uspořádaným komplexním organismům [9] .

Složitost objektu nebo systému je relativní vlastností. Například pro mnoho funkcí (úloh) je výpočetní složitost, jako je výpočetní čas, menší, když se používají vícepáskové Turingovy stroje , než když se používají jednopáskové Turingovy stroje. Stroje s náhodným přístupem do paměti mohou dále snížit časovou složitost (Greenlaw a Hoover 1998: 226), zatímco Turingovy indukční stroje mohou dokonce snížit třídu složitosti funkce, jazyka nebo množiny (Burgin 2005). To ukazuje, že nástroje činností mohou být důležitým faktorem složitosti.

Konkretizace konceptu složitosti v různých oblastech vědy

V různých oblastech vědy se používají specializované užší definice složitosti:

Jiné oblasti vědy zavádějí méně přesně definované pojmy složitosti:

Prozkoumávání

Složitost byla vždy součástí našeho prostředí, a proto se komplexními systémy a jevy zabývá mnoho vědních oborů. Na jedné straně je  vzhledem k výsledkům zjištěným v průběhu výzkumu nejzajímavější něco, co je poněkud obtížné – zobrazení variace bez náhodnosti .

Pojem "komplexní" je často zaměňován s pojmem "matoucí". V teorii systémů je rozdíl mezi složitým a komplexním rozdílem mezi nesčetnými spojovacími „tahy“ a efektivními „integrovanými“ řešeními, tj. „komplexní“ je v protikladu k „nezávislému“ a „provázané“ je protikladem k „jednoduchému“.

Ačkoli v některých oblastech vědy byly navrženy konkrétní definice složitosti, nedávno došlo k hnutí přeskupit pozorování z různých oblastí ke studiu složitosti jako jediného fenoménu, ať už jde o mraveniště , lidské mozky , akciové trhy nebo sociální systémy [16]. ] . Jednou takovou interdisciplinární skupinou oborů je teorie relačního řádu .

Témata výzkumu

Chování

Často se říká, že chování komplexního systému souvisí se vznikem a sebeorganizací . Teorie chaosu zkoumala citlivost systémů na změny počátečních podmínek jako jednu z příčin komplexního chování.

Mechanismy

Nedávný vývoj v umělém životě , evoluční práci na počítači a genetických algoritmech vedl k rostoucímu zájmu o složitost a komplexní adaptivní systémy .

Simulace

Ve společenských vědách  , studium vzniku makrovlastností z mikrovlastností, v sociologii také známé jako makromikrovize. Toto téma je běžně označováno jako sociální složitost , což je často spojováno s používáním počítačových simulací ve společenských vědách, jako je výpočetní sociologie .

Systémy

Systémová teorie se dlouho zabývá studiem komplexních systémů (nověji se jako název oboru používá také teorie složitosti a komplexní systémy ). Tyto systémy se používají ve výzkumu napříč různými obory, včetně biologie , ekonomie , společenských věd a technologie . V poslední době se komplexita stala přirozeným předmětem zájmu reálných sociokognitivních systémů a nového výzkumu v systemice . Složité systémy mívají mnoho rozměrů , jsou nelineární a obtížně se modelují. Za určitých okolností mohou vykazovat nízkorozměrné chování.

Údaje

V teorii informace se algoritmická teorie informace zabývá složitostí řádků dat.

Složité řetězce se hůře komprimují. I když nám intuice říká, že to může záviset na kodeku použitém ke kompresi řetězce (kodek by teoreticky mohl být vytvořen v jakémkoli libovolném jazyce, včetně jazyka, ve kterém by velmi malý příkaz „X“ mohl způsobit, že počítač vydá velmi složitý řetězec, jako je např. "18995316"), kterékoli dva Turingovy kompletní jazyky mohou být implementovány do sebe, což znamená, že délka dvou kódování v různých jazycích se nebude lišit o více než délku "překladového jazyka", což skončí je zanedbatelný pro dostatečně dlouhé řetězce dat.

Tato měření složitosti algoritmu obvykle přiřazují vysoké hodnoty náhodnému šumu . Avšak ti, kteří studují složité systémy, nevnímají náhodnost jako složitost.

Informační entropie se také někdy používá v teorii informace jako míra složitosti, ale entropie je také vysoká, když nejde o složitost, ale o náhodnost. V teorii informace není náhodnost považována za druh složitosti a její definice složitosti je užitečná v mnoha aplikacích.

Nedávná práce v oblasti strojového učení prozkoumala složitost dat, protože ovlivňuje výkon kontrolovaných klasifikačních algoritmů. Ho a Basu představují soubor měřítek složitosti pro problémy binární klasifikace [17] .

Opatření komplexnosti obecně zahrnují:

Instanční analýza tvrdosti je nový přístup, který je primárně zaměřen na identifikaci případů, které mohly být chybně klasifikovány (nebo jinými slovy na identifikaci případů, které mohou být nejobtížnější) .  Charakteristiky případů, které mohly být chybně klasifikovány, jsou pak měřeny na základě „skórů obtížnosti“. "Měření obtížnosti" je založeno na několika metodách učení pod dohledem, jako je měření počtu nekompatibilních sousedů nebo pravděpodobnost správného přiřazení označení třídy daným vstupním charakteristikám. Informace poskytované měřením obtížnosti se zkoumají pro použití v meta -learningu k určení, pro které je filtrování datových sad (nebo odstranění podezřelých hlučných případů z trénovací sady) nejslibnější [19] a lze je rozšířit na další oblasti. .

V molekulárním rozpoznávání

Nedávná studie založená na molekulárním modelování a korespondenčních konstantách popisuje molekulární rozpoznávání jako organizační fenomén [20] . Dokonce i pro malé molekuly, jako jsou sacharidy , nelze proces rozpoznávání předvídat nebo zkonstruovat, včetně předpokladu, že síla každé jednotlivé vodíkové vazby je přesně známa.

Aplikace

Teorie výpočetní složitosti se zabývá studiem složitosti řešení problémů. Na výpočetní složitost lze přistupovat z různých úhlů pohledu. Tuto složitost problému lze měřit množstvím času, paměti nebo jiných zdrojů potřebných k jeho vyřešení. Čas a prostor jsou dva z nejdůležitějších a běžně používaných parametrů při analýze problémů složitosti.

Problémy jsou klasifikovány do tříd obtížnosti na základě času, který algoritmus – obvykle počítačový program – potřebuje k vyřešení na základě velikosti problému. Některé problémy se řeší obtížně, jiné snadno. Existují tedy problémy, jejichž řešení v souladu s algoritmem nelze dokončit v čase kratším než exponenciálně závislý na velikosti problému. Příkladem takového problému je problém cestujícího obchodníka , který se řeší v čase (kde n  je velikost navštívené sítě – počet měst, která musí obchodník navštívit právě jednou). S rostoucí velikostí sítě se exponenciálně prodlužuje (více než) čas potřebný k nalezení trasy.

Problém je sice teoreticky řešitelný pomocí výpočtů, nicméně z důvodu příliš velkých časových či prostorových nároků se jeho řešení stává prakticky nemožným. Takové problémy se nazývají prakticky neřešitelné .

Existuje další forma složitosti zvaná hierarchická . Tato forma složitosti odráží hierarchický aspekt systémů, úkolů a problémů a je ortogonální k dříve diskutovaným formám složitosti, které lze v souladu s tím nazvat horizontálními formami složitosti.

Viz také

Poznámky

  1. ↑ ISO/IEC/IEEE 24765:2017 Systémové a softwarové inženýrství – slovník
  2. ↑ Složitost (vědecká teorie  ) . — článek z Encyclopædia Britannica Online . Datum přístupu: 14. ledna 2021.
  3. ↑ Johnson, Steven. Vznik: Propojené životy mravenců, mozků, měst . - New York : Scribner, 2001. - S. 19. - ISBN 978-3411040742 .
  4. ↑ JM Zayed, N. Nouvel, U. Rauwald, OA Scherman. Chemická složitost — supramolekulární samouspořádání syntetických a biologických stavebních bloků ve vodě . Chemical Society Reviews, 2010, 39, 2806-2816 http://pubs.rsc.org/en/Content/ArticleLanding/2010/CS/b922348g
  5. ↑ 1 2 Johnson, Neil F. Kapitola 1: Společnost dvojky, trojka je složitost // Jednoduše složitost: Jasný průvodce teorií složitosti. - Oneworld Publications, 2009. - S. 3. - ISBN 978-1780740492 .
  6. ↑ Weaver, Warren (1948). "Věda a složitost" (PDF) . Americký vědec . 36 (4): 536-44. PMID  18882675 . Získáno 2007-11-21 .
  7. ↑ Johnson, Steven. Vznik: propojené životy mravenců, mozků, měst a softwaru . — New York : Scribner, 2001. — S.  46 . - ISBN 978-0-684-86875-2 .
  8. ↑ Jacobs, Jane. Smrt a život velkých amerických měst . — New York: Random House, 1961.
  9. ↑ Ulanowicz, Robert, "Ecology, the Ascendent Perspective", Kolumbie, 1997
  10. ↑ Burgin, M. (1982) Zobecněná Kolmogorovova složitost a dualita v teorii výpočtů, Notices of the Russian Academy of Sciences, v.25, No. 3, str. 19-23
  11. ↑ Crutchfield, JP (1989). „Odvozování statistické složitosti“. Fyzické kontrolní dopisy . 63 (2): 105-108. Bibcode : 1989PhRvL..63..105C . DOI : 10.1103/PhysRevLett.63.105 . PMID  10040781 .
  12. ↑ Crutchfield, JP (1999). „Termodynamická hloubka kauzálních stavů: Objektivní složitost prostřednictvím minimálních reprezentací“. Fyzický přehled E. 59 (1): 275-283. Bibcode : 1999PhRvE..59..275C . DOI : 10.1103/PhysRevE.59.275 .
  13. ↑ Grassberger, P. (1986). „Směrem ke kvantitativní teorii samogenerované složitosti“. International Journal of Theoretical Physics . 25 (9): 907-938. Bibcode : 1986IJTP...25..907G . doi : 10.1007/ bf00668821 .
  14. ↑ Prokopenko, M. (2009). „Informačně teoretický základ o složitosti, sebeorganizaci a vzniku“. složitost . 15 (1): 11-28. Bibcode : 2009Cmplx..15a..11P . DOI : 10.1002/cplx.20249 .
  15. ↑ Příklad z teorie komplexních sítí: " Komplexní struktury a mezinárodní organizace " ( Grandjean, Martin (2017). "Analisi e visualizzazioni delle reti in storia. L'esempio della cooperazione intellettuale della Società delle Nazioni". Memoria e Ricerca ( 2): 371-393 DOI : 10.14647/87204 .Viz také: Francouzská verze ).
  16. ↑ Bastardas-Boada, Albert. „Komplexika jako meta-transdisciplinární obor“ . Komplex Congres Mondial Pour la Pensee. Les Défis d'Un Monde Globalisé. (Paříž, 8.–9. prosince). unesco .
  17. ↑ Ho, T.K.; Basu, M. (2002). " Míra složitosti kontrolovaných klasifikačních problémů ". IEEE Transactions on Pattern Analysis and Machine Intelligence 24(3), str. 289-300.
  18. ↑ Smith, M. R.; Martinez, T.; Giraud-Carrier, C. (2014). " Analýza složitosti dat na úrovni instance ". Strojové učení, 95(2): 225-256.
  19. ↑ Sáez, José A. (2013). "Předpovídání účinnosti filtrování šumu pomocí měření složitosti dat pro klasifikaci nejbližších sousedů." rozpoznávání vzorů . 46 : 355-364. DOI : 10.1016/j.patcog.2012.07.009 .
  20. ↑ Jorg Grunenberg (2011). „Složitost v molekulárním rozpoznávání“. Phys. Chem. Chem. Phys . 13 (21): 10136-10146. Bibcode : 2011PCCP...1310136G . DOI : 10.1039/c1cp20097f . PMID  21503359 .

Literatura

Odkazy