Számítástudományi és Információelméleti Tanszék

 

Témakiírás

DNS alapú kiszámítás

A biológiai indíttatású számítástudomány távlati célja az, hogy egy DNS alapú, molekuláris műveleteket használó majdani számítógép működésének elméleti alapjait lerakja. A DNS alapú kiszámítás 1994-ben került a figyelem középpontjába, amikor Adleman DNS-szálak kémcsőben való manipulálásával Hamilton-kört tudott találni egy gráfban. Noha az eljárás sokáig tartott és maga a gráf kisméretű volt, az a tény, hogy DNS szálakkal végzett egyszerű műveletekkel számítást lehet végezni, népszerűvé tette ezt a tudományterületet. A módszer fő vonzerejét az adja, hogy óriási mennyiségű információt lehet tárolni DNS szálak segítségével és az algoritmusok során egyszerre számtalan utat tudunk végignézni párhuzamosan, így remény van rá, hogy hagyományos számítógépekkel nehezen kezelhető prblémákra megoldást találjunk. Adleman kísérlete után sok kérdés merült fel, ezek egyike, hogy lehet-e a DNS szálak műveleteire alapozva olyan formális modellt készíteni, mely a Turing géppel azonos számítási erejű. Több ilyen, molekuláris technikákat használó, univerzális erejű elméleti modell is született. A formális nyelvi modellek keresése és vizsgálata mellett sok más, a molekuláris kiszámításban alapvetőnek tekintett kérdés merül még fel. Ilyenek például a következők:

Irodalom:

1. Martyn Amos: Theoretical and Experimental DNA Computation, Springer, 2005.

2. A szerző weboldalán a fenti könyvről: http://www.dcs.ex.ac.uk/~mramos/DNACOMP/

3.G.Paun, G.Rozenberg, A.Salomaa: DNA Computing: new computing paradigms. Springer Verlag 1998.

Szükséges nyelvtudás: angol

Dr. Csima Judit
egyetemi adjunktus
29-87
csima@cs.bme.hu