Új számítási paradigmák

Bevezetés az intervallum-értékű, a DNS-, a membrán- és a kvantumszámítógépek elméletébe

Nagy Benedek


Tartalom

Bevezetés
I. A Klasszikus Számítási Paradigma Áttekintése
1. A hagyományos számítási modell
1.1. A Turing-gép
1.1.1. Univerzális Turing-gép
1.2. A Neumann-elv
1.3. Hagyományos számítógépek
1.3.1. A klasszikus logika
1.3.2. Bitek és bájtok
1.4. Bonyolultságelméleti alapfogalmak
1.4.1. A SAT probléma megfogalmazása
1.4.2. A Hamilton-út probléma megfogalmazása
1.5. Néhány nem-hagyományos elvű algoritmus
1.5.1. A Spagetti-számítógép rendezési algoritmusa
1.5.2. Rendezés a gravitáció segítségével
II. Az Intervallum-értékű Számítási Paradigma
Bevezetés az Intervallum-értékű paradigmába
1. Motivációk
2. Az Intervallum-értékű logika
2.1. A többértékű logikák szükségessége
2.2. Többértékű és fuzzy logikák
2.2.1. Belnap négyértékű logikája
2.2.2. Post logikája
2.2.3. A Gödel-féle logika
2.2.4. Łukasiewicz-féle logikák
2.2.5. Kleene logikája
2.2.6. A szorzat-logika
2.2.7. A bitek logikája
2.2.8. A három fő fuzzy rendszer összehasonlítása
2.3. Az intervallum-értékű logika definíciója
2.3.1. Intervallum-értékek
2.3.2. Logikai operátorok
2.3.3. Nem-logikai operátorok
2.4. Többértékű és fuzzy logikák vizualizációja intervallum-értékekkel
2.4.1. A Gödel-féle logika szemléltetése
2.4.2. A Łukasiewicz-féle logika szemléltetése
2.4.3. A szorzat-logika szemléltetése
2.4.4. A bitek logikájának szemléltetése - vizuális igazságtábla
3. Intervallum-értékű számítások
3.1. A klasszikus és az intervallum-értékű paradigma kapcsolata
3.1.1. A hagyományos számítógép modellezése
3.1.2. Lista-reprezentáció
3.2. Intervallum-értékű számítások formális megadása
3.3. Eldöntési feladatok megoldása
3.3.1. A SAT probléma megoldása lineáris időben
3.3.2. A qSAT probléma és lineáris lépésszámú megoldása
3.4. Diszkrét értékű függvények kiszámítása
3.4.1. Prímfaktorizáció
3.4.2. Diszkrét logaritmus probléma megoldása
3.5. Irodalmi hivatkozások, az intervallum-értékű számítási paradigma története
3.6. Ellenőrző kérdések
3.7. Feladatok
III. A DNS-számítások Alapjai
Bevezetés a DNS-számítások elméletébe
4. A DNS felépítése és vele végezhető műveletek
4.1. A DNS szerkezete
4.1.1. A nukleotidok felépítése
4.1.2. Az egyszálú DNS
4.1.3. Watson-Crick párok – a kétszálú DNS
4.2. Műveletek a DNS-sel
4.2.1. Denaturálás
4.2.2. Renaturálás vagy hibridizáció
4.2.3. Szintetizálás
4.2.4. Sokszorozás
4.2.5. Pecázás
4.2.6. Hosszmérés
4.2.7. Bázissorend meghatározása - a szekvenálás
4.2.8. Enzimek
5. DNS-számítások a gyakorlatban
5.1. Adleman kísérlete — a Hamilton-út probléma megoldása
5.2. Lipton megoldása a SAT-ra
6. Betekintés a sejten belüli számításokba
6.1. A csillós egysejtűek
6.2. A génképzési feladat
6.3. A génképzés műveletei
6.3.1. Az ld művelet
6.3.2. A hi művelet
6.3.3. A dlad művelet
6.4. A génképzés modellezése
6.5. Irodalmi és egyéb megjegyzések
6.6. Ellenőrző kérdések
6.7. Feladatok
IV. Membránszámítások
Bevezetés a membránszámítások elméletébe
7. Membránszámítások — az alapok
7.1. A biológiai membránok
7.2. A formális membrán számítási modell
7.3. Multihalmazok és számítások: Parikh nyelvek
7.4. Műveletek a membránrendszerben
7.4.1. Evolúciós szabályok
7.4.2. A számítás eredménye
8. Számítások aktív membránokkal
8.1. Számítások membránok megszűnésével
8.2. Számítások a membránok számának növelésével
8.3. Bonyolult számítási problémák megoldása
8.3.1. A Hamilton-út feladat megoldása membránok születésével
8.3.2. A SAT probléma megoldása elemi membránok osztódásával
8.3.3. Általános párhuzamos membránszámítógép
8.3.4. Megoldások uniformitása
9. A P-automata
9.1. Szimport-antiport rendszerek
9.2. Az input értelmezése és a számítás menete P-automatában
9.2.1. Példák P-automatára
9.2.2. P-automaták gátló és segítő multihalmazokkal
9.3. A membránrendszerek számítási ereje
9.3.1. Mátrix nyelvtanok
9.3.2. Univerzalitási eredmények membránrendszerekre
9.4. Összefoglalás, a paradigma története és a legújabb kutatási irányok
9.5. Ellenőrző kérdések
9.6. Feladatok
V. Kvantumszámítások
Bevezetés – a kvantumjelenségek és a kvantumszámítógépek
10. A kvantumszámítások szempontjából fontos fizikai jelenségek
10.1. Kvantumoptika – szuperpozíció
10.2. A kvantum-összefonódás
10.3. Az Einstein-Podolsky-Rosen kísérlet
10.4. A mérés
10.4.1. Heisenberg-féle határozatlansági elv
10.4.2. A Schrödinger macskája
10.4.3. Oldjuk meg egy méréssel
10.5. „Megfordítható” számítások
11. A kvantumszámítások alapjai
11.1. A kubit
11.2. Kubit-transzformációk
11.3. A kvantumregiszter
12. Kvantumkapuk
12.1. Elméleti leírás és eredmények
12.1.1. Ismeretlen kvantumállapot nem másolható
12.1.2. Összefonódott állapotok leírása
12.2. Egykubites kapuk
12.2.1. A Hadamard-transzformáció megadása
12.2.2. Forgató operátorok
12.2.3. Negáció kvantumkapukkal
12.2.4. Fáziseltoló operátorok
12.3. Kétkubites kapuk
12.3.1. A vezérelt NOT kapu
12.3.2. Vezérelt fáziseltolás
12.3.3. Kubit csere
12.4. Nagyobb kapuk
12.5. Univerzális kapuhalmazok
13. Kvantumalgoritmusok
13.1. Az első kvantumalgoritmusok
13.1.1. A Deutsch algoritmus
13.1.2. A Deutsch-Jozsa algoritmus
13.1.3. Simon algoritmusa
13.1.4. Grover (kereső) algoritmusai
13.2. Kommunikációs és kriptográfiai kvantumalgoritmusok
13.2.1. Shor algoritmusa – prímfaktorizáció
13.2.2. Kvantumkommunikáció
13.2.3. Kvantumkriptográfia
13.2.4. Kvantumteleportáció
13.3. Fizikai megvalósítások
13.3.1. Adiabatikus kvantumszámítógép és a D-Wave
13.3.2. Az NMR kvantumszámítógép
13.3.3. Optikai kvantumszámítógép
13.4. Kvantumszámítógépek – összefoglalás és irodalom
13.5. Ellenőrző kérdések
13.6. Feladatok
Összefoglalás és további irodalom az új számítási paradigmákról
1. Utószó

