算法
概述
算法是为解决特定问题或完成特定任务而定义的有限、明确、有效的计算步骤序列，是计算机科学的核心概念之一。
关键内容
- 基本特征：
- 有穷性：算法必须在有限步骤内结束
- 确定性：每个步骤都有确切的含义
- 输入：有零个或多个输入
- 输出：有一个或多个输出
-
可行性：每个步骤都能够执行
-
理论定义：
- 在图灵机理论中，算法对应图灵机的程序
- 通过图灵机或其他等价模型可以精确定义算法概念
-
所有合理的算法定义都与图灵机等价（Church-Turing论题）
-
历史发展：
- 词源来自波斯数学家花拉子米（al-Khwarizmi）
- 1936年图灵给出算法概念的精确数学定义
-
为算法的性质和能力提供了理论基础
-
分类：
- 可计算算法：图灵机可以实现的算法
- 多项式时间算法：P类问题的算法
-
非确定性多项式时间算法：NP类问题的算法
-
与计算理论的关系：
- 算法概念是计算理论研究的基础
- 停机问题表明并非所有问题都有算法解
-
计算复杂度理论研究算法效率
-
实际应用：
- 排序、搜索等基础算法
- 加密、压缩等实用算法
- 机器学习、AI等高级算法
来源
- 01-turing-on-computable-numbers — 算法概念的精确化
- 论可计算数及其在判定问题上的应用 — 理论定义
相关
- 计算理论 — 理论框架
- 图灵机 — 理论模型
- 算法分析 — 性能研究
- 计算 — 上位概念
- 阿兰·麦席森·图灵 — 理论奠基人
- Church-Turing论题 — 等价性
- 停机问题 — 能力边界