跳到主要內容

臺灣博碩士論文加值系統

(100.28.227.63) 您好!臺灣時間:2024/06/15 01:02
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:吳昱融
研究生(外文):Yu-rong Wu
論文名稱:對輸出視而不見的化學反應網路的速度
論文名稱(外文):The speed of output-oblivious chemical reaction network
指導教授:陳和麟
指導教授(外文):Ho-lin Chen
口試委員:于天立劉智弘呂學一
口試委員(外文):Tian-Li YuChih-Hung LiuHI Lu
口試日期:2023-01-18
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2023
畢業學年度:111
論文頁數:46
中文關鍵詞:分子計算化學反應網路
外文關鍵詞:Molecular ComputationChemical Reaction Networkoutput oblivious
DOI:10.6342/NTU202300354
相關次數:
  • 被引用被引用:0
  • 點閱點閱:73
  • 評分評分:
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
隨機化學反應網路 (Chemical Reaction Network) 被科學家廣泛的使用來描述分子之間的反應。化學反應網路可以視為一種用來描述分子反應的語言。在化學反應網路中所能夠做到的計算,在現實中的分子也能夠做到。我們假設每個反應的反應率都是1,因為在穩定計算下反應率不會影響到最後的結果。在此篇中我們專注在” 對輸出視而不見的化學反應網路” 上,此種網路可以直接和其他化學反應網路串接且不會有錯誤。 [3] 第一個定義了輸出不會當成某些反應的反應物的化學反應網路為” 對輸出視而不見的化學反應網路”,並且證明了這類網路能夠計算什麼函數,但裡面有一些很慢的反應。我們對這些慢的反應進行改良,並將計算”對輸出視而不見的化學反應網路” 的時間從 O(N^r) 降到 O(NlogN ).
Stochastic Chemical Reaction Networks(CRNs) are widely used to describe how molecules interact with each other by scientists. CRNs can be viewed as a language for describing the reaction between molecules. If the CRNs can compute the function f , so do the molecules in nature. We assume that the rate of each reaction is one because it doesn’t affect the output under the stable computation. In this thesis, we only consider one special type of CRNs called output oblivious CRN. These CRNs can concatenate to other CRNs directly. Chugg et al. [3] first define the CRN whose output species never being a reactant of reaction in CRN as output oblivious CRN. They have characterized all functions f : N^2 → N which can be stably computed by output oblivious CRNs with a leader. However, the CRNs they designed may require an extremely long time to converge to the correct output. We modify the original reactions and reduce the time needed for output oblivious CRN from O(N^r) to O(NlogN ).
謝詞 i
摘要 iii
abstract v
content vii
Chapter1 Introduction 1
Chapter2 Preliminaries 5
2.1 Kinetic model 9
Chapter3 Construction analysis 11
3.1 Partial affine function 12
3.2 Partial fissure functions 13
3.2.1 Base case 14
3.2.2 Z-producing reactions 16
3.2.3 Z-consuming reactions 17
3.2.4 Y-producing reactions 18
3.3 Stitching 20
Chapter4 Output oblivious CRNs which compute efficiently 25
4.1 Partial affine function 26
4.2 Partial fissure function 30
4.3 Stitching 36
Chapter5 Conclusion 43
Reference 45
Alistarh, Dan, Gelashvili, Rati, and M. Vojnović. Fast and exact majority in population protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 47–56, 2018.

A. Case, J. H. Lutz, and D. M. Stull. Reachability problems for continuous chemical reaction networks. In Natural Computing, volume 17, pages 223–230, 2018.

B. Chugg, H. Hashemi, and A. Condon. Output-oblivious stochastic chemical reaction networks. In J. Cao, F. Ellen, L. Rodrigues, and B. Ferreira, editors, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.

A. Dana, A. James, and E. David. Stably computable predicates are semilinear. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 292–299, 2006.

A. Dana, A. James, Eisenstat, David, and R. Eric. The computational power of population protocols. In Distributed Computing, volume 20, pages 279–304, 2007.

S. David, S. Georg, and W. Erik. DNA as a universal substrate for chemical kinetics. In Proceedings of the National Academy of Sciences, volume 107, pages 5393–5398,2010.

Gillespie and D. T. Exact stochastic simulation of coupled chemical reactions. In The journal of physical chemistry, volume 81, pages 2340–2361, 1997.

H. Hashemi, B. Chugg, and A. Condon. Composable computation in leaderless, discrete chemical reaction networks. In C. Geary and M. J. Patitz, editors, 26th International Conference on DNA Computing and Molecular Programming (DNA 26), volume 174 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:18. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.

C. Ho-Lin, D. Doty, and D. Soloveichik. Deterministic function computation with chemical reaction networks. In Natural computing, volume 13, pages 517–534. Springer, 2014.

C. Ho-Lin, D. Doty, and D. Soloveichik. Rate-independent computation in continuous chemical reaction networks. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 313–326, 2014.

E. E. Severson, D. Haley, and D. Doty. Composable computation in discrete chemical reaction networks. In P. Robinson and F. Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, page 14–23, 2019.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top