Aktuální číslo:

2017/12

Téma měsíce:

Kontakty

Složité a obtížné

 |  1. 1. 2003
 |  Vesmír 82, 3, 2003/1

Nebyli bychom lidi, kdybychom se tu a tam neocitli ve složité situaci, kterou jen obtížně zvládáme. Příjemné to není, nejraději bychom všechno měli jednoduché a snadné. Jen co jsem to napsal, už nesouhlasím. Kdyby všechno bylo jednoduché a všechno snadné, kde bychom byli? Nudný by to byl svět, opravdu.

Je zajisté mnoho sfér lidské činnosti, v nichž rozlišování mezi složitým a jednoduchým hraje klíčovou roli. Například ve vědeckém bádání a technickém budování. To, co je složité, je nesrozumitelné, nepopsatelné, nepředvídatelné a neovladatelné, je to spíše poruchové, zranitelné, křehké, drahé a jinak choulostivé. Přesto je složitost, či spíše jistá její podoba – někdy zvaná „komplexita“ – též principem tvořivým: nikoliv kvantita (jak nás zjednodušeně učili), ale komplexita se mění v kvalitu. Aspoň překročí-li jakousi mez, pak to ale stojí za to. Příkladem jsou organizmy, zejména poté, co se kdysi dávno začaly starat samy o sebe a odolávat nástrahám světa.

V posledních desetiletích se pěstují dva pozoruhodné vědní obory, které si za své téma i název vybraly právě složitost. Jedním je věda o složitosti (Science of Complexity), druhým teorie výpočtové složitosti (Complexity Theory).

Věda o složitosti je vzorně transdisciplinární (s těžištěm u teorie systémů a matematické fyziky). Do širší známosti pronikla mimo jiné po založení známého vědeckého ústavu v Santa Fe začátkem 80. let. 1) Sám pojem složitosti, vztažený zde hlavně k dynamickým systémům, si vysloužil řadu rozmanitých definic; jedna namátkou z českého webu: „systém označíme za složitý, pokud se skládá z řady navzájem interagujících komponent a objevuje se u něj nové chování, které není samozřejmým důsledkem chování jednotlivých komponent.“ Složitost je v tomto smyslu spíše vlastností než veličinou a jako vlastnost je protikladem nejen jednoduchosti, ale i plané neuspořádanosti. 2)

Druhý obor, teorie výpočtové (popřípadě algoritmické) složitosti, je součástí matematické informatiky. V tomto čísle (v příspěvku Pavla Pudláka na s. 10) je popsán jeden konkrétní úspěch této teorie: byl nalezen polynomiální (což znamená „snadný“, jak uvidíme) algoritmus, jenž pro jakékoliv číslo, které si vymyslíte, pozná, zda je to prvočíslo.

To, o co tu jde, není složitost věcí, nýbrž problémů a algoritmů a pro odlišení ji budu nazývat obtížnost, nikoliv složitost. Nejprve co rozumíme úlohou, algoritmem, výpočtem. Příklad obecné úlohy:

Pro libovolné přirozené číslo x urči, zda je dělitelné třemi.

Ze školy si pro ni dokonce pamatuji chytrý algoritmus:

Sčítej cifry čísla x, a to opakovaně, dokud nezískáš jednociferné číslo;

je-li toto číslo dělitelné třemi, odpověz ANO, jinak NE.

Tento algoritmus je ovšem také obecný, teprve při zadání vstupu (hodnoty parametru x) jej lze použít k řízení konkrétního výpočtu (což je formálně posloupnost elementárních početních kroků). Pokud výpočet skončí (což se v našem případě vždy stane), dostaneme výsledek (řešení úlohy, zde odpověď ANO, nebo NE). Čtenář nechť si to zkusí třeba pro x = 72321. 3)

Nic obtížného – v tomto případě. V jiných případech je to horší. Teorie výpočtové složitosti proto potřebuje obecnou definici obtížnosti (výpočtu, algoritmu, úlohy). Začněme u výpočtu: ten může být zdlouhavý (když je třeba provést velký počet elementárních kroků), nebo paměťově náročný (užívá velký počet míst v pracovní paměťi).

