第一章 算法与问题:介绍算法的概念与性质、问题的求解过程、问题变换的目的和类型。算法与程序、算法与问题的区别和内在联系。1.1稳定匹配问题:引入稳定匹配问题,介绍问题的求解过程[判断题]一个问题的同一实例可以有不同的表示形式
1.2Hi!什么是算法?:介绍算法的概念与性质、算法与程序、算法与问题的区别和内在联系。
1.3大学入学申请问题:引入大学入学申请问题,介绍问题变换的目的和类型
对
错
答案:√
[判断题]同一数学模型使用不同的数据结构会有不同的算法,有效性有很大差别。
对
错
答案:√
错
对
答案:错
输入
输出
确定性
有穷性
答案:有穷性
(3)(1)(4)(5)(2)
(3)(4)(1)(5)(2)
(3)(1)(5)(4)(2)
(1)(2)(3)(4)(5)
答案:(3)(1)(5)(4)(2)
算法是一种计算方法,对问题的每个实例计算都能得到正确答案。
同一问题可能有几种不同的算法,解题思路和解题速度也会显著不同。
如果一个算法能应用于问题的任意实例,并保证得到正确解答,称这个算法解答了该问题。
证明算法不正确,需要证明对任意实例算法都不能正确处理。
答案:证明算法不正确,需要证明对任意实例算法都不能正确处理。
程序总是在有穷步的运算后终止。
程序是算法用某种程序设计语言的具体实现。
算法的每一步骤必须要有确切的含义,必须是清楚的、无二义的。
算法是一个过程,计算机每次求解是针对问题的一个实例求解。
答案:算法的每一步骤必须要有确切的含义,必须是清楚的、无二义的。程序是算法用某种程序设计语言的具体实现。
最大团
稳定匹配问题
区间调度问题
最小顶点覆盖
答案:最大团最小顶点覆盖
完美匹配
稳定匹配
最大匹配
没有不稳定配对
答案:稳定匹配完美匹配没有不稳定配对最大匹配
(1)
(5)
(2)
(4)
(3)
答案:(5)
logn
n
nlogn
n^2
答案:n