Összefoglalás és további irodalom az új számítási paradigmákról

Tartalom

1. Utószó

Az új számítási paradigmák a hagyományos Neumann-Turing szekvenciális paradigmának elvetik valamely korlátját, leggyakrabban a számítások szekvencialitása helyett párhuzamos számításokat engednek meg. A párhuzamos számításokkal kapcsolatban ajánljuk a Herendi Tamás-Nagy Benedek: Párhuzamos algoritmusmodellek c. könyvet amely e könyvvel egyidőben jelenik meg.

A párhuzamosságnak a számításokat tekintve két fő fajtáját különböztethetjük meg: a vagy-párhuzamosságot és az és-párhuzamosságot (lásd pl. R. Loos, B. Nagy: On the Concepts of Parallelism in Biomolecular Computing, TRIANGLE: LANGUAGE, LITERATURE, COMPUTATION 6 (2011), 109–118). A vagy-párhuzamosság (ami a „kínai hadsereg” útkereső modelljének felel meg: minden elágazásnál minden irányba megy valaki, elég sokan vannak ahhoz, hogy ez mindig megoldható legyen, így valaki csak átér a hegység túloldalára a hírrel) esetén több adatra próbáljuk ugyanazt az algoritmust futtatni, bármelyik adhatja az eredményt. Ez a fajta párhuzamosság közel áll a nemdeterminisztikus próbálgatáshoz. 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. Ez a párhuzamosság az adat-párhuzamos számításokat is jellemzi. (Ha szekvenciálisan számolunk, de szerencsénk van, akkor ugyanannyi idő alatt oldhatjuk meg a problémát, mint a vagy-párhuzamos algoritmussal, igaz ott elég erőforrás esetén a szerencsének nincs szerepe, determinisztikus lesz a megoldás.) Ez a vagy-párhuzamosság jellemzi a DNS számításokat, ahogyan pl. Adleman képes volt Hamilton-út előállítására. Ugyancsak ilyen jellegű a kvantumpárhuzamosság is, ahol egy szuperpozícióval kubitbe kódolva egyszerre számolunk több adattal is. Az intervallum-számításoknál is megjelenik ez a fajta párhuzamosság, amint az intervallum különböző részein (mint bitsorozatokon például) egyszerre végezzük el a logikai műveleteket.

Ezzel 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. Ez a fajta párhuzamosság a „high-performance computing”-ot jellemzi. A vagy-párhuzamossággal szemben ez a fajta párhuzamosság kihat a megoldási időre is, a megfelelően használt párhuzamos erőforrásokkal az csökkenthető. A problémát sokszor az jelenti, hogy egyáltalán nem lehet automatikus módon megtenni a részproblémákra bontást és így megfelelően kihasználni az erőforrásokat. A tárgyalt paradigmák közül pl. a membránszámítások maximálisan párhuzamos szabály alkalmazásai tartoznak ide, pl. amikor egy szót generál a rendszer.

Sok nemhagyományos számítási paradigma analóg jelenségeken alapul, így az analóg és digitális világ, illetve ennek megfelelően a számítások különböző tulajdonságai is különbségként jelennek meg a hagyományos digitális számítások és az adott analóg számítási paradigma között. A világ analóg, a digitálissal (bármennyire is szebben hangzik sokak számára), csak közelíteni tudjuk és akarjuk. A mai informatika a digitális technikán alapul. Mindent bitsorozatokkal reprezentálunk (hangot, képet, videót stb.). A digitális technika egyik óriási fegyverténye a pontos másolás lehetősége. A DNS számításokat is tekinthetjük ebben az értelemben digitálisnak (csak itt nem a bináris ábécét, hanem a négy aminósav által alkotott ábécét használjuk). Ezzel szemben a valódi (analóg) világban nem tudunk pontos másolatot készíteni, mindent csak bizonyos méréshatáron belül tudunk közelíteni. Amikor vonaton utazunk egy tájegységen keresztül, akkor hosszú ideig nagyon hasonló képet láthatunk, viszont soha nem látjuk útközben kétszer teljesen ugyanazt a képet. A digitális technikában viszont az a legegyszerűbb (és pl. animációs filmek esetén gyakran alkalmazott) technika, ha a háttér periodikusan ismétlődik. A kvantumszámítások ebből a szempontból valahol az analóg és a digitális világ között helyezkednek el, hiszen a kubitek analóg, folytonos mennyiségeket vehetnek fel értékekül, pontos másolásuk (klónozásuk) általában nem lehetséges, de a mérés kapcsán csak digitálisan férünk hozzájuk.

Végül néhány a jelen munkához hasonló jellegű angol nyelvű munka, melyekben több számítási paradigma is részletezésre kerül. Az egyik olyan könyv, amely egyszerre nyújt bepillantást többféle paradigmába is a (Calude, Păun 2001) könyv, ebben a DNS- és a membránszámítások mellett a kvantumszámításokról is olvashatunk. Több (az ebben a könyvben tárgyaltak közül is több) számítási paradigmáról található meglehetősen részletes és naprakész leírás, a 2012-ben megjelent 4 kötetes, összesen több, mint kétezer oldalas (Handbook 2012) könyvben, melynek főbb részei a sejtautomatákkal, a neurális- és az evolúciós számításokkal, a molekuláris számításokkal (ideértve a DNS- és membránszámításokat), illetve a kvantumszámításokkal is foglalkoznak.

  1. (Calude, Păun 2001) C. S. Calude, Gh. Păun: Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing, Taylor & Francis/Hemisphere, London, Bristol, PA, USA, 2001.

  2. (Handbook 2012) G. Rozenberg, T. Bäck, J. N. Kok (szerk.): Handbook of Natural Computing, (4 volumes), Springer, 2012.