Az ábrák listája

1.1. A Turing-gép rajza.
1.2. Többszalagos Turing-gép szimulációja egy szalaggal, összetett ábécé szimbólumokkal.
1.3. A fontosabb bonyolultsági osztályok hierarchiája.
1.4. A spagetti rendezés: egy csoportos összehasonlítással kiválasztható a leghosszabb elem.
1.5. A „gravitációs” rendezés.
2.1. A Belnap-féle logika igazságértékei.
2.2. A A és intervallum-értékek grafikus ábrázolása. és A és intervallum-értékek grafikus ábrázolása. intervallum-értékek grafikus ábrázolása.
2.3. Példa negációra intervallum-értékekkel.
2.4. Példa konjunkcióra és diszjunkcióra intervallum-értékekkel.
2.5. Példa implikációra intervallum-értékekkel.
2.6. A Cantor-halmaz előállítása az intervallum-értékek szorzásával.
2.7. Példa a Gödel-féle konjunkcióra és diszjunkcióra intervallum-értékekkel.
2.8. A Gödel-féle negáció modellezése intervallum-értékekkel.
2.9. Példák a Gödel-féle implikációra intervallum-értékekkel.
2.10. A Łukasiewicz-féle összekötőjelek modellezése intervallum-értékekkel.
3.1. Intervallum-értékek kiszámítása az ítéletváltozókhoz.
3.2. Az intervallum-értékű számítás egy kielégíthető formulára (balra) és a legbelső egzisztenciális kvantoros részformula kiszámítása lépésenként (jobbra).
3.3. Nem kielégíthető formula elemzése (bal oldalon) és egy univerzális kvantoros formula értékelése lépésenként (jobb oldalon).
3.4. Az Az input intervallum-értékű reprezentációja. input intervallum-értékű reprezentációja.
3.5. A A és intervallum-értékek esetre. és A és intervallum-értékek esetre. intervallum-értékek A és intervallum-értékek esetre. esetre.
3.6. A A és intervallum-értékek és a értékek által reprezentált egészek. és A és intervallum-értékek és a értékek által reprezentált egészek. intervallum-értékek és a A és intervallum-értékek és a értékek által reprezentált egészek. értékek által reprezentált egészek.
3.7. A A és intervallum-értékek és az általuk reprezentált egészek. és A és intervallum-értékek és az általuk reprezentált egészek. intervallum-értékek és az általuk reprezentált egészek.
3.8. A A és intervallum-értékek által reprezentált számok szorzatai. és A és intervallum-értékek által reprezentált számok szorzatai. intervallum-értékek által reprezentált számok szorzatai.
3.9. A A és intervallum-értékek egyenlőségének vizsgálata. és A és intervallum-értékek egyenlőségének vizsgálata. intervallum-értékek egyenlőségének vizsgálata.
3.10. A kódolt szorzótényező értéke.
3.11. Az output meghatározása.
3.12. Az input kódolása intervallum-értékekkel (Az input kódolása intervallum-értékekkel ( ). ).
3.13. A lehetséges kitevők intervallum-értékekkel és jelentésük.
3.14. Hatványozás (5 maradékosztályában).
3.15. A A és a értékek meghatározása a példában. és a A és a értékek meghatározása a példában. értékek meghatározása a példában.
3.16. Egyenlőség tesztelése a példában.
4.1. Az adenin molekula: a bázis, a pentóz és a foszfát-csoport szerkezete és kapcsolódásuk módja.
4.2. A citozin bázisának felépítése.
4.3. A guanin bázisának kémiai felépítése.
4.4. A timin molekula bázisa.
4.5. DNS lánc kialakulása nukleotidokból vízkilépéssel.
4.6. A citozin és a guanin bázisai közt háromszoros hidrogénkötés alakulhat ki.
4.7. A polimeráz enzim kiegészíti a DNS láncot.
4.8. DNS láncok szétválasztása hossz alapján gélelektroforézissel.
4.9. Egy vágás „ragadós végek” létrehozásával.
5.1. Az Adleman által vizsgált gráf.
5.2. A csúcsoknak és az éleknek megfelelő láncokból a H-kötések által létrejönnek az utakat jelentő kétszálú DNS láncok.
5.3. Az Az három változóval rendelkező formulákhoz használható gráf. három változóval rendelkező formulákhoz használható gráf.
5.4. A példaként adott formula elemi diszjunkcióiban levő literálokat pecázzuk.
6.1. A makronukleusz felépítése, az összerakott génsorozat.
6.2. Az ld operátor.
6.3. A hi operátor.
6.4. A dlad szétvágás és újraillesztés operátor.
7.1. A sejt membránjának szerkezete.
7.2. A membránalkotó foszfolipid molekula szerkezete.
7.3. A sejt, mint membrán számítási modell.
7.4. Fa, ami leírja a 7.3. ábrán látható membránstruktúrát.
7.5. Példa kooperatív membránrendszerre.
8.1. A membránfal vastagsága (átjárhatósága, megléte) speciális szimbólumokkal szabályozható.
8.2. Kiinduló állapot.
8.3. Egy példaszámítás menete.
8.4. Általános párhuzamos feladatmegoldó (membrán-) számítógép modellje.
9.1. P-automata, ami az input P-automata, ami az input -k és -k számát méri. -k és P-automata, ami az input -k és -k számát méri. -k számát méri.
9.2. P-automata a zárójelek nyelvéhez.
9.3. P-automata segítő és gátló multihalmazokkal.
10.1. Mermin kísérlete.
10.2. Érmék kiválasztása a méréshez.
10.3. A Toffoli kapu diagramja.
11.1. Kubit reprezentációja és mérése.
12.1. A A kapu megvalósítása három kapuval (a satírozott kis gömb a vezérlőszálat jelzi). kapu megvalósítása három A kapu megvalósítása három kapuval (a satírozott kis gömb a vezérlőszálat jelzi). kapuval (a satírozott kis gömb a vezérlőszálat jelzi).
12.2. A kvantumos félösszeadó kapu megvalósítása egy A kvantumos félösszeadó kapu megvalósítása egy és egy kapuval. és egy A kvantumos félösszeadó kapu megvalósítása egy és egy kapuval. kapuval.
12.3. A vezérelt-vezérelt-A vezérelt-vezérelt- kapu szimulációja kisebb vezérelt kapukkal. kapu szimulációja kisebb vezérelt kapukkal.
13.1. A Deutsch algoritmus.
13.2. A Deutsch-Jozsa algoritmus kapcsolási rajza.
13.3. A Simon algoritmus kapcsolási rajza.
13.4. Összefonódott kubitek előállítása (pl. kriptográfiai alkalmazáshoz).
13.5. A kvantumteleportáció elve.
13.6. 128 kubites D-Wave chip. (A fotó a D-Wave Systems Inc. engedélyével/Courtesy of D-Wave Systems Inc.)
13.7. Valódi véletlenszám generátor kvantumoptikai alapon (a fotó a Quantis quantum randomgenerátorról a gyártó cég engedélyével).

A táblázatok listája

1.1. Az alapvető logikai operátorok igazságtáblája.
1.2. Az alapvető logikai operátorok működése egy bájton (bitek sorozatán), ahol minden és bit értéke a halmazból való.
1.3. A SHIFT operátor hatása egy bájtra.
2.1. Tagadás Belnap logikájában.
2.2. A konjunkció Belnap logikájában.
2.3. A diszjunkció Belnap logikájában.
2.4. Speciális egyargumentumú műveletek Belnap logikájában.
2.5. A negáció Heyting logikájában.
2.6. Az implikáció Heyting logikájában.
2.7. A negáció Łukasiewicz 4-értékű logikájában.
2.8. Az implikáció Łukasiewicz 4-értékű logikájában (a művelet eredményét az átskálázott értékekkel tüntettük fel).
2.9. A három alapművelet a bitek sorozatán végrehajtva.
2.10. A fuzzy rendszerek jellemzése.
2.11. Az alapvető logikai operátorok intervallum-értékeken.
2.12. Igazságtábla készítése.
9.1. Példa mátrix nyelvtanra, ahol nemterminálisok, terminálisok, a mondatszimbólum, a szabályok pedig:

Az egyenletek listája

11..
11..
11..