aiwiki.page
中文

算法与理论

141 个词条第 2 / 3 页
里德–所罗门码

里德–所罗门码利用有限域上的多项式运算,保护数字信息免受符号错误和擦除的影响。

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-problem
A* 搜索

A* 是一种最佳优先搜索算法,结合已累积的路径代价与预估的剩余代价,在特定条件下找到最优路径。

a-star-search
Alpha–Beta 剪枝

Alpha–Beta 剪枝通过排除不影响根节点值的分支,加速极小化极大算法的博弈树搜索。

alpha-beta-pruning