aiwiki.page
中文

算法与理论

141 个词条第 1 / 3 页
2-SAT

2-SAT 判断每个子句至多含两个文字的布尔公式是否存在满足赋值,可在线性时间内求解。

two-sat
3SUM问题

3SUM问题旨在判断一组数中是否存在三个元素之和为零,是细粒度复杂度理论中的基准问题。

3sum-problem
阿姆达尔定律

阿姆达尔定律描述了计算中未受改进影响的部分如何限制整体加速比,尤其适用于增加并行处理器的情形。

amdahls-law
艾伦·图灵

艾伦·图灵是英国数学家和密码破译专家,其研究奠定了计算机科学、人工智能与数学生物学的基础。

alan-turing
贝尔曼–福特算法

贝尔曼–福特算法求解含负权边的加权图中的单源最短路径,并检测从源点可达的负权环。

bellman-ford-algorithm
背包问题

背包问题研究如何从重量和价值已知的物品中进行选择,使总重量不超过容量限制,同时使总价值最大。

knapsack-problem
泵引理

泵引理给出某类形式语言必须满足的重复性质,常用于证明语言不是正则语言或上下文无关语言。

pumping-lemma
比特

比特是二进制数位,也是信息量的单位,是数字计算、存储与通信的基础。

bit
编辑距离

编辑距离是通过插入、删除、替换等指定操作将一个序列转换为另一个序列所需的最小总成本。

edit-distance
并行计算

并行计算同时利用多个处理资源执行计算任务的不同部分,以提高速度或处理更大规模的问题。

parallel-computing
博弈树

博弈树表示博弈中可能的行动序列及结果,用于分析策略决策和设计计算机博弈算法。

game-tree
布尔可满足性问题

布尔可满足性问题判定是否存在使布尔公式为真的赋值,连接计算复杂性理论与实用的自动推理。

boolean-satisfiability-problem
插入排序

插入排序逐个元素构建有序序列,仅需常数辅助空间,适用于小规模或接近有序的输入。

insertion-sort
抽象数据类型

抽象数据类型通过可观察的行为规定值及其操作,而不依赖具体的表示或实现方式。

abstract-data-type
达梅劳–莱文斯坦距离

达梅劳–莱文斯坦距离是将一个字符串变为另一个所需的插入、删除、替换及相邻交换操作的最少次数。

damerau-levenshtein-distance
大Θ记号

大Θ记号描述函数增长的渐近紧确界,忽略常数因子及输入规模较小时的行为。

big-theta-notation
大Ω记号

大Ω记号表示函数的渐近下界,常用于描述输入规模增长时计算资源需求的下界。

big-omega-notation
戴克斯特拉算法

戴克斯特拉算法通过反复确定尚未定案的最近顶点,在边权非负的图中计算最短路径。

dijkstra-algorithm
倒排索引

倒排索引将词项或其他索引特征映射到包含它们的文档,支持高效的全文搜索、筛选和排序检索。

inverted-index
低密度奇偶校验码

低密度奇偶校验码利用稀疏的奇偶校验约束和迭代译码,保护传输或存储的信息免受错误影响。

low-density-parity-check-code
递归

递归通过自身的更简单实例来定义结构或计算,是数学定义和许多算法的基础。

recursion
递归函数

递归函数将有效计算形式化,并通过引用所定义函数自身的规则来规定计算。

recursive-functions
迭代

迭代是反复执行某一过程,用于遍历数据、改进近似解、解决计算问题,以及逐步开发软件。

iteration
动态规划

一种通过组合并复用子问题的解来求解具有特定结构的问题的数学与计算方法。

dynamic-programming
动态数组

动态数组是一种可调整长度的序列,支持常数时间的按索引访问,以及摊还常数时间的尾部插入。

dynamic-array
堆排序

堆排序是一种原地比较排序算法,利用二叉堆以常数辅助空间实现最坏情况下 O(n log n) 的运行时间。

heapsort
队列(数据类型)

队列是一种先进先出的抽象数据类型,用于有序处理、缓冲、通信和算法遍历。

queue-data-type
多边形三角剖分

多边形三角剖分将多边形区域划分为内部互不重叠的三角形,广泛用于几何算法、图形处理和数值模拟。

polygon-triangulation
二叉堆

二叉堆是满足堆序约束的完全二叉树,可高效访问和移除最小或最大元素。

binary-heap
二叉树

