理论计算机科学

图灵机的艺术代表。图灵机用于建模一般计算设备。

理论计算机科学TCS )是一般计算机科学数学的子集,该子集的重点是计算机科学的数学方面,例如计算理论形式语言理论lambda colculus类型理论

很难精确地限制理论领域。 ACM算法和计算理论(SIGACT)的特殊兴趣小组提供了以下描述:

TCS涵盖了各种各样的主题,包括算法数据结构计算复杂性平行分布式计算,概率计算,量子计算自动机理论,信息理论,信息理论密码学语言验证算法游戏理论,机器学习,计算生物学计算生物学计算生物学,计算,计算经济学计算几何以及计算数理论代数。在这个领域的工作通常以其对数学技术和严格性的重视来区分。

历史

尽管以前存在逻辑推理和数学证据,但1931年,库尔特·戈德尔(KurtGödel)证明了他的不完整定理,表明可以证明或反驳哪些陈述存在基本限制。

克劳德·香农( Claude Shannon)以1948年的数学交流理论添加了信息理论。在同一十年中,唐纳德·赫布(Donald Hebb)引入了大脑中学习的数学模型。通过安装生物学数据,通过一些修改来支持这一假设,建立了神经网络平行分布处理的领域。 1971年,史蒂芬·库克(Stephen Cook)独立工作,莱昂尼德·莱文( Leonid Levin )证明了存在NP完整的实际相关问题,这是计算复杂性理论的里程碑。

随着20世纪初的量子力学的发展,可以在整个粒子波函数上进行数学操作的概念。换句话说,一个人可以同时在多个状态上计算功能。这导致了20世纪下半叶的量子计算机的概念,该量子在1990年代起飞时,彼得·谢尔(Peter Shor)表明,这种方法可用于在多项式时间内考虑大量数量,如果实施,这将渲染一些现代化RSA Insecure等公共密钥加密算法。

现代理论计算机科学研究基于这些基本发展,但包括许多其他数学和跨学科问题,如下所示:

p = np
数学逻辑自动机理论数字理论图理论计算理论计算复杂性理论
gnitirw-terces
密码学类型理论类别理论计算几何形状组合优化量子计算理论

主题

演算法

算法是用于计算的逐步过程。算法用于计算数据处理自动推理

算法是一种有效的方法,作为用于计算功能的明确指令的有限列表。从初始状态和初始输入(也许是空)开始,指令描述了一个计算,该计算在执行时,通过有限数量的连续数量有限的连续状态进行,最终产生“输出”并在最终结束状态下终止。从一个国家到下一个状态的过渡不一定是确定性的。某些算法(称为随机算法)包含随机输入。

自动机理论

自动机理论是对抽像机器自动机的研究,以及可以使用它们解决的计算问题。在离散数学数学计算机科学的一部分)下,它是理论计算机科学中的理论。自动机来自希腊语αὐτόματα的意思是“自我活性”。

自动机理论是对自动操作虚拟机的研究,以帮助对输入和输出过程的逻辑理解,而没有计算的中间阶段(或任何功能/过程)。

编码理论

编码理论是对代码属性及其对特定应用的适合度的研究。代码用于数据压缩密码学错误校正,最近也用于网络编码。代码由各种科学学科(例如信息理论电气工程数学计算机科学)进行研究,目的是设计高效可靠的数据传输方法。这通常涉及删除冗余以及传输数据中错误的校正(或检测)。

计算生物学

计算生物学涉及数据分析和理论方法,数学建模和计算模拟技术的开发和应用,以研究生物学,行为和社会系统。该领域是广泛定义的,包括计算机科学,应用数学动画统计生物化学化学,生物物理学分子生物学遗传学,基因组学,生态学进化解剖学神经科学可视化

计算生物学不同于生物计算,该计算是使用生物工程生物学来构建计算机的计算机科学和计算机工程的子场,但与生物信息学类似,这是一种使用计算机来存储和处理生物学数据的跨学科科学。

计算复杂性理论

计算复杂性理论计算理论的一个分支,它侧重于根据计算问题的固有难度对计算问题进行分类,并将这些相互关联。计算问题被理解为原则上可以通过计算机求解的任务,这相当于指出该问题可以通过机械应用数学步骤(例如算法)来解决。

如果其解决方案需要大量资源,无论使用什么算法,问题就会被认为本质上很难。该理论通过介绍计算数学模型来研究这些问题并量化解决这些问题所需的资源数量,例如时间和存储所需的资源数量来形式化这种直觉。还使用了其他复杂性度量,例如通信量(用于通信复杂性),电路中的数(用于电路复杂性)和处理器数量(并行计算中)。计算复杂性理论的作用之一是确定计算机可以和不能做什么的实际限制。

计算几何形状

计算几何形状是用于研究算法的计算机科学的一个分支,可以从几何形状上说明。计算几何算法的研究引起了一些纯粹的几何问题,并且这些问题也被认为是计算几何的一部分。