Több olyan magas színvonalú konferenciasorozat is létezik, ahol az új számítási paradigmákkal kapcsolatos eredményeket bemutatják az ezzel foglalkozó kutatók. Általános (többféle paradigmával kapcsolatos) ilyen konferenciák pl. a CiE: Computability in Europe (9. ilyen konferencia 2013-ban Milánóban, a 10. pedig 2014-ben Budapesten lesz), UCNC: Unconvential Computation and Natural Computation (2013-ban Milánóban a 12.), DCM: International Workshop on Developments in Computational Models (9. alkalommal 2013-ban, Argentínában).

Inkább csak egy-egy paradigmára koncentráló szűkebb spektrumú konferenciák pl. DNA: International Meeting on DNA Computing (2013-ban az USA-ban, a 19. ilyen konferencia), illetve a CMC: International Conference on Membrane Computing (2013-ban Moldovában, már a 14. alkalom, 2012-ben pedig Budapesten volt a 13.).

1. Utószó

A szerző 1996-ban végzett fizikusként, 1997-ben programozó matematikusként, 1998-ban filozófusként (logika specializációval), 1999-ben programtervező matematikusként, 2000-ben fizikatanárként, valamint általános és alkalmazott nyelvészként. 1996-ban hallgatóként részt vett az ESSLLI (European Summer School in Logic, Language and Information) nyári iskolán, Prágában. Az itt hallott előadások inspirálták arra, hogy még ebben az évben kidolgozza az intervallum-értékű logikai rendszert, amivel fuzzy logikai rendszerek reprezentálhatóak. 1997-ben az OTDK-n különdíjat kapott e dolgozatára. Közben 1998-ban PhD tanulmányokat is kezdett Debrecenben (az akkori Kossuth Lajos Tudományegyetemen, 2000-től Debreceni Egyetemen). 1998-ban egy szemesztert Németországban a berlini Freie Universitäten tanult logikát, majd 2002-ben egy szemesztert töltött az USA-ban az Indiana University-n, Bloomingtonban. Elsősorban itt is logikával foglalkozott, az intervallum-értékű logikával kapcsolatos eredményeit angolul is előadta Mike Dunn kurzusán. Emellett a kvantumszámítógépek alapjaival is megismerkedett a Meglicki, Zdislaw: Three Lectures on Quantum Computing, Foundations of Computing seminar rövid kurzuson. 2003-ban és 2004-ben részt vett a International PhD School on Formal Languages and Applications iskola kurzusain a spanyolországi Rovira i Virgili Universidad intézményben Tarragonában. Itt a GRLMC (Research Group on Mathemtical Linguistics) tagjaként ismerkedett meg részletesen a DNS számítások alapjaival (ezen kurzusok oktatói: G. Rozenberg, Tom Head, M. Ogihara); a membránszámításokkal, ezt Gh. Păuntól tanulta; illetve a kvantumszámításokkal kapcsolatban is tovább fejlesztette ismereteit, ezt a kurzust C. Calude tartotta. 2004-ben itt kezdte kidolgozni az intervallum-értékű logikára épülő intervallum-értékű számítási paradigmát, amivel kapcsolatos kutatásaihoz 2006-ban Vályi Sándor is csatlakozott. A szerző 2004-ben PhD, majd 2007-ben habilitációs fokozatot kapott a Debreceni Egyetemen Matematika és Számítástudományok területen. Időközben és azóta különböző konferenciák meghívott előadásai, tutoriáljai segítségével követte az új számítási paradigmákat, így – az imént már említett nevek mellett, – többek közt a kvantumszámítások témakörben H. Buhrmann (CiE 2005), M. Hirversalo (DLT 2008), G. Brassard (CiE-UCNC 2013); DNS és membránszámításokkal kapcsolatban pl. Ion Petre (AFL 2008), Csuhaj-Varjú Erzsébet (CiE 2008), N. Jonoska (DLT 2004, CiE 2010), Lila Kari (UCNC 2013), előadásait és ehhez kapcsolódó anyagait, valamint a szűkebb témakörök konferenciáit/workshopjait (DNA 2007, DCM 2012, CMC 2012) figyelte.

Amint láthatjuk a különböző számítási paradigmák közül több a számítástudomány, a matematika és az informatika mellett más tudományterületek, így pl. a biológia vagy a fizika bizonyos fokú ismeretét is feltételezi. Ebből is kitűnik, hogy a tudomány (és ezen belül a számítástudomány és az informatika) továbbfejlődéséhez szükség van interdiszciplináris kutatásokra, amelyek a különböző tudományterületek ismereteit képesek együttesen felhasználni, arra, hogy legalább az egyik területen valamilyen előrelépést tudjunk felmutatni. Az informatika és a számítástudomány szempontjából néhány ilyen jelentős irányt mutattunk be e könyvben, reméljük az olvasó kedvet kapott néhány ilyen irány további tanulmányozásához (ehhez ajánljuk a részek végén jelzett irodalmat, illetve az azokban az irodalmakban szereplő további irodalmat).

A szerző ezúton is szeretné köszönetét kifejezni tanárainak, kollégáinak, akik kutatási anyagokkal, véleményükkel, tanácsaikkal segítették munkáját. Köszönet azoknak a hallgatóknak, akik részt vettek hasonló témájú kurzusain, ott feltett kérdéseikkel, javaslataikkal befolyásolták a könyv anyagát/formáját. Külön köszönet illeti Vályi Sándor lektort lelkiismeretes munkájáért. Végül, de nem utolsó sorban a szerző köszöni a családjának azt a mérhetetlen türelmet, amivel hagyták, hogy azt a nem kevés időt a könyv létrehozására fordítsa...