二叉树是一种有根数据结构,每个节点最多有两个可区分的子节点,可用于搜索、优先队列、表达式处理和层次化计算。

binary-tree
二叉搜索树

二叉搜索树按层次组织键,支持查找、更新和有序查询,其效率取决于树的高度。

binary-search-tree
二分查找

二分查找通过反复排除约一半的剩余候选项,在有序搜索空间中定位目标值或边界。

binary-search
分布式共识

分布式共识使独立的计算进程在发生故障、通信延迟或恶意行为时,仍能就共同决策达成一致。

distributed-consensus
分治法

一种算法设计范式,通过将问题分解为较小的子问题并合并其解来求解原问题。

divide-and-conquer
弗洛伊德–沃舍尔算法

弗洛伊德–沃舍尔算法利用动态规划,计算加权图中所有顶点对之间的最短路径距离。

floyd-warshall-algorithm
复杂性类

复杂性类根据求解所需的资源、计算模型及正确性条件,对计算问题进行分类。

complexity-class
格罗弗算法

格罗弗算法在无结构搜索空间中查找标记项,所需预言机查询次数相较经典搜索具有平方级加速。

grovers-algorithm
广度优先搜索

广度优先搜索按距离逐层探索图,并在所有边的代价相等时求出最短路径。

breadth-first-search
归并排序

一种基于比较的排序算法,将数据划分为较小的序列,再将排好序的序列合并为完整的有序结果。

merge-sort
哈夫曼编码

哈夫曼编码为给定的符号分布构造变长前缀码,使平均码字长度最小。

huffman-coding
哈希表

哈希表通过计算数组位置存储键及其关联值,在哈希方式和容量适当时,可实现快速查找、插入和删除。

hash-table
哈希函数

哈希函数将数据映射为紧凑的值,用于高效查找、比较和分布,并可在具备适当安全性质时提供密码学保护。

hash-function
汉明距离

汉明距离统计两个等长序列中符号不同的位置数,是纠错码和离散数据比较中的基本度量。

hamming-distance
红黑树

红黑树是一种自平衡二叉搜索树,通过颜色不变式保证查找、插入和删除操作的时间复杂度为对数级。

red-black-tree
混叠

混叠指不同信号经采样后无法区分,产生虚假频率或图案;在编程中则指多个引用指向同一存储位置。

aliasing
极小极大算法

极小极大算法是一种对抗搜索算法,假定对手采取最优策略,据此选择能取得最佳结果的行动。

minimax
计算复杂性

计算复杂性研究解决计算问题所需的资源,以及高效计算的极限。

computational-complexity
计算机科学

计算机科学研究计算、算法、信息处理,以及软件和计算机系统的基本原理。

computer-science
计算几何

计算几何研究表示、分析和处理几何对象的算法与数据结构,应用于空间搜索、图形学、工程和机器人学。

computational-geometry
计算模型

计算模型以形式化方式规定计算过程如何运行、能计算什么,以及消耗哪些资源。

model-of-computation
加性白高斯噪声信道

加性白高斯噪声信道通过在发送信号上叠加与信号独立、功率谱平坦的高斯噪声来描述通信过程。

additive-white-gaussian-noise-channel
近似算法

近似算法能高效求得优化问题的可行解,并以数学证明保证其与最优解的差距。

approximation-algorithm
纠错码

纠错码为数据加入有结构的冗余,使解码器能在出现一定传输或存储错误时恢复信息。

error-correcting-code
局部敏感哈希

局部敏感哈希以较高概率将相似对象映射到相同哈希值,从而实现高效的近似相似性搜索。

locality-sensitive-hashing
柯尔莫哥洛夫复杂度

柯尔莫哥洛夫复杂度以有限对象的最短有效描述的长度,度量该对象所含的信息量。

kolmogorov-complexity
可计算性理论

可计算性理论研究算法能够解决哪些问题,并对不可解性的数学界限与程度进行分类。

computability-theory
可满足性模理论

可满足性模理论结合布尔推理与数学理论,判断逻辑约束是否存在模型。

satisfiability-modulo-theories
空间复杂度

空间复杂度衡量在指定计算模型和计量约定下,算法所需内存随输入规模增长的情况。

space-complexity
快速排序

快速排序是一种基于划分的排序算法,期望运行时间为 \(O(n\log n)\),且有高效的原地实现。

quicksort
快速选择

快速选择通过分区在无序集合中寻找指定秩的元素,随机选择枢轴时期望运行时间为线性。

quickselect