13. fejezet - Összefoglalás - a párhuzamosság és a Watson-Crick komplementaritás szerepe

Tartalom

13.1. A párhuzamosság formái

A DNS számítógépek és számítási modelleket már a bevezetőben elhelyeztük a számítástudományban.

Általában a DNS számítások, és modelljeik, két fő jellemzője a következő: az egyik a Watson-Crick komplementaritás, a másik a masszív párhuzamosság. A Watson-Crick komplementaritás kihasználása szinte mindegyik modellben megtörtént. Ez az alapja a dominók, a ragadós végek lehetséges összeragasztásának. Ugyancsak ez adja az alapot a különféle H-rendszerek, a beszúró-törlő rendszerek formális műveleteihez. A WK-automaták esetén is ez az egyik fő különbség a hagyományos automatákhoz képest. A DNS origamiban és az élő sejtek számítási folyamatiban is elsőrangú fontosságú. A komplementaritás azt is megengedi, hogy (amint a természetben is történik), másolhassuk a DNS molekulákat. A DNS molekulák nano mérete, és így az oldatban levő hatalmas számuk adja a lehetőséget a masszív párhuzamosság kihasználására.

Az első kíséreltek is ezt a két alapvető tulajdonságot használták ki. A kísérleti módszerek gyakorlati alkalmazhatóságának határt szab, hogy ugyan a molekulák nagyon kicsik, így az elméleti modellek egy bizonyos méretig nagyon szépen fedik a gyakorlatot, azért egy adott határ felett a nehéz feladatoknál a kombinatorikai robbanás eléri ezeket az óriási számokat is. Pl. egy 100 változós SAT formulánál, már így sem kivitelezhető az összes lehetséges kiértékelés együttes kezelése (számoljuk ki hányféle molekulát is jelentene ez, és ha mindből csak egyet vennénk, - ami egyébként egyáltalán nem garantálná, hogy megtaláljuk azt az adott molekulát, vagy pont vele is elvégeznénk az adott műveletet ennyi molekula közt, - és minden bit értéket 1 nukleotid hosszan tárolnánk, mennyi is lenne csak a molekulák összsúlya, vajon mekkora oldatmennyiségben lehetne ezeket tárolni...).

A másik, a szerző szerint magasabb szintű, intelligensebb megközelítés a konstruktív modellek használata. Ilyenek pl. a DNS-ek önépítő modelljei. Itt az információ nem az egész levesben együtt van tárolva, hanem egy komplex molekulában (ami sokszor itt már nem az eredeti kétláncú molekulát takarja, hanem sok rövidebb egyláncú molekulából felépített pl. kétdimenziós alakzatot). A számításokkal kapcsolatos kutatások hangsúlya is ez irányba tolódott az utóbbi években. Illetve nagyon erősek, dinamikusak a biológiai, orvosi alkalmazások irányába történő fejlesztések.

13.1. A párhuzamosság formái

Bár általában a legtöbb esetben a párhuzamos számítások során a „vagy-párhuzamosság" és az „és-párhuzamosság" nem teljesen tiszta formában jelennek meg, mint szélső pólusokat ismertetjük.

A vagy-párhuzamosság, a nyers erő (brute-force), a „kínai hadsereg" útkereső algoritmusa, a „sok lúd disznót győz" modelljének felel meg. Az egyes DNS számítási modellek (elméletileg) elképesztő hatékonysága ezen a vagy-párhuzamosságon alapul, amikor a nagyon nagy számú megoldásjelöltet egyszerre teszteljük. Tipikusan ilyenek a szűrő és a dominó modellek. Ezen tekintetben ez a fajta párhuzamosság közel áll a nemdeterminisztikus próbálgatási módszerhez, amikor a vagy-szálak egyikét elég lenne számolni, a többire nem lesz szükség, de ha előre nem tudjuk, melyik szál lesz a jó, akkor mindet egyszerre próbálhatjuk, ha rendelkezünk megfelelő párhuzamos erőforrással (és erre nagyon alkalmasak a DNS molekulák, kicsik és sokan elférnek kis helyen). Ugyanez a párhuzamosság jellemzi az adatpárhuzamos számításokat is.

A vagy-párhuzamossággal szemben az és-párhuzamosság az „oszd meg és uralkodj” elv alapján részproblémákra bontja a problémát, és a részeket oldja meg párhuzamosan, így a részeredmények együttesen jelentik majd a probléma megoldását. Úgy kell ezt elképzelnünk, mint pl. a mesterséges intelligenciában használatos problémaredukciós problémamegoldási elvet, azzal a feltétellel, hogy a részproblémák egymástól függetlenül, párhuzamosan is megoldhatóak. Ez a fajta párhuzamosság jellemzi az ún. „high-performance computing”-ot is. A konstruktív modellekben inkább ez a párhuzamosság jellemzőbb, szemben a korábbi modellekkel, ahol a vagy-párhuzamosság szerepe a döntő.