比浏览器更快的访问！
38 关系: 劍橋大學出版社，博弈论，卡普的二十一個NP-完全問題，可计算性理论，史蒂芬·库克，启发法，复杂性类，大O符号，密码学，中央处理器，布尔可满足性问题，布尔函数，并行计算，交互式证明系统，二分图，二分查找算法，图灵机，图论，理查德·卡普，算法，组合数学，电路复杂性，计算模型，计算机科学，近似算法，背包问题，邱奇-图灵论题，零知识证明，電腦記憶體，John Wiley & Sons，概率，歸約，每秒指令，決定性問題，演绎推理，指数函数，施普林格科学+商业媒体，旅行推销员问题。
劍橋大學出版社
劍橋大學出版社（Cambridge University Press）隸屬於英國劍橋大學，成立於1534年，是世界上僅次於牛津大學出版社的第二大大學出版社。.
新！!: 計算複雜性理論和劍橋大學出版社 · 查看更多 »
博弈论
賽局理論（game theory），又譯為对策论，或者--，经济学的一个分支，1944年馮·諾伊曼與奧斯卡·摩根斯特恩合著《博弈論與經濟行為》，標誌著現代系統博弈理論的的初步形成，因此他被稱為「博弈論之父」。博弈論被認為是20世紀經濟學最偉大的成果之一。目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。主要研究公式化了的激励结构（游戏或者博弈）间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。也是運籌學的一个重要学科。.
新！!: 計算複雜性理論和博弈论 · 查看更多 »
卡普的二十一個NP-完全問題
在計算複雜度理論內，一個極度重要的成就是史提芬·古克在1971年證明出了第一個NP-完全問題— 布爾可滿足性問題。在1972年，理查德·卡普將這個想法往前推進，發表了他著名的論文"Reducibility Among Combinatorial Problems"，其內證明了21個不同的，均因為其難解而惡名昭彰的組合數學與圖論問題，是NP-完全問題。 藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P.
新！!: 計算複雜性理論和卡普的二十一個NP-完全問題 · 查看更多 »
可计算性理论
在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。.
新！!: 計算複雜性理論和可计算性理论 · 查看更多 »
史蒂芬·库克
史蒂芬·亞瑟·库克（Stephen Arthur Cook，，計算機科學家，計算複雜性理論的重要研究者。 1971年，在他的論文《The Complexity of Theorem Proving Procedures》，他整理了NP完備性的目標，亦產生了库克定理——布爾可滿足性問題是NP完備的證明。 1982年，库克获得图灵奖。因為其論文開啟了NP完備性的研究，令這個领域於之後的十年成為計算機科學中最活躍和重要的研究。 库克現為多倫多大學的計算機科學和數學系教授。.
新！!: 計算複雜性理論和史蒂芬·库克 · 查看更多 »
启发法
启发法（heuristics，源自古希腊语的εὑρίσκω，又译作：策略法、助发现法、启发力、捷思法）是指依据有限的知识（或“不完整的信息”）在短时间内找到问题解决方案的一种技术。它是一种依据关于系统的有限认知和假说从而得到关于此系统的结论的分析行为。由此得到的解决方案有可能会偏离最佳方案。通过与最佳方案的对比，可以确保启发法的质量。 典型的启发法有试错法和排除法。鉴于启发法基于经验，有时它也可能是基于错误的经验（如感知偏离和伪关系）。.
新！!: 計算複雜性理論和启发法 · 查看更多 »
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: 計算複雜性理論和复杂性类 · 查看更多 »
大O符号
大O符号（Big O notation），又稱為漸進符號，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。 大O符号是由德国数论学家在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家的著作中才推广的，因此它有时又称为朗道符号（Landau symbols）。代表“order of...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。.
新！!: 計算複雜性理論和大O符号 · 查看更多 »
密码学
密碼學（Cryptography）可分为古典密码学和现代密码学。在西欧語文中，密码学一词源於希臘語kryptós“隱藏的”，和gráphein“書寫”。古典密码学主要关注信息的保密书写和传递，以及与其相对应的破译方法。而现代密码学不只关注信息保密问题，还同时涉及信息完整性验证（消息验证码）、信息发布的不可抵赖性（数字签名）、以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。古典密码学与现代密码学的重要区别在于，古典密码学的编码和破译通常依赖于设计者和敌手的创造力与技巧，作为一种实用性艺术存在，并没有对于密码学原件的清晰定义。而现代密码学则起源于20世纪末出现的大量相关理论，这些理论使得现代密码学成为了一种可以系统而严格地学习的科学。 密码学是数学和计算机科学的分支，同时其原理大量涉及信息论。著名的密碼學者罗纳德·李维斯特解釋道：「密碼學是關於如何在敵人存在的環境中通訊」，自工程學的角度，這相當于密碼學與純數學的差异。密碼學的发展促進了计算机科学，特別是在於電腦與網路安全所使用的技術，如存取控制與資訊的機密性。密碼學已被應用在日常生活：包括自动柜员机的晶片卡、電腦使用者存取密碼、電子商務等等。.
新！!: 計算複雜性理論和密码学 · 查看更多 »
中央处理器
中央处理器 （Central Processing Unit，缩写：CPU），是计算机的主要设备之一，功能主要是解释计算机指令以及处理计算机软件中的数据。计算机的可编程性主要是指对中央处理器的编程。中央处理器、内部存储器和输入／输出设备是现代电脑的三大核心部件。1970年代以前，中央处理器由多个独立单元构成，后来发展出由集成电路制造的中央处理器，這些高度收縮的元件就是所謂的微处理器，其中分出的中央处理器最為复杂的电路可以做成单一微小功能强大的单元。 中央处理器廣義上指一系列可以执行复杂的计算机程序的逻辑机器。这个空泛的定义很容易地将在“CPU”这个名称被普遍使用之前的早期计算机也包括在内。无论如何，至少从1960年代早期开始，这个名称及其缩写已开始在电子计算机产业中得到广泛应用。尽管与早期相比，“中央处理器”在物理形态、设计制造和具体任务的执行上有了极大的发展，但是其基本的操作原理一直没有改变。 早期的中央处理器通常是为大型及特定应用的计算机而定制。但是，这种昂贵的为特定应用定制CPU的方法很大程度上已经让位于开发便宜、标准化、适用于一个或多个目的的处理器类。这个标准化趋势始于由单个晶体管组成的大型机和微机年代，随着集成电路的出现而加速。IC使得更为复杂的中央处理器可以在很小的空间中设计和制造（在微米的數量级）。中央处理器的标准化和小型化都使得这一类数字设备和電子零件在现代生活中的出现频率远远超过有限应用专用的计算机。现代微处理器出现在包括从汽车到手机到儿童玩具在内的各种物品中。.
新！!: 計算複雜性理論和中央处理器 · 查看更多 »
布尔可满足性问题
可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布爾可滿足性問題（Boolean satisfiability problem；SAT)）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多領域的皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。.
新！!: 計算複雜性理論和布尔可满足性问题 · 查看更多 »
布尔函数
在数学中，布尔函数（Boolean function）描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中（参见S-box）。.
新！!: 計算複雜性理論和布尔函数 · 查看更多 »
并行计算
并行计算（parallel computing）一般是指许多指令得以同时进行的计算模式。在同時進行的前提下，可以將計算的過程分解成小部份，之後以並行方式來加以解決。 電腦軟體可以被分成數個運算步驟來執行。為了解決某個特定問題，軟體採用某個演算法，以一連串指令執行來完成。傳統上，這些指令都被送至單一的中央处理器，以循序方式執行完成。在這種處理方式下，單一時間中，只有單一指令被執行(processor level: 比较微处理器，CISC, 和RISC，即流水线Pipeline的概念，以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展，比如branch-prediction, 比如forwarding，比如在每个运算单元前的指令堆栈，汇编程序员对programm code的顺序改写)。平行運算採用了多個運算單元，同時執行，以解決問題。.
新！!: 計算複雜性理論和并行计算 · 查看更多 »
交互式证明系统
在计算复杂性理论中，交互式证明体系（下简称交互证明）是一类计算模型。像其它计算模型一样，我们的目标是对一个语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。 交互证明的基本假设是：证明者在计算能力上是无限的，在概率多项式时间的图灵机。一般来说，对给定的L，我们关注的是交互证明中验证者V这一角色，并对它加以如下的要求：.
新！!: 計算複雜性理論和交互式证明系统 · 查看更多 »
二分图
二分图又稱雙分圖、二部图、偶图，指頂點可以分成兩個不相交的集U和V(U and V 皆为（independent sets），使得在同一個集內的頂點不相鄰（沒有共同邊）的圖。 二分图又称作二部图，是图论中的一种特殊模型。 设 G.
新！!: 計算複雜性理論和二分图 · 查看更多 »
二分查找算法
#重定向 二分搜索算法.
新！!: 計算複雜性理論和二分查找算法 · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: 計算複雜性理論和图灵机 · 查看更多 »
图论
图论（Graph theory）是组合数学的一个分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯复形。.
新！!: 計算複雜性理論和图论 · 查看更多 »
理查德·卡普
查德·曼寧·卡普（Richard Manning Karp，），計算機科學家以及計算理論家。為柏克萊加州大學教授，在演算法理論方面有卓越的貢獻，因此獲得1985年的圖靈獎，2004年的本杰明·富兰克林奖章，2008年的京都賞（Kyoto Prize）。.
新！!: 計算複雜性理論和理查德·卡普 · 查看更多 »
算法
-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.
新！!: 計算複雜性理論和算法 · 查看更多 »
组合数学
广义的组合数学（Combinatorics）就是离散数学，狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究可數或离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。 组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳組合）等。.
新！!: 計算複雜性理論和组合数学 · 查看更多 »
电路复杂性
电路复杂性理论在1990年代以前，被众多研究者认为是解决NP与P关系问题的可能的途径之一。电路复杂性研究的对象是非一致性的计算模型电路，并考虑计算一个布尔函数所需的最小的电路的深度（depth）和大小（size）等资源。其中，大小为多项式大小的电路族可以计算的布尔函数被记为P/poly。可以证明，P包含在P/poly之中，而卡普-利普顿定理（Karp-Lipton theorem）表明若P/poly在NP之中，则多项式层级（polynomial hierarchy）将会坍缩至第二层，这是一个不大可能的结果。这两个结果结合起来表明，P/poly可以当作是分离NP与P的一个中间的工具，具体的途径就是证明任一个NP完全问题的电路大小的下界。在直观上说，电路复杂性也绕过了NP与P问题的第一个困难：相对化证明困难（relativizing proofs）。 在1980年代，电路复杂性途径取得了一系列的成功，其中包括奇偶性函数（Parity function）在AC^0中的下界为指数，以及团问题（clique problem）在单调性电路（monotone circuit）中的下界为指数。然而在1994年Razborov和Rudich的著名论文自然性证明（Natural proof）中指出，上面所用证明电路下界的方法，在单向函数存在的前提下是不可能分离NP和P的。该结果使很多专家对证明电路下界来分离NP和P的前景表示不乐观。.
新！!: 計算複雜性理論和电路复杂性 · 查看更多 »
计算模型
计算模型（computational model）是计算科学中的一个数学模型，它使用大量的計算資源来用计算机模拟研究一个复杂系统的行为。被研究的系统通常是一个复杂的非線性系统，这种系统不易取得简单、直观的解析解。相比于推导数学分析来解决问题，它是通过在计算机中调整系统参数并研究实验结果的差异来完成模型。模型的操作理论可以从这些实验来推断/推导。 常见的计算模型有天气预报模型、地球模拟器模型、飛行模擬器模型、分子蛋白质折叠模型和神经网络模型。.
新！!: 計算複雜性理論和计算模型 · 查看更多 »
计算机科学
计算机科学用于解决信息与计算的理论基础，以及实现和应用它们的实用技术。 计算机科学（computer science，有时缩写为CS）是系统性研究信息与计算的理论基础以及它们在计算机系统中如何与应用的实用技术的学科。 它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。计算机科学包含很多分支领域；有些强调特定结果的计算，比如计算机图形学；而有些是探討计算问题的性质，比如计算复杂性理论；还有一些领域專注于怎样实现计算，比如程式語言理論是研究描述计算的方法，而程式设计是应用特定的程式語言解决特定的计算问题，人机交互则是專注于怎样使计算机和计算变得有用、好用，以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算机问题的事业（比如信息技术），或者只是与使用计算机的经验有关，如玩游戏、上网或者文字处理。其实计算机科学所关注的，不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质，更要通过现有的知识创造新的程序或者改进已有的程序。 尽管计算机科学（computer science）的名字里包含计算机这几个字，但实际上计算机科学相当数量的领域都不涉及计算机本身的研究。因此，一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学（computing science），以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy"，以反映这一事实，即科学学科是围绕着数据和数据处理，而不一定要涉及计算机。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院，该学院成立于1969年，Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时，在计算技术发展初期，《ACM通讯》建议了一些针对计算领域从业人员的术语：turingineer，turologist，flow-charts-man，applied meta-mathematician及applied epistemologist。 三个月后在同样的期刊上，comptologist被提出，第二年又变成了hypologist。 术语computics也曾经被提议过。在欧洲大陆，起源于信息（information）和数学或者自动（automatic）的名字比起源于计算机或者计算（computation）更常见，如informatique（法语），Informatik（德语），informatika（斯拉夫语族）。 著名计算机科学家Edsger Dijkstra曾经指出：“计算机科学并不只是关于计算机，就像天文学并不只是关于望远镜一样。”（"Computer science is no more about computers than astronomy is about telescopes."）设计、部署计算机和计算机系统通常被认为是非计算机科学学科的领域。例如，研究计算机硬件被看作是计算机工程的一部分，而对于商业计算机系统的研究和部署被称为信息技术或者信息系统。然而，现如今也越来越多地融合了各类计算机相关学科的思想。计算机科学研究也经常与其它学科交叉，比如心理学，认知科学，语言学，数学，物理学，统计学和经济学。 计算机科学被认为比其它科学学科与数学的联系更加密切，一些观察者说计算就是一门数学科学。 早期计算机科学受数学研究成果的影响很大，如Kurt Gödel和Alan Turing，这两个领域在某些学科，例如数理逻辑、范畴论、域理论和代数，也不断有有益的思想交流。.
新！!: 計算複雜性理論和计算机科学 · 查看更多 »
近似算法
近似算法是计算机科学中算法研究的一个重要方向。所谓“近似”，就是指结果不一定是最优的，但是也在可以承受的范围内，而且可以比精确求解消耗更少的资源。这里的资源是计算复杂性理论中的标准，可以是时间，空间或者询问次数等。.
新！!: 計算複雜性理論和近似算法 · 查看更多 »
背包问题
背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。 相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。 也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。.
新！!: 計算複雜性理論和背包问题 · 查看更多 »
邱奇-图灵论题
#重定向 邱奇－图灵论题.
新！!: 計算複雜性理論和邱奇-图灵论题 · 查看更多 »
零知识证明
#重定向 交互式证明系统#.E9.9B.B6.E7.9F.A5.E8.AF.86.E8.AF.81.E6.98.8E.EF.BC.88Zero-knowledge_proofs.EF.BC.89.
新！!: 計算複雜性理論和零知识证明 · 查看更多 »
電腦記憶體
電腦記憶體（Computer memory）是一種利用半導體技術制成的儲存資料的電子裝置。其電子電路中的資料以二進位方式儲存，記憶體的每一個儲存單元稱做記憶元。 電腦記憶體可分为内部存储器(简称内存或主存)和外部存储器，其中内存是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取速率快。内存是电脑中的主要部件，它是相对于外存而言的。我们平常使用的程序，如Windows操作系统、打字软件、游戏软件等，一般都是安装在硬盘等外存上的，但仅此是不能使用其功能的，必须把它们调入内存中运行，才能真正使用其功能，我们平时输入一段文字，或玩一个游戏，其实都是在内存中进行的。就好比在一个书房里，存放书籍的书架和书柜相当于电脑的外存，而我们工作的办公桌就是内存。通常我们把要永久保存的、大量的数据存储在外存上，而把一些临时的或少量的数据和程序放在内存上，当然内存的好坏会直接影响电脑的运行速度。.
新！!: 計算複雜性理論和電腦記憶體 · 查看更多 »
John Wiley & Sons
#重定向 約翰威立.
新！!: 計算複雜性理論和John Wiley & Sons · 查看更多 »
概率
--率，舊稱--率，又称或然率、機會率或--、可能性，是数学概率论的基本概念，是一个在0到1之间的实数，是对随机事件发生之可能性的度量。 概率常用來量化對於某些不確定命題的想法"Kendall's Advanced Theory of Statistics, Volume 1: Distribution Theory", Alan Stuart and Keith Ord, 6th Ed, (2009), ISBN 978-0-534-24312-8，命題一般會是以下的形式：「某個特定事件會發生嗎？」，對應的想法則是：「我們可以多確定這個事件會發生？」。確定的程度可以用0到1之間的數值來表示，這個數值就是機率William Feller, "An Introduction to Probability Theory and Its Applications", (Vol 1), 3rd Ed, (1968),Wiley,ISBN 978-0-471-25708-0。因此若事件發生的機率越高，表示我們越認為這個事件可能發生。像丟銅板就是一個簡單的例子，正面朝上及背面朝上的兩種結果看來機率相同，每個的機率都是1/2，也就是正面朝上及背面朝上的機率各有50%。 這些概念可以形成機率論中的數學公理（參考概率公理），在像數學、統計學、金融、博弈論、科學（特別是物理）、人工智慧/機器學習、電腦科學及哲學等學科中都會用到。機率論也可以描述複雜系統中的內在機制及規律性。.
新！!: 計算複雜性理論和概率 · 查看更多 »
歸約
在可計算性理論與計算複雜性理論中，所謂的歸約是將某個轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。 一般寫作A ≤m B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。 將一組問題歸約到特定類型所產生的數學結構，通常形成预序关系，其等價類可用於定義求解難度和複雜度。.
新！!: 計算複雜性理論和歸約 · 查看更多 »
每秒指令
每秒指令（Instructions per second，縮寫：IPS）是一種計算電腦中央處理器速度的記量單位。大多數IPS的數值是在某些特定測量軟體中取極限值所得，而較為可信的MIPS值取決於測試軟體的測試情境以及測試時間。記憶體階層的效能也大大影響處理器的效能，也影響IPS數值的真確性。由於以上問題，研發者發展了數套標準測試方案，例如SPECint以計算真實情況下軟體使用情況的效能，也讓IPS計量單位變成較無用的計量單位。 本術語通常與數量單位關連在一起，例如每秒千指令（kIPS）、每秒百萬指令（MIPS）或每秒百萬操作（MOPS）等。MFLOPS是考察单字长浮点指令的平均执行速度。.
新！!: 計算複雜性理論和每秒指令 · 查看更多 »
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.
新！!: 計算複雜性理論和決定性問題 · 查看更多 »
演绎推理
演绎推理（Deductive Reasoning）在传统的亚里士多德逻辑中是「结论，可从叫做‘前提’的已知事实，‘必然地’得出的推理」。如果前提为真，则结论必然为真。这区别于溯因推理和归纳推理：它们的前提可以预测出高概率的结论，但是不确保结论为真。 “演绎推理”还可以定义为结论在普遍性上不大于前提的推理，或「结论在确定性上，同前提一样」的推理。.
新！!: 計算複雜性理論和演绎推理 · 查看更多 »
指数函数
指数函数（Exponential function）是形式為b^x的數學函数，其中b是底數（或稱基數，base），而x是指數（index / exponent）。 現今指數函數通常特指以\mbox為底數的指數函數（即\mbox^x），為数学中重要的函数，也可寫作\exp(x)。这里的\mbox是数学常数，也就是自然对数函数的底数，近似值为2.718281828，又称为欧拉数。 作为实数变量x的函数，y.
新！!: 計算複雜性理論和指数函数 · 查看更多 »
施普林格科学+商业媒体
施普林格科学+商业媒体（Springer Science+Business Media）或施普林格（Springer，），在柏林成立，是一个总部位于德国的世界性出版公司，它出版教科书、学术参考书以及同行评论性杂志，专--于科学、技术、数学以及医学领域。在科学、技术与医学领域中，施普林格是最大的书籍出版者，以及第二大世界性杂志出版者（最大的是爱思唯尔）。施普林格拥有超过60个出版社，每年出版1,900种杂志，5,500种新书，营业额为9.24亿欧元（2006年），雇有超过5,000名员工 。施普林格在柏林、海德堡、多德雷赫特（位于荷兰）与纽约设有主办事处。施普林格亚洲总部设在香港。2005年8月，施普林格在北京成立代表处。.
新！!: 計算複雜性理論和施普林格科学+商业媒体 · 查看更多 »
旅行推销员问题
旅行推销员问题（最短路径问题）（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。 TSP是与的一种特殊情况。 在计算复杂性理论中，TSP的做决定版本（其中，给定长度 L，任务是决定图中是否有路径比 L 还要短）属于NP完全问题。因此随着城市数量的增多，任何TSP算法最坏情况下的运行时间都有可能随着城市数量的增多超多项式（可能是）级别增长。 问题在1930年首次被形式化，并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中，观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用（如资源或时间窗口有限）中，可能会加入额外的约束。.
新！!: 計算複雜性理論和旅行推销员问题 · 查看更多 »
重定向到这里：
复杂度理论，复杂性理论，空间复杂度，算法复杂度，计算复杂度，计算复杂度理论，计算复杂性，计算复杂性理论。
