理論計算機科學

维基百科,自由的百科全书
跳转至: 导航搜索

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

定义和范围[编辑]

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

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

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

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

 P \rightarrow Q \, DFAexample.svg Elliptic curve simple.png 6n-graf.svg
数理逻辑 自动机 数论 图论
Wang tiles.png P = NP ? GNITIRW-TERCES \Gamma\vdash x : Int
可计算性理论 計算複雜性理論 密码学 类型理论
Commutative diagram for morphism.svg SimplexRangeSearching.png Blochsphere.svg
范畴论 计算几何 量子计算

历史[编辑]

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

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

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

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

参考文献[编辑]

  1. ^ Theoretical Computer Science, Elsevier Journal. [2010-07-28]. 
  2. ^ SIGACT. [2010-07-27]. 
  3. ^ ToCT. [2010-07-27]. 

外部链接[编辑]

参见[编辑]