里德–所罗门码利用有限域上的多项式运算,保护数字信息免受符号错误和擦除的影响。
reed-solomon-code链表链表是一种用引用连接元素的序列式数据结构,可在局部插入和删除元素,无须移动相邻元素。
linked-list量子电路量子电路以有序网络表示计算,网络包含量子门、态制备、测量和经典控制操作。
quantum-circuit量子纠错量子纠错通过冗余编码保护量子信息,并在不测量所存储逻辑态的情况下识别错误。
quantum-error-correction量子退火量子退火利用受控的量子涨落,搜索用于编码优化问题或物理模型的低能态。
quantum-annealing邻接表邻接表通过为每个顶点关联一组相邻顶点或关联边来表示图。
adjacency-list梅西会议梅西会议是1946至1953年举行的跨学科会议,通过探讨反馈、通信及生物与社会系统,推动了控制论的确立。
macy-conferences蒙特卡洛算法蒙特卡洛算法利用随机性,在保证计算成本有界的同时,允许结果以受控概率出错。
monte-carlo-algorithm米利机米利机是一种有限状态计算模型,每一步的输出由当前状态和当前输入共同决定。
mealy-machine模型检验模型检验通过系统分析系统数学模型的可能行为,自动判定模型是否满足形式化规定的性质。
model-checking排序算法排序算法按指定顺序重排数据,其性能取决于比较模型、内存需求、稳定性和输入特征。
sorting-algorithm启发式方法利用估计或简化规则指导决策的实用问题求解方法,但不一定保证得到最优结果。
heuristic启发式评估函数估计状态价值或到达目标所需代价的函数,使搜索算法无需穷尽所有可能即可作出决策。
heuristic-evaluation-function前缀码任何码字都不是其他码字前缀的编码,拼接后的码字无需向后预读或分隔符即可解码。
prefix-code强指数时间假设强指数时间假设断言,随着子句宽度增大,布尔可满足性问题的指数时间复杂度趋近于穷举搜索。
strong-exponential-time-hypothesis丘奇—图灵论题丘奇—图灵论题将有效可计算函数等同于图灵机可计算函数,把非形式化的算法概念与精确的数学模型联系起来。
church-turing-thesis日志结构合并树一种写入优化的索引结构,通过缓冲更新并跨存储层合并有序数据,以额外读取和重写换取更低的写入开销。
log-structured-merge-tree深度优先搜索深度优先搜索沿每条分支尽可能深入,再回溯探索其他分支,以遍历图或树。
depth-first-search时间复杂度时间复杂度描述在指定计算模型下,算法所需的计算工作量如何随输入规模增长。
time-complexity束搜索束搜索是一种启发式搜索算法,每步仅保留有限个有潜力的部分解,以缩小搜索范围为代价降低计算成本。
beam-search树(数据结构)树是一种层次化数据结构,利用父子关系支持高效搜索、索引、优先级管理及嵌套信息表示。
tree-data-structure数据结构数据结构组织信息及其相互关系,使计算机程序能够高效地访问、修改和处理数据。
data-structure数据压缩数据压缩以更少的比特表示信息,通过精确保留原始数据或允许受控损失,降低存储和传输需求。
data-compression数组(数据结构)数组是按索引组织的元素集合,通常以固定间隔存储在内存中,以便高效地直接访问。
array-data-structure斯特拉森算法斯特拉森算法以七次递归分块乘法替代八次,将矩阵乘法的算术复杂度降至次立方级。
strassen-algorithm算法算法是为执行计算或解决某一类问题而精确定义的过程。
algorithm算术编码算术编码是一种无损压缩技术,通过逐步细分概率区间来表示符号序列。
arithmetic-coding随机化算法在计算过程中使用随机选择,并以概率分析其正确性、运行时间或近似质量的算法。
randomized-algorithm贪心算法贪心算法通过局部最优选择逐步构造解;当问题结构保证这些选择在全局上安全时,便能得到最优解。
greedy-algorithm摊还分析摊还分析通过约束操作序列的总成本,给出单次操作的成本保证,无须假定输入的概率分布。
amortized-analysis停机问题停机问题询问程序在给定输入下是否会终止;不存在能对所有程序和输入都作出正确判断的算法。
halting-problem通用图灵机通用图灵机是一种抽象计算机器,能根据编码后的机器描述及输入,模拟任意图灵机。
universal-turing-machine图灵机图灵机是一种抽象计算模型,用于定义算法、确定可计算性的界限并分析计算资源。
turing-machine图灵奖图灵奖是美国计算机协会每年颁发的奖项,表彰对计算领域具有持久且重大技术意义的贡献。
turing-award图灵完备性图灵完备性是指计算系统在资源不受限的条件下模拟任意图灵机的能力。
turing-completeness唯一博弈猜想计算复杂性中的一个猜想:区分几乎可满足与高度不可满足的唯一约束系统是 NP 困难的。
unique-games-conjecture伪代码伪代码以编程结构、数学符号和自然语言描述算法,便于人类阅读,无须遵守可执行代码的句法规则。
pseudocode伪随机数生成器伪随机数生成器是一种确定性算法,可将初始状态扩展为可复现、近似随机的数值序列。
pseudorandom-number-generator稳定排序稳定排序保留排序键相等的元素原有的相对顺序,使先前的排序信息在后续排序中得以保留。
stable-sorting无损数据压缩无损数据压缩在减小数据表示大小的同时,允许精确还原原始数据。
lossless-data-compression线性查找线性查找逐一检查元素,直到找到匹配项或遍历整个搜索范围,最坏情况下需要线性时间。
linear-search肖尔算法肖尔算法利用量子周期查找,在多项式时间内完成整数分解和离散对数计算,对广泛使用的公钥密码体系构成挑战。
shors-algorithm信息增益信息增益衡量观测或数据划分使不确定性降低的程度,通常用熵的减少量或先验与后验分布之间的散度表示。
information-gain形式语言形式语言是精确定义的符号串集合,可通过文法、自动机、代数、逻辑和计算等方法加以研究。
formal-language循环不变式循环不变式是程序状态的一种性质,在循环每次迭代前后的指定位置都成立。
loop-invariant优先队列优先队列是一种按优先级而非插入顺序取出元素的抽象数据类型,通常用堆实现。
priority-queue游程编码游程编码是一种无损压缩技术,将连续重复的值表示为该值及其重复次数。
run-length-encoding有损数据压缩有损数据压缩通过丢弃部分信息来缩小数字数据的体积,以无法精确还原原始数据为代价,降低存储或传输需求。
lossy-data-compression有限状态机有限状态机通过有限个状态及根据输入改变状态的规则,对计算或控制过程进行建模。
finite-state-machine原地算法原地算法在输入数据原有的存储空间内完成变换,仅使用少量额外内存。
in-place-algorithm栈(数据类型)栈是一种按后进先出顺序存储元素的抽象数据类型,支持在指定的一端插入和移除元素。
stack-data-type正则语言正则语言是可由有限自动机识别的有限字符串集合,也可等价地用经典正则表达式描述。
regular-language指数时间假设指数时间假设猜想:在最坏情况下,判定3-CNF布尔公式的可满足性需要关于变量数的指数时间。
exponential-time-hypothesis中位数的中位数中位数的中位数是一种确定性的枢轴选择方法,可在最坏情况下以线性时间找到任意指定秩的元素。
median-of-medians主定理主定理通过比较非递归工作量与递归分支的增长,给出分治递推关系的渐近界。
master-theorem字节对编码字节对编码是一种反复替换相邻符号对的算法,用于无损压缩,经过改造后也用于学习语言处理中的子词词表。
byte-pair-encoding自动定理证明自动定理证明利用计算方法推导形式化公理的逻辑后果,为数学、验证和机器推理提供支持。
automated-theorem-proving最短路径问题最短路径问题旨在寻找图中顶点之间总权重最小的路线,算法选择取决于图的结构和边权。
shortest-path-problemA* 搜索A* 是一种最佳优先搜索算法,结合已累积的路径代价与预估的剩余代价,在特定条件下找到最优路径。
a-star-searchAlpha–Beta 剪枝Alpha–Beta 剪枝通过排除不影响根节点值的分支,加速极小化极大算法的博弈树搜索。
alpha-beta-pruning