Co všechno dokáží DNA počítače: Výběr automobilu, cesta grafem, šifrování,úložné médium i hry

Protože DNA funguje v živých organismech jako systém pro ukládání a zpracování informace, její využití i pro dalš...


Protože DNA funguje v živých organismech jako systém pro ukládání a zpracování
informace, její využití i pro další typy výpočtů je vlastně nasnadě. Možnosti
DNA počítačů byly v polovině 90. let poprvé demonstrovány při řešení úlohy
obchodního cestujícího (travelling salesman problem). Tvůrcem algoritmu byl
profesor na Jihokalifornské univerzitě Leonard Adleman, mj. spoluautor známé
šifry RSA (Rivest-Shamir-Adleman). V tomto případě se při hledání nejkratší
cesty využilo masivního paralelismu molekulárních počítačů (viz také
obrázek).Na CeBITu v roce 2002 pak bylo vědci z Frauhoferova ústavu
demonstrováno i poloautomatické zařízení pro tento typ výpočtu.
Kromě úlohy obchodního cestujícího se na DNA počítačích podařilo realizovat
také algoritmus řešící problém splnitelnosti (satisfiability problem). V tomto
případě jde řešení úlohy vyžadující splnění celé řady omezujících podmínek
("chci si koupit zelenou Škodovku, pokud její cena nepřesáhne částku X, půjde
dodat do termínu Y a na skladě současně nebude modrý automobil značky Z").
Seriózní využití najdou tyto techniky při návrhu řady výrobních procesů,
jejichž výsledkem má být výrobek splňující určité podmínky.
DNA počítač se však naproti tomu ani teoreticky nepodařilo uzpůsobit k další
významné a výpočetně náročné úloze, faktorizaci.Zde není zatím známo, jak
využít masivního paralelismu samozřejmě není myslitelné použít molekulu DNA
obsahující počet nukleotidů v řádu např. 1030,což odpovídá běžné délce klíče
používané dnes v šifrovacích algoritmech. Možné blýskání na lepší časy pro DNA
počítače lámající šifry by mohly znamenat pokusy provedené opět Leonardem
Adlemanem, které byly zaměřené proti kryptografii typu DES
Historii těchto experimentů jsme v uplynulých 4 letech poměrně podrobně
mapovali také v Computerworldu; články obsahující popis jednotlivých algoritmů
lze snadno dohledat např. v našem archivu na webu nebo na ww.scienceworld.cz.
Byly realizovány také experimenty, ve kterých DNA sloužila jako molekulární
paměť (1 gram suché DNA pojme tolik informace jako tuny CD-ROMů).
Poslední využití, které na stránkách CW zmiňujeme poprvé, je poměrně kuriózní.
Před rokem naprogramovala skupina nadšenců (především Milan Stojanovic z
newyorské Columbia Univesity a Darko Stefanovic z University of New Mexico) na
DNA počítači algoritmus hry tic-tac-toe. Jedná se o obdobu piškvorek na ploše 3
x 3;střetnutí skončí při správné hře obou soupeřů samozřejmě remízou.
Piškvorkový DNA počítač byl pojmenován Maya. Systém fungoval tak, že lidský
hráč vložil svoji "herní" DNA na hrací desku. Hráč měl k dispozici 9 kousků
DNA, které odpovídaly určitému políčku, a tu kladl na všechna pole to aby o
svém tahu"uvědomil" všechna políčka počítače. Jedno políčko mělo přitom
velikost zhruba 1cm2 Počítač zareagoval sérií biochemických reakcí (respektive
logických operací realizovaných prostřednictvím enzymů), které nakonec vedly k
zezelenání na políčku odpovídajícím odpovědi
Jednalo se sice o hračku, nicméně současně šlo o první interaktivní DNA
počítač,jehož běh nebyl určen dopředu, ale který průběžně reagoval na vstupy
uživatele.A počítač skutečně fungoval alespoň v tom smyslu, že jej lidský hráč
v žádné ze100 pokusných partií nedokázal porazit.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.