第一章 算法在计算中的作用

第1章 算法在计算中的作用

第一周

记于2022/12/4

• “是否存在一个通用的过程（算法）。可以自动判定任意命题是否正确？” 否
• 算法：一个定义明确的是可计算过程（Input -> Computational Procedure / algorithm -> Output）
• 算法是正确的：若对每个输入实例算法都以正确的输出停机，则称该算法是正确的，并称正确的算法解决了给定的计算问题。不正确的算法对某些输入实例可能根本不停机，也可能以不正确的回答停机。
• 应用领域
  • 基因工程
  • 互联网
  • 电子商务
  • 制造业和商业...
• 数据结构是一种存储和组织数据的方式，旨在便于访问和修改。
• 集合
• 线性结构
• 树形结构
• 图形结构
• 数据结构是静态的，算法是动态的；程序是动态的，算法是静态的
• 效率：为求解相同问题而设计的不同算法在效率方面常常具有显著的差别。这些差别可能比由于硬件和软件造成的差别要重要得多。