Bevezetés

Ez a tankönyv a Debreceni Egyetemen mester szakos kurzusként oktatott Új számítási paradigmák tárgy oktatásának és elsajátításának megkönnyítésére íródott. A 2005-ben készült hasonló tematikájú Új elvű számítógépek (Bevezetés az új számítási modellekbe és a nem-klasszikus „számítógépek” tudományába) jegyzet jelentősen átdolgozáson esett át, köszönhetően az időközben eltelt időnek is.

A könyv I. része a klasszikus, hagyományosnak tekintett számítási paradigmát tekinti át röviden, beleértve a Turing gépet, a Neumann elvet, a klasszikus propozicionális logikát, és az alapvető bonyolultsági fogalmakat is.

A könyv II. része az intervallum-értékű logikát, mint általános többértékű logikát mutatja be, amely segítségével az ismert többértékű logikák vizuálisan modellezhetőek. Az erre épülő intervallum-értékű számítási paradigmában az adott területen (a intervallumon) tárolt információ mennyisége nőhet a számítás során, ennek segítségével a PSPACE-teljes qSAT, a prímfaktorizáció, illetve a diszkrét logaritmus probléma hatékony (az adott paradigmában polinomiális lépésszámú) megoldását ismertetjük.

A könyv III. részében a DNS felépítése és vele végezhető műveletek bemutatása az első. Ezután Adleman 1994-ben elvégzett kísérletét mutatjuk be, melyben a Hamilton-út probléma megoldásával bizonyította, hogy a DNS molekulák segítségével számítási problémákat is megoldhatunk. Ugyancsak bemutatjuk röviden annak a folyamatnak egy elméleti modelljét, aminek segítségével a csillós egysejtűek a mikronukleusz formából 3 DNS láncokon értelmezett művelet segítségével előállítják a genetikai kódjukat tartalmazó makronukleusz formát. (Itt jegyezzük meg, hogy az érdeklődő olvasó a DNS-számítások témakör egy sokkal részletesebb leírását, illetve jóval több a DNS által inspirált számítási paradigma bemutatását találja meg a DNS-számítógépek és formális modelljeik könyvben.)

A könyv IV. része a membránszámításokba (P-rendszerek) nyújt bevezetést. Ezt a paradigmát, a XX. század legvégén, Gh. Păun hozta létre, a sejtek működésének analógiájára. A membránok régióiban objektumok multihalmazai adják a számítás konfigurációit, amik evolúciós szabályok (maximálisan párhuzamos) alkalmazásával alakulnak a következő konfigurációba. A számítás kimenetét a kimeneti membránban összegyűjtött objektumokkal, vagy a számítás közben a környezetbe juttatott objektumok segítségével értelmezhetjük. Ily módon a multihalmaz számításokkal rokon a paradigma. A membrán-struktúra számítás közbeni megváltozásával, az aktív membránok segítségével, bonyolult problémák oldhatók meg rövid idő alatt maximálisan párhuzamosan, köszönhetően az akár exponenciálisan növekvő tárhelynek. A szimport-antiport rendszerekben az evolúciós szabályok helyét kommunikációs szabályok veszik át. Ilyeneket használunk a P-automatákban is, amelyekkel a számítás közben beszívott (importált) objektumok alapján felépített inputokat tudjuk elfogadni.

A könyv V. része a kvantuminformatikába és -számításokba nyújt rövid bevezetést, amit a kvantummechanika különös jelenségeinek ismertetésével kezdünk. Ezután definiáljuk a kvantum bitet (kubit), illetve az ezekből felépülő kvantum regisztert. A kubitek evolúciója, vagyis értékük változása a számítás alatt kvantum- (vagy kubit-) kapuk segítségével történik. Az egyszerű kapukból állíthatjuk össze a kvantumalgoritmusokat. A legegyszerűbb algoritmusok után a kvantum számítások kriptográfiai jelentőségéről és a gyakorlati megvalósításokról is ejtünk szót.

Azt gondoljuk, hogy nemcsak az elmélet iránt érdeklődő, de a gyakorlati szakemberek számára is inspiráló lehet és így új, hatékonyabb problémamegoldást tehet lehetővé, ha tudnak más paradigmák szerint is gondolkodni, problémát megközelíteni... Ezért ajánljuk ezt a könyvet a számítások, illetve számítási paradigmák iránt érdeklődő mester-, illetve PhD hallgatóknak, illetve szakembereknek.

Debrecen, 2013. július

Nagy Benedek