Sztring építő rendszerek és Watson-Crick véges automaták leírási bonyolultsága

A tétel rövid nézete
dc.contributor.advisorVaszil, György
dc.contributor.authorMurvai, András
dc.contributor.departmentDE--Informatikai Kar
dc.date.accessioned2026-02-12T20:58:57Z
dc.date.available2026-02-12T20:58:57Z
dc.date.created2025
dc.description.abstractA dolgozatban két, DNS számítás inspirálta formális számítási modellt, a Watson-Crick automatát és a sztring építő rendszert, illetve ez utóbbi változatait vizsgálom az alapján, hogy leírási bonyolultságuk függvényében hogyan alakul az egymáshoz viszonyított számítási erejük, azaz a formális nyelveket definiáló képességük. A DNS-t felépítő két polinukleotidszál, illetve a szálakat felépítő nukleotidok bázisai között fennálló ún. Watson-Crick komplementaritás alkalmassá teszi a DNS molekulákat számítási feladatok elvégzésére. A két számítási modell a DNS molekulák absztrakciójának tekinthető kettős sztringekkel dolgozik, melyekre tekinthetünk úgy, mint egy "alsó" és egy "felső" betűsorozatból álló sztringpárra, ahol az egyes, azonos pozíción lévő betűk között egy szimmetrikus reláció áll fenn. Egy Watson-Crick automata a bemeneti szalagjára írt kettős sztringeket olvassa, az aktuális állapota függvényében a két olvasófeje egymástól függetlenül mozogva tud olvasni az alsó, illetve felső sztringről betűket, mely alapján újabb állapotot vehet fel. Egy sztring építő rendszer sztringpárok (ún. építőelemek) összeillesztésével épít fel kettős sztringeket, az adott változattól függően ezen építőelemek vagy egy, vagy három halmazból származnak, illetve az elemek összeillesztésére megszabhatunk egy speciális illesztési előfeltételt. A vizsgált számítási modellek viszonya nagyban függ attól, hogy a sztring építő rendszerek esetén megkülönböztetünk-e több elemhalmazt vagy megköveteljük-e az imént említett speciális illesztési feltételt, Watson-Crick automaták esetén pedig hány állapotot engedélyezünk, illetve egybetűs vagy tetszőleges ábécé feletti nyelveket vizsgálunk-e. Ezen megszorításokkal a modellek leírásának tömörségét, bonyolultságát alakíthatjuk. A dolgozatban a különböző leírási bonyolultságú számítási modellekhez tartozó nyelvosztályok viszonyáról fogalmazok meg állításokat.
dc.description.courseProgramtervező informatikus
dc.description.degreeMSc/MA
dc.format.extent43
dc.identifier.urihttps://hdl.handle.net/2437/404567
dc.language.isohu
dc.rights.infoHozzáférhető a 2022 decemberi felsőoktatási törvénymódosítás értelmében.
dc.subjectszámítástudomány
dc.subjectautomaták
dc.subjectformális nyelvek
dc.subject.dspaceInformatika::Számítógéptudomány
dc.titleSztring építő rendszerek és Watson-Crick véges automaták leírási bonyolultsága
Fájlok
Eredeti köteg (ORIGINAL bundle)
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
szakdolgozat.pdf
Méret:
719.9 KB
Formátum:
Adobe Portable Document Format
Leírás:
szakdolgozat
Megjelenítés
Engedélyek köteg
Megjelenítve 1 - 1 (Összesen 1)
Nincs kép
Név:
license.txt
Méret:
2.35 KB
Formátum:
Item-specific license agreed upon to submission
Leírás:
Letöltés
Gyűjtemények
Hallgatói dolgozatok (Informatikai Kar)