《算法导论》PPT课件

Ford-Fulkerson终止时的流有什么性质？
39
最大流与最小割

定理7.9 如果f是使得剩余图Gf中没有s-t 路径的一个s-t流，那么在G中存在一个 s-t割(A*,B*)使得v(f)=(A*,B*).因此，f有 G中任何流的最大值，且(A*,B*)有G中任 何s-t割的最小容量。 最大流最小割定理. [Ford-Fulkerson 1956] 最大流的值等于最小割
5
最大流问题

1. 2.
流的定义： s-t流是一个函数f,它把每条边e映射到 + E → R 一个非负实数f: ,值f(e)表示由边 e携带的流量，一个流f必须满足下面两 个性质： (容量条件)0<=f(e)<=Ce (守恒条件)除了s,t外，对每个结点v,满 足 ∑ f ( e ) = ∑ f ( e)
3
7.1 最大流问题
9 9 9

用图对交通网络建模 比如公路系统：边是公路，结点交叉路口 比如计算机网络：边是链接线，结点是开关 比如管网：边是输送些体的管道，结点是管道 连接点 抽象出来的要素： 边上的容量； 源点；终点；交通量通过边运送
4
最大流问题

流网络 有向图G=(V,E) 每条边关联一个容量，非负数Ce. 存在单一源点s, 以及单一汇点t

42
最大流与最小割
设流f没有增广路径. 定义集合A 是剩余图Gf中从源点s可达顶点集合. 根据定义，那么s ∈ A；终点 t ∉ A, ∈ B. 如果e=(u,v), u∈A,v∈B,那么f(e)=c(e); 如果e’=(u’,v’), u’∈B,v’∈A,那么f(e’)=0.

v( f ) = =
24

23
带权的区间调度


预处理：算法实现的过程中先对开始时 间和结束时间排序，便于后面的处理 一些编程语言，如Lisp，就可以自动实现 备忘录的功能(built-in support for memorization)，因而有好的执行效率； 但是在其他的一些语言中，比如Java， 就没有实现这一功能。
7
带权的区间调度
不同区间的影响是不一样的
a b c d e f g h
0 1 2 3 4 5 6 7 8 9 10 11
Time
8
带权的区间调度

贪心算法情形下，区间的权重可以看成都是1 对于区间权重不同的情形，贪心算法就失效了
weight = 999
b
weight = 1
a Time
解决之道：更加灵活的调度策略

对于带权区间调度问题，我们可以不使 用备忘录式的递归方法，而通过迭代算 法直接计算M[]中的项。
,
Input: n, s1,…,sn
f1,…,fn
,
v1,…,vn
Sort jobs by finish times so that f1 ≤ f2 ≤ ... ≤ fn. Compute p(1), p(2), …, p(n) Iterative-Compute-Opt { M[0] = 0 for j = 1 to n M[j] = max(vj + M[p(j)], M[j-1]) } 自底向上
19
带权的区间调度

递归的备忘录形式 为了避免上面的重复计算，我们把中间 计算的结果存储起来，需要的时候先查 找是否计算过 下面将用到一个数组M[0…n]保存中间计 算结果
20

Algorithm description
• Specification:
– Natural language, computer program, hardware design
• An algorithm can be specified in English | Chinese, as a computer program, or even as a hardware design.
• Know the strengths and limitations of data structures • Hard problems: NP-complete, efficient algorithm, good | best
1.3 Algorithms as a technology
• Algorithms Exercise & Mark
• See 《算法分析与设计》课程介绍与要求.ppt
Exercises for Chapter 1
• Exercises: 1.2‐3: Find the smallest value of n… • Problems 1‐1: Comparison of running times…
Exercises for Chapter 1
• 1. 1‐3. Select a data structure that you have seen previously, and discuss its strengths and limitations. • 1.1‐4 How are the shortest‐path and traveling‐ salesman problems given above similar? How are • they different? • 1.1‐5 Come up with a real‐world problem in which only the best solution will do. Then come up with one in which a solution that is "approximately" the best is good enough.

15.4 Longest common subsequence LCS Problem
Given two sequences X= <x1, x2, ..., xm> and Y= <y1, y2, ..., yn>, how to find a maximum-length common subsequence of X and Y .
（设zk≠xm, 令Z’= <z1 , ... , zk , xm>，则 Z’ 是 X 和 Y 的相同子序列，且 length(Z’)=k+1 ⇒ Z’ 是比 Z 更长的子序列 ⇒ 与题设 Z 是LCS矛盾）
Now show Zk-1 is an LCS of Xm-1 and Yn-1. Clearly, it’s a CS. Now suppose there exists a CS W of Xm-1 and Yn-1 that’s longer than Zk-1 ⇒length(W) ≥ k. Make subsequence W’ by appending xm to W. W’ is CS of X and Y , length(W’)≥k+1 ⇒ contradicts Z being an LCS.
举出 X 的所有子序列，逐项核查这些子序列是否为 Y 的子序列）
Each subsequence of X corresponds to a subset of the
indices {1, 2, ..., m} of X. There are 2m subsequences of
X . Exponential time, impractical for long sequences.

computing
“计算机算法的圣经”
Bibliography
《Introduction to Algorithms》(Second Edition),
T. H. Cormen, C. E. Leiserson, R. L. Rivest (2002, Turing Award),
The MIT Press
}
利用此界面使 方法sum通用化
18
第18页/共25页
1.3 描述算法
6.通用方法
（2）parable 界面 Java的Comparable 界面中惟一的方法头compareTo用于比较
2个元素的大小。例如pareTo(y) 返回x-y的符号，当x<y时返回负数，当x=y时返回0，当x>y时返 回正数。 （3）Operable 界面
8
第8页/共25页
1.2 表达算法的抽象机制
2.抽象数据类型
抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有：
（1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
期末闭卷考试：
about 70%
课程安排
课堂讲解：基本理论讲解，基本方法的介绍分析
上机实践：基本习题和经典习题的上机实践
第4页4 /共25页
主要内容介绍

analysis: n2 multiplications and at most n2-1 additions (加法). So, T(n)=O(n2).
6

Exam2 Multiplication of two numbers （整数相乘） two n-digit numbers X and Y, Complexity(X × Y) = ? � Divide and Conquer algorithm Let X=ab Y=cd where a, b, c and d are n/2 digit numbers, e.g. 1364=13×102+64. Let m= n/2. Then XY = (10ma+b)(10mc+d) =102mac+10m(bc+ad)+bd
11

Exam3 Multiplication of two matrices （矩阵相乘） two n×n matrices A and B, Complexity(C=A×B) = ?
�
Divide and conquer (Strassen Algorithm) An n×n matrix can be divided into four n/2×n/2 matrices, ⎡ A11 A12 ⎤ ⎡ B11 B12 ⎤ ⎡ C11 C12 ⎤ A= ⎢ ,B= ⎢ ,C= ⎢ ⎥ ⎥ ⎥ ⎣A 21 A 22 ⎦ ⎣B21 B22 ⎦ ⎣C21 C 22 ⎦
12
Complexity analysis: Totally, 7 multiplications, and 18 additions. T(1)=1, T(n) = 7T( ⎡n/2⎤ )+ cn2. Applying Master Theorem,