Aktuální číslo:

2021/9

Téma měsíce:

Vzdělávání

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, CSc., Ph.D., (11. 10. 1938 – 25. 4. 2021) po vyloučení z internátní Koleje krále Jiřího pro „buržoazní původ“ dokončil základní školu v Praze a poté se vyučil jemným mechanikem. Později však večerně vystudoval střední školu a večerně také automatizaci a počítače na Elektrotechnické fakultě ČVUT (1961–1966). V letech 1969 až 1971 postgraduálně studoval na Kalifornské univerzitě v Berkeley, kde získal doktorát v matematické informatice. Po návratu se v Ústavu teorie informace a automatizace ČSAV zabýval teorií automatů. Z politických důvodů musel ústav v roce 1979 opustit a až do roku 1989 se živil jako programátor v družstvu invalidů META. Nespokojil se však s prací pro obživu. Organizoval bytové semináře, věnoval se samizdatové literatuře. Po sametové revoluci od listopadu 1989 do června 1990 působil v Koordinačním centru Občanského fóra. V polovině roku 1990 se stal spoluzakladatelem a prvním ředitelem transdisciplinárního pracoviště Centra pro teoretická studia UK a AV ČR. Nadále se zabýval kybernetikou, umělou inteligencí a kognitivní vědou, v souvislosti s transdisciplinaritou jej zajímala komplexita, emergentní jevy, vznik vědomí. V roce 1992 se habilitoval v oboru umělá inteligence. Do roku 2018 přednášel na MFF UK. Od srpna 1990 do konce roku 2019 byl šéfredaktorem časopisu Vesmír. Stejně jako v CTS i zde svou zvídavostí i šíří zájmů propojoval vědce, filosofy, umělce. Editoriály, které psal do Vesmíru, daly vznik knihám Otevřené oči a zvednuté obočí, Zvednuté oči a zjitřená myslZjitřená mysl a kouzelný svět. (Soupis významnějších publikací)
Havel Ivan M.

Doporučujeme

Záhada zhasínající hvězdy vyřešena

Záhada zhasínající hvězdy vyřešena

Záhada velkého pohasnutí Betelgeuze (Vesmír 100, 106, 2021/2) se zdá být více méně rozřešena. Důležitým klíčem byla pozorování povrchu hvězdy...
Převrácená výuka a nová role učitele

Převrácená výuka a nová role učitele

Zdeněk Hurák  |  6. 9. 2021
Co je a co určitě není převrácená výuka? Jaké jsou její cíle? Pokusím se vyvrátit několik oblíbených mýtů a nabídnu vlastní učitelské zkušenosti...
O myších (v podzemí) a lidech

O myších (v podzemí) a lidech uzamčeno

Radim Šumbera  |  6. 9. 2021
Čtenář dobrodružné literatury ví, že pro člověka a jeho žaludek byla důležitá velká zvířata, zejména savci. Vzpomeňme na lovce mamutů, indiány a...

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é