理论计算机科学

理论计算机科学（英语：Theoretical computer science，缩写为TCS）是计算机科学的一个分支，它主要研究有关计算的相对更抽象化，逻辑化和数学化的问题，例如计算理论，算法分析，以及程序设计语言的语义。尽管理论计算机科学本身并非一个单独的研究主题，从事这个领域的研究人员在电脑科学的研究者里自成一派。

定义和范围

根据Elesevier出版社《理论电脑科学杂志》（Theoretical Computer Science）的解释^[1]，理论电脑科学有着数学和抽象的本质，但动机来自实践和日常中的计算问题。它旨在理解计算的本质，并根据这种理解提供更有效率的方法。

精确地限制定义理论计算机科学的范围并非易事；根据计算机协会(ACM)算法与计算理论兴趣组（SIGACT）的表述：^[2]

“

理论计算机科学的领域广泛包含算法、数据结构、计算复杂性、分布式计算、并行计算、VLSI、机器学习、计算几何、信息论、密码学、量子计算、计算数论、符号计算、程序语义和形式化方法，自动机理论，以及随机方面的研究。此领域的研究常需要强调严格的数学。

”

计算机协会（ACM）《计算理论学报》（Transactions on Computation Theory）^[3]又为以上的列表添加了：编码理论，计算学习理论，以及与数据库、信息获取、经济学模型和计算机网络中与理论计算机科学相关的方面。

${\displaystyle P\rightarrow Q\,}$
数理逻辑	自动机理论	数论	图论
	P = NP ?	GNITIRW-TERCES	${\displaystyle \Gamma \vdash x:Int}$
可计算性理论	计算复杂性理论	密码学	类型理论
范畴论	计算几何	组合优化	量子计算

历史

尽管形式化算法已经存在了数千年，例如求最大公因数的欧几里得算法至今依然在为人们所使用，但直到1936年，艾伦·图灵，阿隆佐·邱奇和斯蒂芬·科尔·克莱尼才给出了算法在计算理论中的形式化定义。早在1703年之前就有了二进制和数理逻辑系统，莱布尼茨建立了真假二元的形式逻辑。1931年，哥德尔证明了哥德尔不完备定理，该定理指出，任何相容的形式体系不能用于证明它本身的相容性。

这些成果引领了理论计算机科学，包括现代数理逻辑和可计算性等的研究。1948年，信息论由香农将信息的传递作为一种统计现象而引入。同样在1940年代，Donald Hebb建立了一套大脑学习模式的数学模型，神经网络和平行分布式处理等学科也建立了起来。

随着20世纪初量子力学的发展，数学运算的概念被引入了粒子波函数，可以同时计算多重状态上的函数。这一概念引领了20世纪后半叶量子计算机概念的产生，在1990年代彼得·秀尔（Peter Shor）提出量子质因数分解算法，可以在多项式时间内分解大数，如果得以实现，现代的公开密钥加密系统将变得不安全。

现代理论计算机科学研究在以上的基础上展开，同时也包含了其它数学和跨学科的问题。

参考文献

1. Theoretical Computer Science， Elsevier Journal. [2010-07-28]. （原始内容存档于2011-10-29）.
2. SIGACT. [2010-07-27]. （原始内容存档于2010-03-12）.
3. ToCT. [2010-07-27]. （原始内容存档于2010-11-04）.

外部链接

• （英文） SIGACT （页面存档备份，存于互联网档案馆）
• （英文） Usenet comp.theory 新闻组^{[永久失效链接]}

参见

• 计算机科学主题

• 计算机科学
• 计算机协会（ACM）
• 欧洲理论计算机科学协会（European Association for Theoretical Computer Science）