三个世界理论 (信息学)
在資訊学（尤其在计算机科学、数据库理论）中的“三个世界”理论中，“三个世界”指现实世界、資訊世界和机器世界（即电脑世界），概括了将现实世界中客观存在的事物（一些事实与事件）转化成为数据库存储中的数学模型的三个过程。独立存在于人们头脑外、客观存在的事物归属现实世界；当人们把这些客观事物收入头脑后，予以整理，对其简化、抽象化后，选出事物、事件较具代表性质的属性，这便成为信息世界的实体；最后通过各种媒体（特别指电子计算机存储器），将这些属性整…
标签：#理论计算机科学
共 39 篇文章
布鲁克斯定理
图论中，布鲁克定理（） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。 背景 图染色数 考慮為G的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图G中任意两个顶点u,v，如果uv\in E(G)，那么u,v所染成的颜色不同。 对于图G，如果存在一个k种颜色的恰当染色方案，…
阈值定理
在量子计算中，阈值定理（或称量子容错定理）指出，如果量子计算机的物理错误率低于某个特定阈值，通过应用量子纠错机制，可以将逻辑错误率抑制到任意低的水平。这表明量子计算机可以实现容错计算，类似于冯·诺伊曼（）关于经典计算的阈值定理 。这一结果由多里特·阿哈罗诺夫（）和迈克尔·本-奥尔（）的研究小组； 伊曼纽尔·克尼尔（）、雷蒙德·拉弗拉姆（）和沃伊切赫·祖瑞克（）； 以及阿列克谢·基塔耶夫（） 等人独立证明。 这些成果建立在彼得·肖尔（）的…
Π演算
在理论计算机科学中，π演算（或）是一种进程演算模型。 π演算允许通过通道本身传递通道名称。得益于此，它可以描述计算过程中网络拓扑可能发生变化的并发计算系统。 π演算语法简单，但表达能力很强（参见）。函数式程序可以被表示成π演算，这种表示强调了计算的对话本质，并与博弈语义建立了联系。π演算的扩展形式，如spi演算和应用π演算（applied π），在分析和推理方面获得了成功。除了用于描述并发系统的最初用途外，π演算也被用于推理、分子生物学…
量子演算法
量子演算法（Quantum algorithm；量子算法）是在量子計算中，於量子計算的現實模型上運行的演算法，最常用的模型是量子線路的計算模型。經典（或非量子）演算法是有限的指令序列，或用於解決問題的分步驟過程，其中每個步驟或指令都可以在經典計算機上執行。同樣地量子演算法是一個循序漸進的過程，其中每個步驟都可以在量子計算機上執行。儘管所有經典演算法也可以在量子計算機上執行，量子演算法一詞通常用於那些看起來本質上是量子的演算法，或者使用量…
最小平方頻譜分析法
最小平方頻譜分析法（）是一種利用最小平方法尋找適配於資料點之最佳正弦曲線，以估算頻譜的方法。其數學原理與科學界中最常用的傅立葉分析相似。 最小平方頻譜分析法也稱為凡尼切克法（Vaníček method）、隆布法（Lomb method）或隆布—史卡構法（Lomb–Scargle method），分別取名自對其有所貢獻的、尼可拉斯·隆布（Nicholas R. Lomb）。然而，大多數以上述理論為基礎開發的方法僅適用於取樣間距相等的訊號…
DNA運算
DNA计算（DNA computing，或譯DNA運算）是一个新出現的交叉學門領域，利用DNA、生物化学以及分子生物学原理，而非传统上以硅為基礎的电子计算技術。该领域涉及DNA计算的理论、实验和应用。虽然该领域最初始于 1994 年Len Adleman的计算应用演示，但现在已扩展到存储技术开发等其他几个方面、纳米级成像模式、合成控制器与反应网络、等。 历史 DNA运算最先由南加州大学的伦纳德·阿德曼在1994年实现。Adleman演示…
算法
-{zh-hans:]];zh-hant:]]}- 算法（），在数学（算学）和计算机科学中指一个被定义好的、计算机可施行其指示的有限步骤或次序，常用于计算、数据处理和自动推理。算法可以使用条件语句通过各种途径转移代码执行（称为自动决策），并推导出有效的推论（称为自动推理），最终实现自动化。 相反，启发式是一种解决问题的方法，可能没有完全指定，也可能不能保证正确或最优的结果，尤其是在没有明确定义的正确或最优结果的问题领域。例如，社交媒体推…
量子機器學習
量子机器学习，是将量子算法整合到机器学习程序中。该术语最常见的用法是指用于分析量子计算机上执行的经典数据的机器学习算法，即量子增强机器学习。常规机器学习算法被用来计算海量数据，而量子机器学习利用量子位和量子運算或专门的量子系统来提高算法在程序中完成的计算速度和数据存储。在实际操作中，量子机器学习会混合常规机器学习，先用常规计算机执行机器学习程序，然后将无法通过常规计算机完成的子程序交由量子计算机完成。這些子程序可能比較複雜，在量子計算機…
通粹纠缠度 (量子计算)
在量子信息科学中，通粹纠缠度是一种涉及量子比特的状态不变量，用来度量纠缠度。 定义 通粹纠缠度是一种纠缠单调函数（一种测量纠缠的方法），针对两个量子比特的混合状态定义为： : \mathcal{C}(\rho)\equiv\max(0,\lambda_1-\lambda_2-\lambda_3-\lambda_4) 其中\lambda_1,...,\lambda_4是如下 Hermitian 矩阵的特征值（按降序排列） : R = \s…
量子计算机
乃一種對於二階量子系統之純態空間的幾何表示法，是建立量子電腦的基礎。]] 量子计算机（）是以量子力学为基础搭建、用于進行通用計算的設備。量子计算机使用量子比特来儲存數據，使用量子演算法操作數據。不同于电子计算机的比特只能处于0或1两种状态之一，量子比特可以处于这两个基态之间的叠加态，也就是说，它可以以一种抽象意义上的“中间状态”同时表现出两种基态的特性（即同时为0和1）。当对量子比特进行测量时，结果是一个经典比特的概率性输出。如果量子计…
自动推理
自动推理（）是计算机科学和数理逻辑的一个交叉领域，致力于理解推理的不同方面。自动推理的研究有助于开发能够让计算机完全或近乎完全自动地进行推理的计算机程序。虽然自动推理被视为人工智能的一个子领域，但它也与理论计算机科学和哲学有密切联系。 自动推理中发展最成熟的子领域包括自动定理证明（以及交互式定理证明）和。在类比推理、归纳推理和溯因推理方面也有大量研究工作。其他重要主题包括不确定性推理和非单调逻辑推理。自动推理的工具和技术包括经典逻辑和演…
最近公共祖先 (图论)
在图论和计算机科学中，最近公共祖先（）是指在一个树或者有向无环图中同时拥有和作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果是的后代，那么就是和的最近公共祖先。 最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w…
惠特尼连通性定理
图论中，惠特尼连通性定理（），简称惠特尼定理（），是美國數學家哈斯勒·惠特尼于1932年提出的关于2连通图等价性质的定理，该定理提供了关于2连通图的不同点对之间的连通性质刻画，描述了2连通图的特殊性质。 定理陈述 对一个图G，若G至少存在3个点，则G是2连通的当且仅当对G中任意两个点u, v，G中至少存在连接u, v的2条内部不相交路径，即除首尾相同（皆為u, v）外，沒有其他公共頂點的路徑。 定理证明 必要性 因为任意两点之间均存在路…
递归 (计算机科学)
遞迴（）在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。 遞迴式方法可以被用於解決很多的電腦科學問題，因此它是電腦科學中十分重要的一個概念。 絕大多數程式語言支援函式的自呼叫，在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈，因此有很多在函數程式語言（如Scheme）中用递归来取代循环的例子。 電腦科學家尼克勞斯·維爾特如此描述遞迴： 遞迴程式 java public void…
惠特尼不等式
在图论中，惠特尼不等式 (英：Whitney's connectivity inequalities or Whitney's inequalities)，又称为惠特尼连通性不等式，是关于图的连通度的重要不等式，几乎出现于任何一本图论教科书中。该不等式明确地指出了图的点连通度与边连通度以及与图最小度之间的大小关系。但目前关于该定理的提出者是否是哈斯勒·惠特尼还没有统一定论。 叙述 对于任何一个非平凡图G，均满足 \kappa(G)\le…
形式语言
在数学、逻辑和计算机科学中，形式语言（）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面：语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。 语言的形式定义 字母表与字符串 语言定义在某一个特定的字母表上，字母表（经常记作 Σ ）可以为任意…
数据结构
是数据结构的一种类型]] 在计算机科学中，数据结构（）是计算机中存储、组织数据的方式。 数据结构意味着介面或封装：一个数据结构可被视为两个函数之间的介面，或者是由数据类型联合组成的存储内容的访问方法封装。 大多数数据结构都由数列、记录、可辨识联合、引用等基本类型构成。举例而言，可為空的引用（nullable reference）是引用与可辨识联合的结合体，而最简单的链式结构链表则是由记录与可空引用构成。 数据结构可透过编程语言所提供的数…
生产者消费者问题
生产者消费者问题（），也称有限缓冲问题（），是一个多进程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两个进程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。 要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据…
伪随机性
伪随机性（）是一个过程似乎是随机的，但实际上并不是。例如伪随机数是使用一个确定性的算法计算出来的似乎是随机的数序，因此伪随机数实际上并不随机。在计算伪随机数时假如使用的开始值不变的话，那么伪随机数的数序也不变。伪随机数的随机性可以用它的统计特性来衡量，其主要特征是每个数出现的可能性和它出现时与数序中其它数的关系。伪随机数的优点是它的计算比较简单，而且只使用少数数值很难推算出计算它的算法。一般人们使用一个假的随机数，比如電腦上的時間作为计…