Definitions

• 定义：一个对于完成计算或者解决问题的精确指示的有限集合。
• 可以使用pseudocode来specify algorithms, 是一种介于自然语言与程序语言中间点的方法。

Properties

• 必须要有从一个确定的集合中决定的输入集合
• 输出一个结果，是问题的解决方案
• 必须是确定的(Definiteness)
• 必须是正确的correctness
• 必须是有限的finiteness
• 必须是有效的effectiveness
• 必须是可拓展的generality

Example Problems

• Optimization问题就是从一个集合中找到最大值或者最小值的问题
• Greedy Algorithms:
  • 贪心算法，每一步都采取当前步骤下的最优选择
  • 虽然不一定是最优的，无论是否最优，我们都将其称之为greedy algorithm
• 可以采用数学证明Cashier Problems下，Greedy Algorithm 一定是最优算法。