Vesmírná školaVesmírná školaVesmírná školaVesmírná školaVesmírná školaVesmírná škola

Aktuální číslo:

2024/12

Téma měsíce:

Expedice

Obálka čísla

1, 2, 3, 4, 5, 6, 7, ...

 |  5. 6. 1995
 |  Vesmír 74, 303, 1995/6

Slýcháme, že přirozená čísla jsou od Boha - či aspoň od přírody, jak svědčí jejich název -, vše ostatní si lidé nebo matematici vymysleli. Je-li tomu tak, naskýtá se otázka, jakým způsobem čísla v přírodě vůbec existují a jak se my o nich dovídáme.

Nějaké číslo vstupuje do bytí především jako počet něčeho. Na první pohled banální tvrzení, skrývá však háček: co si máme myslet o těch číslech, která shodou okolností nejsou ničeho počtem? Jsou to například hodně velká čísla - těch je dokonce většina! A vůbec, kdo rozhodne, které to entity světa mají povahu počítatelnosti? Když takto začneme uvažovat, brzy se dostaneme k otázce, kolik nám to čísel Bůh vlastně nadělil.

Několik málo nejmenších čísel lze přímo "vidět": stačí se přece podívat, abychom poznali, zda hřib, čáp, kůň, střevlík či pavouk má vždy správný počet nohou. Není nutno počítat. Horizont takovéto viditelnosti je někde mezi osmi a počtem nohou stonožky (který není sto ale 34, u některých druhů až 346, mám-li věřit knihám).

Za tímto horizontem už nezbývá než zdlouhavě počítat, či odpočítávat, jako ovčák ovce, jednu po druhé. Narazíme však brzy na další problém. Běžně máme za to, že počet nějakých reálných věcí, ať je jich sebevíc - počet ovcí v houfu, molekul v roztoku, hvězd v galaxii - je exaktní, objektivní, nezávislý na počítajícím. Představa, že k takto chápanému počtu se lze dobrat počítáním, by však vyžadovala něco závažnějšího než trpělivost: museli bychom počítajícího vysvobodit z našeho reálného času a prostoru. V něm totiž počítání předpokládá určitou prostorovou činnost, přenášení informace z místa na místo, nebo přeskupování počítané množiny - a nic nám přitom nezaručí, že se přitom počítaná množina nějak nepozorovaně nezmění.

Asi je to tak, že od Boha (či od přírody) máme jen malá čísla. Ta velká (rozuměj: větší, než lze v přírodě potkat) si matematici museli domyslet. Dobře udělali, protože se ukázalo, že teoretizovat lze daleko snáze o množině všech čísel vůbec než o některé její části. Hlavním trikem jsou aritmetické operace: sčítání a násobení. Aritmetika umožňuje mluvit o všech číslech najednou v jazyku malých čísel (stačí dokonce jednička) a definovat celou nekonečnou množinu čísel na malém kousku papíru. Stačí vyjít z několika základních zákonů (axiomů a odvozovacích pravidel), vše ostatní lze odvodit. Pozor! Opravdu vše?

Nekonečno, jehož přijetí umožňuje přemítat o množině všech přirozených čísel vcelku a tak o nich mluvit nezávisle na tom, zda jsou velká či malá, se nám vzepřelo dát do rukou vše. Od roku 1931 víme, že ať definujeme přirozená čísla sebelépe, vždy nám některé jejich vlastnosti zůstanou utajeny. Slavná Gödelova věta totiž praví, že žádný (konečný) systém zákonů nemůže být tak silný, aby byl schopen dokázat všechny pravdy o číslech, aniž by přitom nedokázal též nějaké nepravdy.

Existuje intimní souvislost mezi množinami čísel, výroky o číslech a algoritmy, které s čísly operují. Tak například výrok "číslo x je prvočíslo" říká, že číslo x je prvkem množiny prvočísel. K množině prvočísel pak existuje algoritmus (počítačový program), který rozpoznává prvočísla. Vložíme-li na vstup tohoto algoritmu číslo x, odpoví "ano" v případě, že náš výrok byl pravdivý.

Nelze se proto divit, že existuje stejně intimní souvislost mezi teorií čísel a teorií algoritmů. Zatímco teorie čísel je tu s námi již dlouho, je teorie algoritmů záležitostí tohoto století. Její rozvoj v posledních desetiletích je - jak by se dalo čekat - důsledkem existence počítačů. Jak už to bývá, praktické potřeby silně ovlivňují směr teoretického bádání (to je prostě fakt, nikoliv apel) a protože rychlost výpočtu (pro různá vstupní data) je z praktického hlediska snad nejdůležitější vlastností algoritmů, je teorie výpočtové složitosti jednou z nejživějších disciplín informatiky.

V tomto čísle je teorii složitosti věnován článek Pavla Pudláka (Vesmír 74, 305, 1995/6). Teorie výpočtové složitosti nahrazuje otázku principiální existence algoritmu (či důkazu nějakého tvrzení) otázkou existence zvládnutelného algoritmu pro danou úlohu - rozumí se takového, jehož nároky na výpočetní čas nerostou příliš strmě v závislosti na velikosti vstupních dat. Existuje zajímavá třída úloh (mnohé z nich jsou dokonce "ze života"), zvaná "NP", pro něž všechny známé algoritmy hledají řešení jen obtížně (zdlouhavě), přičemž však pokud nějaké řešení spadne z nebe, snadno se pozná, zda je správné. Nezbývá tedy než trpělivě probírat všechny případy, jeden po druhém.

Kdekdo se snaží zjistit, zda s tím lze něco dělat. Kdyby se totiž našel zvládnutelný algoritmus aspoň pro jednu úlohu z jisté dobře popsané podtřídy úloh typu NP, pak by už všechny úlohy typu NP měly zvládnutelný algoritmus.

Situace mi trošičku připomíná rozdíl mezi malými, "viditelnými" čísly a čísly, k nimž se lze jen dopočítávat, jak o tom byla řeč na začátku. Je možné, že ony zvládnutelné algoritmy, založené zpravidla na nějakém vhledu do podstaty úlohy, se vyskytují jen velmi vzácně mezi primitivními a zdlouhavými algoritmy, které neumějí než se probírat všemi možnostmi.

OBORY A KLÍČOVÁ SLOVA: Různé
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

Do srdce temnoty

Do srdce temnoty uzamčeno

Ladislav Varadzin, Petr Pokorný  |  2. 12. 2024
Archeologické expedice do severní Afriky tradičně směřovaly k bývalým či stávajícím řekám a jezerům, což téměř dokonale odvádělo pozornost od...
Vzhůru na tropický ostrov

Vzhůru na tropický ostrov

Vojtěch Novotný  |  2. 12. 2024
Výpravy na Novou Guineu mohou mít velmi rozličnou podobu. Někdo zakládá osadu nahých milovníků slunce, jiný slibuje nový ráj na Zemi, objevuje...
Je na obzoru fit pilulka?

Je na obzoru fit pilulka? uzamčeno

Stanislav Rádl  |  2. 12. 2024
U řady onemocnění se nám kromě příslušné medikace od lékaře dostane také doporučení zvýšit svoji fyzickou aktivitu. Lze ji nahradit „zázračnou...