计算几何形状作为纪律发展的主要动力是计算机图形和计算机辅助设计和制造( CAD / CAM )的进步,但是计算几何学上的许多问题本质上都是经典的,并且可能来自数学可视化

计算几何形状的其他重要应用包括机器人技术(运动计划和可见性问题),地理​​信息系统(GIS)(几何位置和搜索,路线计划),集成电路设计(IC几何设计和验证),计算机辅助工程(CAE) (网格生成),计算机视觉(3D重建)。

计算学习理论

机器学习的理论结果主要涉及一种称为监督学习的归纳学习。在监督学习中,给出了一种以某种有用方式标记的算法。例如,样品可能是蘑菇的描述,标签可能是蘑菇是否可食用。该算法采集这些先前标记的样品,并使用它们诱导分类器。该分类器是一个将标签分配给样品的函数,包括算法以前从未见过的样品。监督学习算法的目的是优化某种措施,例如最大程度地减少新样本中犯的错误数量。

计算数理论

计算数理论,也称为算法数理论,是用于执行数字理论计算算法的研究。该领域最著名的问题是整数分解

密码学

密码学是对第三方(称为对手)在存在的情况下进行安全交流技术的实践和研究。更一般而言,它是关于构建和分析协议,以克服对手的影响,并且与信息安全性的各个方面有关,例如数据机密性数据完整性身份验证非纠正。现代密码学与数学计算机科学电气工程的学科相交。密码学的应用包括ATM卡计算机密码电子商务

现代密码学是基于数学理论和计算机科学实践的重大基础。加密算法是围绕计算硬度假设设计的,这使得任何对手都难以破坏这种算法。从理论上讲,破坏这样的系统是可能的,但是通过任何已知的实践手段这样做是不可行的。因此,这些方案在计算上被称为安全;理论进步,例如,整数分解算法的改进以及更快的计算技术需要不断调整这些解决方案。存在理论上的信息安全方案,即使使用无限的计算能力也无法折断,这是一次性键盘- 但这些方案比理论上最可损坏但在计算上安全的机制更难以实施。

数据结构

数据结构是一种在计算机中组织数据的特殊方式,因此可以有效地使用它。

不同种类的数据结构适用于不同类型的应用程序,有些则高度专门针对特定任务。例如,数据库使用b-Tree索引用于少数数据检索,并且编译器和数据库使用动态哈希表作为查找表。

数据结构提供了一种有效地管理大量数据的方法,例如大型数据库Internet索引服务。通常,有效的数据结构是设计有效算法的关键。一些正式的设计方法和编程语言强调数据结构而不是算法是软件设计中的关键组织因素。可以在存储在主内存辅助内存中的数据上进行存储和检索。

分布式计算

分布式计算研究分布式系统。分布式系统是一个软件系统,在该软件系统中,位于网络计算机上的组件通过传递消息来通信并协调其操作。组件相互交互,以实现共同的目标。分布式系统的三个重要特征是:组件的并发,缺乏全球时钟以及组件的独立失败。分布式系统的示例从基于SOA的系统大量多人在线游戏点对点应用程序以及比特币等区块炼网络不等。

在分布式系统中运行的计算机程序称为分布式程序,分布式编程是编写此类程序的过程。消息传递机制有许多替代方法,包括类似RPC的连接器和消息队列。分布式系统的重要目标和挑战是位置透明度

基于信息的复杂性

基于信息的复杂性(IBC)研究了连续问题的最佳算法和计算复杂性。 IBC研究了连续问题,作为路径积分,部分微分方程,普通微分方程的系统,非线性方程,积分方程,固定点和非常高维的集成。

正式方法

正式方法是一种基于数学的特定技术,用于软件硬件系统的规范,开发和验证。将正式方法用于软件和硬件设计的动机是由于在其他工程学科中,进行适当的数学分析可以有助于设计的可靠性和鲁棒性。

正式方法最好被描述为相当广泛的理论计算机科学基础知识的应用,尤其是逻辑计算,形式语言自动机理论程序语义,但也将系统代数数据类型键入软件和硬件规范中的问题和代数数据类型确认。

信息理论

信息理论是涉及信息量化的应用数学电气工程计算机科学的分支。信息理论是由Claude E. Shannon开发的,目的是找到有关信号处理操作(例如压缩数据以及可靠地存储通信数据)的基本限制。自成立以来,它已经扩大到在许多其他领域找到应用,包括统计推断自然语言处理密码学神经生物学,分子代码的进化和功能,统计中的模型选择,热物理学,量子计算语言学,语言学,窃,窃,窃,检测,窃,检测,pla窃,pla窃,窃,pla窃,窃,模式识别异常检测和其他形式的数据分析

