引论
1.理解什么是算法，算法的特征，算法和程序的差别；
2.理解什么是判断问题、搜索问题和优化问题。
1.1 计算机问题
计算机问题
计算机问题：A task to be performed by computers（需要计算机解决的任务）
Problems（问题）：mapping from inputs to matching outputs. （输入到对应输出的一个映射）
A particular input must always result in the same output every time the function is computed.
（每次同样的输入计算机给出同样的输出）
★三种不同的计算机问题
Decision Problem 判断问题
回答yes或者no
比如：输入的数是否大于60
Optimal Problem 优化问题
求最优解
比如：从A到B的最短路径长度是多少？
Search problem 搜索问题 / Numerical Calculation 数值计算
比如用计算机求方程或积分等，这些问题都属于数值计算问题
计算机问题求解步骤
理解问题
设计算法前做的第一件事情
仔细阅读问题的描述
提出疑问
手工处理一些实例
考虑特殊情况
确定输入
抽象出问题，用数学表达式描述
了解计算设备的性能，确定计算方法
顺序算法
并行算法
选择精确解和近似解
某些重要的问题无法求得精确解
某些问题求精确解速度慢，无法接受
确定适当的数据结构
算法 + 数据结构 = 程序
算法设计策略
使用算法解题的一般性方法，用于解决计算领域的多种问题。
设计并描述算法
自然语言
伪代码
流程图
证明算法的正确性
证明对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。
一般方法：数学归纳法
证明算法的正确性与不正确哪一个更容易？
分析算法
算法有两种效率：时间效率和空间效率
算法的另外两个特性：简单性和一般性
为算法写代码
用计算机程序实现算法
在把算法转变为程序的过程中，可能会发生错误或者效率非常低
常见的计算机问题
排序(Sorting)
查找(Search)
串处理(String)
图问题(Graph)
组合问题(Combination)
几何问题(Geometry)
数值问题(Numerical)
1.2 算法
★什么是算法？
算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
算法是解决问题的方法。
算法的几个要点
算法的每一个步骤都必须清晰、明确。
算法所处理的输入的值域必须仔细定义。
同样的一个算法可以用几种不同的形式来描述。
可能存在几种解决相同问题的算法。
针对同一个问题的算法可能会基于完全不同的解题思路，而且解题的速度也会有明显区别。
★算法的特征
输入（input）：算法有零个或多个输入量；
输出（output）：算法至少产生一个输出量；
确定性（definiteness）：算法的每一条指令都有确切的定义，没有二义性；
有穷性（finiteness）：算法必须总能在执行有限步之后终止。
★程序与算法的比较
计算机程序是算法用某种程序语言的一个具体表示（实现）。一个Java程序和一个C程序可能是用同样的方法解决同一个问题，这两个语言表达的就是同一个算法。
计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。
程序可以不满足算法的有穷性。
程序 算法 数据结构
计算机程序是使用计算机求解问题的过程
算法是求解问题的步骤描述：从蛮力到策略
数据结构是数据的组织与存储：从杂乱无章到井然有序
Algorithms + Data Structures = Programs
算法 + 数据结构 = 程序
算法设计的目标
- 用计算机解决相应的计算机问题
- 在规定的资源限制下将问题给解决
两个矛盾的目标 :
- To design an algorithm that is easy to understand, code and debug. （容易理解、编码、调试）
- To design an algorithm that makes efficient use of the computer’s resources. （有效利用计算机资源）
算法设计策略
Exhaustive search （穷举搜索）
Greedy method（贪心法）
Divide-and-conquer （分而治之）
Dynamic programming （动态规划）
Back tracking （回溯法）
Branch-and-bound （分支定界法）
Approximation algorithms (近似算法)
…
1.3 Different Classes of Problems 不同类型的问题
Good Algorithms Always Exist? 好的算法总是存在吗？
Some problems have good algorithms and can be solved quickly. Some may not have (we have not found good algorithms yet). 有些问题有很好的算法，可以快速解决。有些可能没有（我们还没有找到好的算法）。
What should we do for hard problems? 我们应该怎么处理棘手的问题？
-believing that there are some good algorithms for them? 相信有一些好的算法？
-believing that these problems are fundamentally different from easy problems? 相信这些问题与简单的问题有本质区别？
Computational complexity 计算复杂性
Classify the problems into different classes by measuring the minimum resource (running time, space, or others) required to solve the problem.
-
P: a solution can be solved in polynomial time. 可以在多项式时间内求解
-
NP: a solution can be checked in polynomial time. 可以在多项式的时间里验证一个解的问题（可以在多项式时间内验证一个解是否正确）
-
NPC: problems that may not have polynomial-time algorithms. 可能没有多项式时间内的解（通过证明没有多项式时间内的解）
Coping with NP-completeness 解决NPC问题
Q. Suppose I need to solve an NP-complete problem. What should I do? 如何需要解决一个NP完全问题？
A.
Sacrifice one of three desired features. 牺牲三个目标之一
i. Solve arbitrary instances of the problem. 求解问题的任意实例
ii. Solve problem to optimality. 得到最优解
iii. Solve problem in polynomial time. 在多项式时间内求解
Coping strategies. 应对策略
i. Design algorithms for special cases of the problem. 为问题的特殊情况设计算法
ii. Design approximation algorithms or heuristics. 设计近似算法或启发式算法
iii. Design algorithms that may take exponential time. 设计可能需要指数时间的算法