# 理論電腦科學

## 運算理論

• 唔同種類嘅理論性運算機械喺解難能力上有乜嘢差異（自動機理論；automata theory）；
• 有啲乜嘢問題係能夠或者唔能夠用運算機械解嘅（可運算性理論；computability theory）；以及
• 一個運算上嘅問題最高嘅可能解決效率（運算複雜性理論；computational complexity theory）

... 等等嘅問題[1][2]

def g(): # 定義 g
if halts(g): # 如果 halt(g) 係真...
loop_forever() # 做永遠唔停嘅 loop


 P = NP? 自動機理論 可運算性理論 運算複雜性理論 演算法 量子電腦

## 資訊理論

 ${\displaystyle S=-\sum _{i}p_{i}\log _{2}(p_{i})}$ ${\displaystyle \mathbb {E} _{X,Y}[SI(x,y)]}$ 資訊熵 相互資訊

## 攷

1. Sipser, M. (2006). Introduction to the Theory of Computation (Vol. 2). Boston: Thomson Course Technology.
2. Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the Theory of Computation. Prentice Hall PTR.
3. Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (58): 345–363.
4. Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), pp 230–265.
5. Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
6. Black, Paul E. (15 December 2004). "Data structure". In Pieterse, Vreda; Black, Paul E. (eds.). Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology.
7. Peter Brass, Advanced Data Structures, Cambridge University Press, (2008).
8. Demystifying Entropy. Towards Data Science.
9. Delgado-Bonal, Alfonso; Martín-Torres, Javier (2016-11-03). "Human vision is determined based on information theory". Scientific Reports. 6 (1).
10. Huelsenbeck, J. P.; Ronquist, F.; Nielsen, R.; Bollback, J. P. (2001). "Bayesian inference of phylogeny and its impact on evolutionary biology". Science. 294 (5550): 2310–2314.
11. Phillip A. Laplante, 2010. Encyclopedia of Software Engineering Three-Volume Set (Print). CRC Press. p. 309.
12. Hall, A. (1990). Seven myths of formal methods. IEEE software, 7(5), 11-19.