Definovat obtížnost algoritmu je náročnější, musíme počítat s tím, že při různých vstupech jednomu algoritmu odpovídá nekonečně mnoho různých výpočtů o rozličném stupni obtížnosti. Postup je tento: zvolíme nějakou vhodnou míru velikosti vstupu (u čísla například délku čili počet cifer) a sledujeme, jak pro daný algoritmus obtížnost výpočtu závisí na velikosti vstupu. Nepřekvapí nás asi, že čím větší vstup, tím obtížnější výpočet, více nás bude ovšem zajímat, zda lze tento růst obtížnosti omezit shora nějakou rozumnou funkcí. Touto funkcí může být například polynom. Všebecně (a odůvodněně) se předpokládá, že polynomiální nárůst (na rozdíl například od exponenciálního) přirozeně vymezuje kategorii „snadných“ (zvládnutelných) algoritmů. 4) To lze zobecnit: úloha je snadná, existuje-li pro ni aspoň jeden polynomiální (tedy „snadný“ algoritmus). 5)

Teorie složitosti sama o sobě by mohla nabídnout materiál i pro „vědu o vědě“. Lze zde například sledovat jemný rozdíl mezi motivací teoretika a praktika: prvého zajímají obecná tvrzení, konkrétní příklady hledá, jen aby si třeba ověřil, že něco existuje. Důkaz, že úloha je obtížná, má pro něj stejnou hodnotu jako důkaz, že je snadná, a je-li snadná, nevadí mu, když se snadnost uplatní až pro astronomicky velké vstupy. Praktik se naopak zajímá o konkrétní algoritmy na řešení úloh „ze života“ a těší ho, když najde algoritmus snadný i pro malé vstupy.

Objevy teoretika jsou principiální, objevy praktika užitečné. Zpravidla však nelze a ani nemá smysl rozlišovat, zda převládá motivace prvého či druhého. To platí, myslím, i o zmíněném případu rozpoznávání prvočísel.

Poznámky

2) O složitosti lze mluvit i u statických struktur (např. u geometrických tvarů).
3) Řešení: ANO.
4) Třída polynomů má pro teoretika smysl jako celek, protože základní operace nad polynomy (součet, součin, mocnina) plodí opět polynomy.
5) Může existovat mnoho různých algoritmů pro stejnou úlohu (nebo také žádný – případ algoritmicky neřešitelných úloh).

Ke stažení

RUBRIKA: Úvodník

O autorovi

Ivan M. Havel

Doc. Ing. Ivan M. Havel, Ph.D., (*1938) absolvoval FEL ČVUT v Praze. V letech 1969–1971 studoval Ph.D. (počítačové vědy) na University of California v Berkeley. Několik let pracoval jako výzkumný pracovník v Ústavu teorie informace a automatizace ČSAV. V současné době je docentem na Univerzitě Karlově v Praze a působí v Centru pro teoretická studia (společném pracovišti UK v Praze a AV ČR), jehož byl v letech 1990 – 2008 ředitelem. Přednáší na MFF UK.
Havel Ivan M.

Doporučujeme

Tajemná „Boží země“ Punt

Tajemná „Boží země“ Punt uzamčeno

Břetislav Vachala  |  4. 12. 2017
Mnoho vzácného zboží starověkého Egypta pocházelo z tajemného Puntu, kam Egypťané pořádali časté obchodní výpravy. Odkud jejich expedice...
Hmyz jako dokonalý létací stroj

Hmyz jako dokonalý létací stroj

Rudolf Dvořák  |  4. 12. 2017
Hmyz patří k nejdokonalejším a nejstarším letcům naší planety. Jeho letové schopnosti se vyvíjely přes 300 milionů let a předčí dovednosti všech...
Hranice svobody

Hranice svobody uzamčeno

Stefan Segi  |  4. 12. 2017
Podle listiny základních práv a svobod, která je integrovaná i v Ústavě ČR, jsou „svoboda projevu a právo na informace zaručeny“ a „cenzura je...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné