理論計算機科學


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




目录





  • 1 定义和范围


  • 2 历史


  • 3 参考文献


  • 4 外部链接


  • 5 参见




定义和范围


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


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





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



























P→Qdisplaystyle Prightarrow Q,Prightarrow Q,

DFAexample.svg
Elliptic curve simple.png
6n-graf.svg

数理逻辑

自动机

数论

图论

Wang tiles.png
P = NP ?

GNITIRW-TERCES

Γ⊢x:Intdisplaystyle Gamma vdash x:IntGamma vdash x:Int

可计算性理论

計算複雜性理論

密码学

类型理论

Commutative diagram for morphism.svg
SimplexRangeSearching.png
TSP Deutschland 3.png
Blochsphere.svg

范畴论

计算几何

组合优化

量子计算


历史


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


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


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


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



参考文献




  1. ^ Theoretical Computer Science， Elsevier Journal. [2010-07-28]. 


  2. ^ SIGACT. [2010-07-27]. 


  3. ^ ToCT. [2010-07-27]. （原始内容存档于2010-11-04）. 



外部链接



  • （英文） SIGACT


  • （英文） Usenet comp.theory 新闻组[永久失效連結]


参见



  • 计算机科学

  • 计算机协会（ACM）


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





































  • 查

  • 论

  • 编



電腦科學的主要领域

注：该模板大致遵循ACM-2012计算分类系统。
电脑硬件

  • 印刷电路板

  • 外部设备

  • 集成电路

  • 超大规模集成电路

  • 绿色计算

  • 電子設計自動化


系统架构组织

  • 電腦系統架構

  • 嵌入式系统

  • 实时计算

网络

  • 网络传输协议

  • 路由

  • 网络拓扑

  • 网络服务

软件组织

  • 直譯器

  • 中间件

  • 虛擬機器

  • 操作系统

  • 软件质量


软件符号和工具

  • 编程范型

  • 编程语言

  • 編譯器

  • 领域特定语言

  • 軟體框架

  • 集成开发环境

  • 软件配置管理

  • 函式庫

软件开发

  • 软件开发过程

  • 需求分析

  • 软件设计

  • 软件部署

  • 軟體維護

  • 开源模式

计算理论

  • 自动机

  • 可计算性理论

  • 计算复杂性理论

  • 量子计算

  • 数值计算方法

  • 计算机逻辑

  • 形式语义学

算法

  • 算法分析

  • 算法设计

  • 随机化算法

  • 计算几何

计算数学

  • 离散数学

  • 概率

  • 统计学

  • 数学软件

  • 数理逻辑

  • 集合论

  • 数论

  • 图论

  • 类型论

  • 范畴论

  • 信息论

  • 数值分析

  • 数学分析

信息系统

  • 数据库管理系统

  • 電腦數據

  • 企业信息系统（英语：Enterprise information system）

  • 社会性软件

  • 地理信息系统

  • 决策支持系统

  • 过程控制

  • 数据挖掘

  • 數位圖書館

  • 系统平台

  • 數位行銷

  • 万维网

  • 信息檢索

安全

  • 密码学

  • 形式化方法

  • 入侵检测系统

  • 网络安全

  • 信息安全

人机交互

  • 计算机辅助功能

  • 用户界面

  • 可穿戴计算机

  • 普适计算

  • 虚拟现实

  • 聊天機器人

并发性

  • 并发计算

  • 并行计算

  • 分布式计算

  • 多线程

  • 多元處理

人工智能

  • 自动推理

  • 计算语言学

  • 计算机视觉

  • 进化计算

  • 专家系统

  • 自然语言处理

  • 机器人学

机器学习

  • 監督式學習

  • 非監督式學習

  • 强化学习

  • 交叉驗證

计算机图形学

  • 计算机动画

  • 可视化

  • 渲染

  • 修飾照片

  • 圖形處理器

  • 混合现实

  • 虚拟现实

  • 图像处理

  • 图像压缩

  • 实体造型

应用计算

  • 电子商务

  • 企业级软件

  • 计算数学

  • 计算物理学

  • 计算化学

  • 计算生物学

  • 計算社會科學

  • 医学信息学

  • 数字艺术

  • 電子出版

  • 網絡戰

  • 电子游戏

  • 文字处理器

  • 運籌學

  • 教育技术学

  • 生物信息学

  • 认知科学

  • 文件管理系统（英语：Document management system）



  • 分类分类


  • 主题主题


  • 专题专题


  • 共享资源页面维基共享



