Aktuální číslo:

2017/12

Téma měsíce:

Kontakty

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, 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é