信息理论的基本主题的应用包括无损数据压缩(例如zip文件),有损耗的数据压缩(例如MP3JPEG )以及通道编码(例如,数字用户线(DSL) )。该领域是在数学统计计算机科学物理神经生物学电气工程的交集。它的影响对于旅行者任务深空成功至关重要还有许多其他领域。信息理论的重要子场是源编码渠道编码算法复杂性理论算法信息理论信息理论安全和信息衡量标准。

机器学习

机器学习是一门科学学科,涉及可以从数据中学习的算法的构建和研究。这种算法是通过基于输入的模型来构建模型并使用该算法来做出预测或决策的,而不是仅遵循明确编程的指令。

机器学习可以视为计算机科学和统计的子场。它与人工智能优化有着密切的联系,该领域将方法,理论和应用领域传达给了该领域。机器学习用于一系列计算任务,在这些任务中,设计和编程明确,基于规则的算法是不可行的。示例应用程序包括垃圾邮件过滤光学角色识别(OCR),搜索引擎计算机视觉。机器学习有时与数据挖掘相结合,尽管这更多地侧重于探索性数据分析。机器学习和模式识别“可以看作是同一领域的两个方面”。

平行计算

并行计算是一种同时进行许多计算的计算形式,其原理是可以将大问题分为较小的计算,然后将其“并行”求解。并行计算有几种不同形式:比特级指令级别数据任务并行性。并行性已经运用了多年,主要是在高性能计算中,但是由于物理限制阻止了频率缩放,对其的兴趣已增长。近年来,随着计算机的功耗(并因此产生的热量产生)已成为一个关注,并行计算已成为计算机架构中的主要范式,主要是以多核处理器的形式。

并行计算机程序比顺序更难编写,因为并发引入了几类潜在的软件错误,其中最常见的是种族条件。不同子任务之间的沟通同步通常是获得良好并行程序性能的最大障碍。

并行化导致单个程序的最大速度称为Amdahl定律

编程语言理论和程序语义

编程语言理论是计算机科学的一个分支,涉及编程语言及其个人特征的设计,实现,分析,表征和分类。它属于理论计算机科学的学科,这取决于和影响数学,软件工程和语言学。这是一个活跃的研究领域,拥有许多专门的学术期刊。

编程语言理论中,语义是与对编程语言含义的严格数学研究有关的领域。它通过评估由特定编程语言定义的句法法律字符串含义,以显示所涉及的计算。在这种情况下,评估将是句法非法字符串,结果将是无效的。语义描述了计算机用该特定语言执行程序时所遵循的过程。可以通过描述程序的输入和输出之间的关系,或者对程序将如何在某个平台上执行的说明,从而创建计算模型

量子计算

量子计算机是一种计算系统,它可以直接使用量子力学现象(例如叠加纠缠)来对数据进行操作。量子计算机与基于晶体管的数字计算机不同。数字计算机需要将数据编码为二进制数字(),而每个数字始终在两个确定的状态之一(0或1)之一中,而量子计算则使用量子位(量子位)(量子位) ,这可以在状态的叠​​加中。理论模型是量子图灵机,也称为通用量子计算机。量子计算机与非确定性概率计算机共享理论相似性;一个例子是能够同时处于多个状态的能力。量子计算领域是由Yuri Manin于1980年首次引入的, Richard Feynman1982年首先引入。

截至2014年,量子计算仍处于起步阶段,但已经进行了实验,在该量子数量上进行了量子计算操作。实际研究和理论研究都在继续,许多国家政府和军事资助机构都支持量子计算研究,以开发用于平民和国家安全目的(例如密码分析)的量子计算机

符号计算

计算机代数,也称为符号计算或代数计算是一个科学领域,它指的是用于操纵数学表达式和其他数学对象算法软件的研究和开发。尽管正确地说,计算机代数应该是科学计算的子场,但通常被认为是不同的字段,因为科学计算通常基于具有近似浮点数的数值计算,而符号计算则强调了包含不含变量的表达式的精确计算任何给定值,因此被操纵为符号(因此,符号计算的名称)。

执行符号计算的软件应用程序称为计算机代数系统,术语系统提到了主要应用程序的复杂性,至少包括一种在计算机中表示数学数据的方法,是用户编程语言(通常与该语言不同用于实现),专用内存管理器,用于数学表达式输入/输出的用户界面,执行常规操作的大量例程,例如表达式简化,使用链条规则差异化多项式分解不确定集成等等。

非常大规模的集成

非常大规模的集成VLSI )是通过将数千个晶体管组合为单个芯片来创建集成电路(IC)的过程。 VLSI始于1970年代,当时正在开发复杂的半导体通信技术。微处理器是VLSI设备。在引入VLSI技术之前,大多数IC都可以执行一套有限的功能。电子电路可能由CPUROMRAM和其他胶水逻辑组成。 VLSI允许IC制造商将所有这些电路添加到一个芯片中。

组织

期刊和新闻通讯

会议

也可以看看