规范控制

  • GND: 4196735-5

-

Popular posts from this blog

【情報】本週珍珠商品重點：煉金時裝 + 艾港勞工宿舍！！

Image
(function(w,d,s,l,i))(window,document,'script','dataLayer','GTM-KDKMGT'); (function(d, s, id) var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/zh_TW/all.js#xfbml=1&appId=668497826514848"; fjs.parentNode.insertBefore(js, fjs); (document, 'script', 'facebook-jssdk')); var hotKeywords = ["u4e16u754cu738b","u4ebau53c3","u4ebau8518","u99ac","u65b0u624b","u8cbfu6613","u885du88dd","u8077u696d","u91e3u9b5a","u5de1u6797u8005","u6c34u6676","u5de1u6797","u758au5c64","u5361u666e","u6d77u602a"]; var useOldSearch = 0; var googlecseLoad = function() var cx = '001994533065495648396:c3salsx3fty'; var gcse = document.createElement('script'); gcse.type = 'text/javascript'; gcse.asyn
Read more

京昆高速公路

Image
坐标： 35°01′30″N 109°57′59″E  /  35.0249599°N 109.9665°E  / 35.0249599; 109.9665 国家高速G5 北京－昆明高速公路 路線簡稱 京昆高速 起點 北京 終點 云南昆明 建设规划 規劃總里程 2716公里 参见 中华人民共和国高速公路 中国国家高速公路网 北京－昆明高速公路 ，简称 京昆高速 （中国国家高速公路网编号 G5 ），北起北京，南抵云南昆明，途经北京、河北、山西、陕西、四川、云南6省市区，贯穿南北东西，全长约2716公里。 [1] 途经主要地区有北京－保定－石家庄－阳泉－太原－晋中－临汾－运城－渭南－西安－汉中－广元－绵阳－德阳－成都－雅安－凉山州－攀枝花－楚雄州－昆明。 目录 1 路段 2 各省过境节点与过境里程 3 沿线出入口及服务区 4 来源 5 参见 路段 中华人民共和国交通运输部已启动全国高速公路统一命名和编号工作，纳入国道主干线的高速公路将逐步使用新名称替换旧名称，下面列出其具体走向的旧名，以资参考。 北京段：全通。 河北段：京界—石家庄曲阳桥段已通，曲阳桥—山西段石太二通道已通。 山西段：全通。 陕西段：全通。 四川段：全通。 云南段：全通。 各省过境节点与过境里程 京昆高速公路过境里程 （公里） [2] 省级行政区 过境里程数 起点 起点里程数 终点（省界点） 终点里程数 北京 60 北京 0 京冀界 60 河北 274.766 冀京界 60 井陉（冀晋界） 334.766 山西 503.458 旧关（晋冀界） 335 禹门口（晋陕界） 838.458 陕西 624.451 禹门口（陕晋界） 839 棋盘关（陕川界） 1463.451 四川 1038.205 棋盘关（川陕界） 1464 永仁方山（川滇界） 2502.205 云南 213 四川田房（滇川界） 2503 昆明 2716 途径省份 里程 起点地名 终点地名 北京 40.000 北京 京冀界 河北 30.000 冀京界 涞水 135.566 涞水 保定石家庄交界 61.200 保定石家庄交界 鹿泉 48.000 鹿泉 井陉(冀晋界) 山西 141.460 旧关(晋冀界) 武宿(东山枢纽) 16.000 武宿(东山枢纽) 罗城(枢纽) 33.165 罗城(枢纽) 夏家营(义望枢纽) 23
Read more

【攻略】陳戈-謝勒汗智慧的古書 (完成)

Image
(function(w,d,s,l,i);w[l].push('gtm.start': new Date().getTime(),event:'gtm.js');var f=d.getElementsByTagName(s)[0], j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src= '//www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f); )(window,document,'script','dataLayer','GTM-KDKMGT'); (function(d, s, id) var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/zh_TW/all.js#xfbml=1&appId=668497826514848"; fjs.parentNode.insertBefore(js, fjs); (document, 'script', 'facebook-jssdk')); var hotKeywords = ["u4e16u754cu738b","u4ebau53c3","u99ac","u4ebau8518","u65b0u624b","u885du88dd","u8cbfu6613","u5de1u6797u8005","u8077u696d","u5de1u6797","u91e3u9b5a","
Read more