Siemens2024Siemens2024Siemens2024Siemens2024Siemens2024Siemens2024

Aktuální číslo:

2024/10

Téma měsíce:

Konzervace

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

O konzervování, zelené dohodě i konzervatismu

O konzervování, zelené dohodě i konzervatismu

Michal Anděl  |  30. 9. 2024
Vesmír přináší v tomto čísle minisérii článků, které se zabývají různými aspekty konzervování. Toto slovo má různé významy, které spojuje...
Životní příběh Nicolase Apperta

Životní příběh Nicolase Apperta uzamčeno

Aleš Rajchl  |  30. 9. 2024
Snaha prodloužit trvanlivost potravin a uchovat je pro období nedostatku je nepochybně stará jako lidstvo samo. Naši předci jistě brzy...
Izotopy odhalují původ krovu z Notre-Dame

Izotopy odhalují původ krovu z Notre-Dame uzamčeno

Anna Imbert Štulc  |  30. 9. 2024
Požár chrámu Matky Boží v Paříži (Cathédrale Notre‑Dame de Paris) v roce 2019 způsobil ikonické památce velké škody. V troskách po ničivé pohromě...