理論計算機科學

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP




理论计算机科学（英语：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
Clash Royale CLAN TAG #URR8PPP body.skin-minerva .mw-parser-output table.infobox captiontext-align:center 倭马亚王朝 بنو أمية ‎ 661年－750年 国旗 倭马亚哈里发国的版图 首都 大马士革（661-744） 哈兰（744-750） 常用语言 阿拉伯语（官方），亚拉姆语，亚美尼亚语，柏柏尔语族，非洲罗曼语，科普特语，格鲁吉亚语，希腊语，希伯来语，突厥语族，库尔德语 [1] ，波斯语，莫札拉布语 宗教 伊斯兰教逊尼派 政府 君主制 哈里发   • 661年–680年 穆阿威叶一世 • 744年–750年 马尔万二世 历史   • 穆阿威叶哈里发 661年 • 阿拔斯家族战胜并杀死马尔万二世，王朝灭亡 750年 面积 750年 13,400,000 km 2 人口 • 750年 34000000 货币 倭马亚第纳尔 先前国 继承国 四大哈里发 拜占庭帝国 西哥特王国 阿拔斯王朝 后倭马亚王朝 大伊朗地區歷史 現代國家興起前 現代之前 伊斯蘭之前 俾什达迪王朝 神话时期 凯扬王朝 （ 英语 ： Kayanian dynasty ） 神话时期 史前 （ 英语 ： Prehistoric Iran ） 埃蘭文明 前3200年－前2800年 埃蘭王朝 前2800年－前550年 吉罗夫特文化 （ 英语 ： Jiroft culture ） 卢卢比人 （ 英语 ： Lullubi ） 古提人 塞尔提亚人 （ 英语 ： Cyrtian ） 科杜内 （ 英语 ： Corduene ） 巴克特里亞-馬爾吉阿納 前2200年－前1700年 馬納王國 前10–前7世紀 米底王國 前728年－前550年 斯基泰王国 前652年–前625年 阿契美尼德王朝 前550年－前330年 塞琉古帝國 前330年－前150年 希腊-巴克特里亚王国 前250年－前125年 帕提亞帝國 前224年－公元248年 公元后 貴霜帝國 30–275年 薩珊王朝 224–651年 阿夫里格王朝 305–995年 嚈噠帝國 425–557年 喀布爾-夏希王朝 565–879年 达不义德王朝 （ 英语 ： Dabu
Read more

Gabbro

Image
Clash Royale CLAN TAG #URR8PPP A coarse-grained mafic intrusive rock Gabbro Photomicrograph of a thin section of gabbro Gabbro ( / ˈ ɡ æ b r oʊ / ) is a phaneritic (coarse-grained), mafic intrusive igneous rock formed from the slow cooling of magnesium-rich and iron-rich magma into a holocrystalline mass deep beneath the Earth's surface. Slow-cooling, coarse-grained gabbro is chemically equivalent to rapid-cooling, fine-grained basalt. Much of the Earth's oceanic crust is made of gabbro, formed at mid-ocean ridges. Gabbro is also found as plutons associated with continental volcanism. Due to its variant nature, the term "gabbro" may be applied loosely to a wide range of intrusive rocks, many of which are merely "gabbroic". Contents 1 Etymology 2 Petrology 3 Distribution 4 Uses 5 See also 6 References 7 External links Etymology The term "gabbro" was used in the 1760s to name a set of rock types that were found in the ophiolites of the Apenn
Read more

托萊多 (西班牙)

Image
Clash Royale CLAN TAG #URR8PPP body.skin-minerva .mw-parser-output table.infobox captiontext-align:center 托萊多 城市 Toledo 托莱多的夕照景色——左邊的托莱多城堡和右邊的托莱多主教座堂在天際線中顯眼 旗幟 徽章 托萊多 坐标： 39°51′24″N 4°1′28″W  /  39.85667°N 4.02444°W  / 39.85667; -4.02444 坐标： 39°51′24″N 4°1′28″W  /  39.85667°N 4.02444°W  / 39.85667; -4.02444 國家   西班牙 西班牙 自治區   卡斯蒂利亚-拉曼恰 省 托萊多省 地区 托萊多 司法辖区 托萊多 聚居 約前7世紀 政府  • 市长 Emiliano García-Page Sánchez （PSOE） 面积  • 陸地 232.1 平方公里（89.6 平方英里） 海拔 529 米（1,736 英尺） 人口 （2015年）INE  • 總計 83,226  • 密度 35,904/平方公里（92,990/平方英里） 邮编 45001-45009 電話區號 +34 網站 http://www.ayto-toledo.org/ 托莱多 （西班牙語： Toledo ， 西班牙語： [toˈleðo] ），又稱 杜麗多 ，是西班牙中部的一个自治市，位于马德里西南约70公里。托莱多是托莱多省的首府，也是其所在的卡斯蒂利亚-拉曼恰自治区的首府。该市2017年人口83,741人 [1] 。 托莱多始於羅馬時期，在腓力二世前為卡斯蒂利亞王國（後西班牙王國）首都。它因其保存完好的基督教、伊斯兰教和犹太教建筑而在1986年被评为世界文化遺產，有哥德式、摩爾式、巴洛克式和新古典式各類教堂、寺院、修道院、王宮、城牆、博物館等古建築70多處。 目录 1 纹章 2 歷史事件 3 地理 4 气候 5 著名景点 6 友好城市 7 著名人物 8 图集 9 参考文献 10 外部連結 纹章 托莱多纹章 托莱多的纹章据称是由查理五世授予的。纹章由带着盾徽的黑色的帝国双头鹰组成。盾徽是卡斯蒂利亚-莱昂的纹章，下面有石榴图案。盾徽被金羊毛勋章垂饰所环绕。双头
Read more