计算复杂性理论 - 测验
A) 开发新的编程语言 B) 计算机硬件设计 C) 人机交互的心理学方面 D) 分析解决计算问题所需的资源
A) 希腊字母 B) 大 O 符号 C) 二进制代码 D) 罗马数字
A) EXP B) NP C) PSPACE D) BPP
A) 建造超级计算机 B) 生成随机数 C) 创造更快的计算机 D) 根据计算问题的内在难度对其进行分类
A) NP完备性 B) 量子算法 C) P 与 NP 问题 D) 并行计算
A) NP-complete B) P C) EXPTIME D) BPP
A) 探索性 B) 指数时间 C) 已扩展 D) 专家
A) NP-complete B) BQP C) 空间 D) PSPACE
A) 计算机硬件方面的问题。 B) 无法求解的数学方程。 C) 一个无法解决的理论问题。 D) 由计算机使用算法解决的任务。
A) 所有 ASCII 字符的集合 B) 二进制字母表 {0, 1} C) 十六进制字母表 D) 所有小写字母的集合
A) 一些具体的输入编码方式 B) 仅使用十进制表示 C) 不需要任何编码 D) 使用自然语言进行编码
A) 在图中寻找最短路径。 B) 计算网络中的最大流量。 C) 判断给定的图是否连通。 D) 确定图中节点的数量。
A) 检查一个图是否为二分图。 B) 判断一个数是否为素数。 C) 旅行商问题。 D) 确定两个图是否同构。
A) 字符 B) 单词 C) 字节 D) 比特
A) 一种用于操纵物理对象的设备。 B) 一种实际的计算技术。 C) 通用计算的理论模型。 D) 一种早期的计算机硬件形式。
A) 邱奇-图灵论题。 B) 哥德尔不完备性定理。 C) P 与 NP 问题。 D) 库克-列文定理。
A) 确定性图灵机。 B) 量子图灵机。 C) 概率图灵机。 D) 非确定性图灵机。
A) 它们以确定性方式运行。 B) 它们在计算过程中使用随机比特。 C) 它们需要具备物理实现的可能性。 D) 它们的运行时间受到多项式时间的限制。
A) 图灵完备性公理 B) 布卢姆复杂性公理 C) P 与 NP 公理 D) 库克-列文定理
A) 量子纠缠复杂度 B) 通信复杂度 C) 决策树复杂度 D) 电路复杂度
A) 通信复杂度 B) 空间复杂度 C) 时间复杂度 D) 电路复杂度
A) PP B) NP C) co-NP D) BQP
A) Hisao Yamada B) Raymond Smullyan C) Boris Trakhtenbrot D) John Myhill
A) PSPACE B) NP C) EXPTIME D) FP
A) NP 不等于 co-NP。 B) co-P 不等于 co-NP。 C) co-P 将等于 co-NP。 D) P 不等于 NP。
A) NL B) L C) NC D) PP
A) 21 B) 10 C) 30 D) 15
A) “信号函数” B) “图灵机” C) “多项式时间” D) “计算复杂度”
A) Sanjeev Arora; Boaz Barak B) Christos Papadimitriou C) Oded Goldreich D) Michael R. Garey; David S. Johnson
A) P B) 全部 C) EXPTIME D) NP
A) 布尔表达式。 B) 连续函数。 C) 量子态。 D) 离散图。
A) 摊销分析 B) 平均情况复杂度 C) 最坏情况复杂度 D) 最佳情况复杂度
A) MA B) PP C) BQP D) PH
A) 1956年 B) 1955年 C) 1971年 D) 1960年
A) Sanjeev Arora; Boaz Barak B) Oded Goldreich C) Christos Papadimitriou D) Michael R. Garey; David S. Johnson
A) Gabriel Lamé B) Juris Hartmanis C) Edmonds D) Leonid Levin
A) 约翰·迈希尔 B) 山田久雄 C) 鲍里斯·特拉赫滕布罗特 D) 雷蒙德·斯穆利安
A) 对数时间约简。 B) 多项式时间约简。 C) 线性时间约简。 D) 指数时间约简。
A) Downey, Rod; Fellows, Michael B) Garey, Michael R.; Johnson, David S. C) Arora, Sanjeev; Barak, Boaz D) Wuppuluri, Shyam; Doria, Francisco A.
A) NC B) BPP C) IP D) QMA
A) 时间层次定理 B) 库克-列文定理 C) 空间层次定理 D) 萨维奇定理
A) 线性边界自动机 B) 复杂度度量 C) 实时计算 D) 基本集合
A) 加布里埃尔·拉梅 (Gabriel Lamé) B) 尤里斯·哈特马尼斯 (Juris Hartmanis) C) 理查德·斯塔尔恩斯 (Richard E. Stearns) D) 艾伦·图灵 (Alan Turing)
A) BPP B) RP C) #P D) NC
A) Khalil, Hatem; Ulery, Dana B) Mertens, Stephan C) Fortnow, Lance; Homer, Steven D) Cook, Stephen
A) Sanjeev Arora B) Christos Papadimitriou C) Boaz Barak D) Michael Sipser
A) Cook, Stephen; Fortnow, Lance B) Downey, Rod; Fellows, Michael C) Wuppuluri, Shyam; Doria, Francisco A. D) Papadimitriou, Christos; Sipser, Michael
A) BPP B) AC C) QMA D) RP
A) BPP B) AC C) NC D) QMA
A) 概率算法。 B) 数字信号处理。 C) 连续动力系统和微分方程。 D) 有限状态机。
A) 萨维奇定理 B) P 与 NP 问题 C) 时间复杂度分层定理 D) 库克-列文定理
A) 1965 B) 1936 C) 1950 D) 1945
A) 1965 B) 1971 C) 1967 D) 1972 |
创建 That Quiz —
为数学和其它学科出题和测试的网站.