|
|
DNA Computing and Applications
Fiala, Jan ; Petrlík, Jiří (referee) ; Bidlo, Michal (advisor)
This thesis focuses on the design and implementation of an application involving the principles of DNA computing simulation for solving some selected problems. DNA computing represents an unconventional computing paradigm that is totally different from the concept of electronic computers. The main idea of DNA computing is to interpret the DNA as a medium for performing computation. Despite the fact, that DNA reactions are slower than operations performed on computers, they may provide some promising features in the future. The DNA operations are based on two important aspects: massive parallelism and principle of complementarity. There are many important problems for which there is no algorithm that would be able to solve the problem in a polynomial time using conventional computers. Therefore, the solutions of such problems are searched by exploring the entire state space. In this case the massive parallelism of the DNA operations becomes very important in order to reduce the complexity of finding a solution.
|
|
|
Watson-Crick Models for Formal Language Processing
Hammer, Jan ; Tomko, Martin (referee) ; Křivka, Zbyněk (advisor)
Tato práce se zabývá Watson-Crickovými jazyky, které jsou inspirovány výpočty nad DNA, dále jejich modely a algoritmy pro rozhodování členství řetězců v těchto jazycích. Analyzuje nedávno představený algoritmus nazvaný WK-CYK a prezentuje algoritmus založený na prohledávání stavového prostoru, jehož základem je standardní prohledávání prostoru do šířky, ale používá množství optimalizací a heuristik, aby byl v praxi efektivnější a dokázal analyzovat delší vstupy. Klíčové jsou heuristiky pro prořezávání stavového prostoru (detekují slepé větve) a heuristiky pro výběr nejslibnějších větví pro další výpočet. Tyto dva algoritmy jsou testovány na 20 různých Watson-Crickových gramatikách (40 včetně jejich verzí v Chomského normální formě). Zatímco WK-CYK je schopen rozhodnout členství v jazyce v rozumném čase u vstupů o délce zhruba 30-50 symbolů, jeho efektivnost je velmi konzistentní u různých gramatik a různých vstupů, algoritmus prohledávající stavový prostor je obvykle (v 89-98 % případů) efektivnější a je schopen provést výpočet pro vstupy s délkou o stovkách často i tisících symbolů. Tedy tento algoritmus má potenciál být vhodným nástrojem pro praktické použití při rozhodování členství ve Watson-Crickových jazycích a nabízí vhodný základ pro další vývoj a vylepšení, která by dále zvyšovala efektivitu algoritmu.
|
|
|
Watson-Crick Models for Formal Language Processing
Hammer, Jan ; Tomko, Martin (referee) ; Křivka, Zbyněk (advisor)
Tato práce se zabývá Watson-Crickovými jazyky, které jsou inspirovány výpočty nad DNA, dále jejich modely a algoritmy pro rozhodování členství řetězců v těchto jazycích. Analyzuje nedávno představený algoritmus nazvaný WK-CYK a prezentuje algoritmus založený na prohledávání stavového prostoru, jehož základem je standardní prohledávání prostoru do šířky, ale používá množství optimalizací a heuristik, aby byl v praxi efektivnější a dokázal analyzovat delší vstupy. Klíčové jsou heuristiky pro prořezávání stavového prostoru (detekují slepé větve) a heuristiky pro výběr nejslibnějších větví pro další výpočet. Tyto dva algoritmy jsou testovány na 20 různých Watson-Crickových gramatikách (40 včetně jejich verzí v Chomského normální formě). Zatímco WK-CYK je schopen rozhodnout členství v jazyce v rozumném čase u vstupů o délce zhruba 30-50 symbolů, jeho efektivnost je velmi konzistentní u různých gramatik a různých vstupů, algoritmus prohledávající stavový prostor je obvykle (v 89-98 % případů) efektivnější a je schopen provést výpočet pro vstupy s délkou o stovkách často i tisících symbolů. Tedy tento algoritmus má potenciál být vhodným nástrojem pro praktické použití při rozhodování členství ve Watson-Crickových jazycích a nabízí vhodný základ pro další vývoj a vylepšení, která by dále zvyšovala efektivitu algoritmu.
|
|
|
DNA Computing and Applications
Fiala, Jan ; Petrlík, Jiří (referee) ; Bidlo, Michal (advisor)
This thesis focuses on the design and implementation of an application involving the principles of DNA computing simulation for solving some selected problems. DNA computing represents an unconventional computing paradigm that is totally different from the concept of electronic computers. The main idea of DNA computing is to interpret the DNA as a medium for performing computation. Despite the fact, that DNA reactions are slower than operations performed on computers, they may provide some promising features in the future. The DNA operations are based on two important aspects: massive parallelism and principle of complementarity. There are many important problems for which there is no algorithm that would be able to solve the problem in a polynomial time using conventional computers. Therefore, the solutions of such problems are searched by exploring the entire state space. In this case the massive parallelism of the DNA operations becomes very important in order to reduce the complexity of finding a solution.
|
guest ::
