mff2024mff2024mff2024mff2024mff2024mff2024

Aktuální číslo:

2024/3

Téma měsíce:

Elektromobilita

Obálka čísla

Nová alchymie

 |  5. 10. 1995
 |  Vesmír 74, 543, 1995/10

Ale je to tím těžší po Rimbaudovi

Najít novou alchymii!

Jiří Kolář, Nový Epiktet

Je to ledva pár desetiletí, co se člověku omrzelo ručně počítat. Vynalezl si stroje, aby za něj řešily rozmanité potřebné i nepotřebné úlohy. Ať jsme rádi či neradi, srostly již s námi tyto podivné stroje, splynuly s naší kulturou a asi se jich už nikdy nezbavíme, těchto vlezlých služebníků.

Dnes jsou počítače nesrovnatelně menší, rychlejší a po mnoha stránkách inteligentnější než v době svého vzniku. Zahledíme-li se však zkoumavým okem do jejich nitra, zjistíme, že co do základního principu jsou víceméně totožné se svými pradědečky. Jde vlastně o dvě vzájemně se doplňující myšlenky. První je založena na prostém faktu, že lze vyrobit prvky, které mohou mít dva a jen dva stavy a které lze spojovat tak, že stavy jedněch se vhodně kombinují se stavy druhých a že cokoliv z toho lze někam uložit pro pozdější použití.

Druhou myšlenkou je pojem algoritmu. Jakýkoliv typ služby, pokud ji lze vůbec od počítače žádat (znásobit čísla, vložit slovo do textu, najít cestu v síti, dokázat teorém), je třeba formulovat v podobě přesného návodu – posloupnosti instrukcí – jak v které situaci postupovat. Tento návod čili program je zpravidla obecný, to jest lze jej použít pro různá počáteční data (různá čísla, slova, sítě, teorémy). Jsou-li tato data větší a složitější, nevadí, bude to jen déle trvat. Jak déle, to lze někdy předem odhadnout a říká se tomu (časová) výpočtová složitost algoritmu (potažmo úlohy, máme-li na mysli pro ni nejefektivnější myslitelný algoritmus). Nehodnotí se délka výpočtu samotná, nýbrž to, jak rychle tato délka narůstá s velikostí vstupních dat. Proto je zcela nepodstatné, z jakých součástek je počítač vyroben.

O výpočtové složitosti jsme si mohli přečíst (při troše čtenářské píle celkem srozumitelně) v červnovém čísle Vesmíru1) a i v tomto čísle se k ní vracíme v článku Melánie a Petra Babincových (Vesmír 74, 545, 1995/10). Tentokrát se navíc dovíme o nejnovějším hitu, nové Adlemanově metodě řešení úloh2), která zcela obchází popsaný princip dnešních počítačů.

Vzpomínáte-li si, ve zmíněném červnovém čísle se mluví o úlohách (“typu NP″) s tou vlastností, že pokud by řešení takové úlohy spadlo z nebe, poměrně snadno by se ověřila jeho správnost, pokud však nic z nebe nepadá, není znám jiný algoritmus, než trpělivě zkoumat jeden po druhém všechny možné kandidáty na řešení (jejichž počet roste závratně rychle s velikostí úlohy).

Právě s tím si Adlemanova metoda dovede výborně poradit. Vyrobí se jednoduše roztok, v němž jsou možní kandidáti na řešení obsaženi všichni najednou (zakódováni do posloupností bází molekul DNA). V tomto roztoku se pak rozličnými důmyslnými chemickými reakcemi rozmnožují nadějní kandidáti a jinými důmyslnými reakcemi se odstraňují chybní kandidáti. Po několika takovýchto úkonech (jejichž počet jen lineárně závisí na velikosti úlohy) spolehlivě dostaneme všechna správná řešení a není problém si je pak přečíst. Adleman to předvedl i prakticky – po týdenní práci v laboratoři nalezl Hamiltonovu cestu v grafu o sedmi vrcholech.

Jeho metoda využívá replikačních vlastností molekul nukleových kyselin a obratně aranžuje situace, v nichž se tyto dlouhé molekuly předepsaným způsobem spojují, dělí, množí a filtrují. Nemá to co dělat s principem tradičních počítačů, ba ani to nelze přirovnat ke konekcionistickému principu paralelních neuronových sítí. To je již samo o sobě pozoruhodné, daleko důležitější však je, že základní nositelé relevantní informace – velké molekuly – jsou tak malé, že v jediné zkumavce lze realizovat triliony trilionů operací najednou. O takovém paralelizmu se konstruktérům počítačů nikdy nesnilo.

Dá se to nazvat výpočtem? Snad ano, ale pak i filtrování kávy je paralelním výpočtem, a to celkem úsporným, protože rozměry filtru jen málo závisí na počtu zrnek namleté kávy.

Teď však něco pro skeptiky. Za ty triliony trilionů je třeba něčím zaplatit. Celkem jednoduchý výpočet ukáže, že kdybychom stejnou úlohu, jakou předvedl Adleman, chtěli jeho metodou řešit pro graf, který místo 7 má 200 vrcholů, museli bychom začít s roztokem o hmotnosti 3.1025 kg, což je víc než váží Země3).

Koho neodrazují takováto přízemní omezení, toho bude jistě zajímat, že Adlemanova metoda je univerzální (vyrovná se Turingovým strojům). Takže principiálně nic nepřekáží tomu, aby chemik ve svých kádinkách a křivulích napodobil i nejmoudřejší počítač, a tedy – jak by měli usoudit důslední funkcionalisté – i mozek mudrců.

Literatura

1) P. Pudlák: Staré a nové problémy v matematice, Vesmír 74, 305, 1995/6. Viz též úvodník, Vesmír 74, 303, 1995/6.
2) L. M. Adleman, Science 266, 1021, 1994
3) J. Hartmanis, On the Computing Paradigm and Computational Complexity. In: Mathematical Formulations of Computer Science 1995, Springer, Berlin 1995, p. 82–92
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

Jak to bylo, jak to je?

Jak to bylo, jak to je? uzamčeno

Ondřej Vrtiška  |  4. 3. 2024
Jak se z chaotické směsi organických molekul na mladé Zemi zrodil první život? A jak by mohla vypadat jeho obdoba jinde ve vesmíru? Proč vše živé...
Otazníky kolem elektromobilů

Otazníky kolem elektromobilů uzamčeno

Jan Macek, Josef Morkus  |  4. 3. 2024
Elektromobil má některé podstatné výhody. Ale samotné vozidlo je jen jednou ze součástí komplexního systému mobility s environmentálními dopady a...
Návrat lidí na Měsíc se odkládá

Návrat lidí na Měsíc se odkládá uzamčeno

Dušan Majer  |  4. 3. 2024
Tragédie lodi Apollo 1 nebo raketoplánů Challenger a Columbia se již nesmí opakovat. Právě v zájmu vyšší bezpečnosti se odkládají plánované cesty...