离散数学-算法.ppt

离散数学
黄晓宇
HuangSir@
1
本讲内容
算法简介
算法例子
算法分析
递归算法
2
算法-一组有限的指令集合
输入:算法接受输入。
输出:算法产生输出。
精确性:步骤被精确描述。
确定性:每步执行的结果是惟一的,且只依赖于输入和前面步骤执行的结果。
有限性:算法可以终止,也就是在执行有限多条指令后停止。
正确性:算法生成的输出结果是正确的,也就是算法可以正确地求解问题。
一般性:算法适应于一组输入。
3
算法示例-三数排序
1. large = a.
2. If b > large, then large = b.
3. If c > large , then large = c.
这个算法的思想是对这些数一个一个地检查,将所见的最大数赋值给变量large。在算法停止时,large 就等于这三个数中最大的了
4
跟踪
a=1, b=5, c=3
a=1, b=5, c=9
1. large = a.
2. If b > large, then large = b.
3. If c > large , then large = c.
x=
5
算法正确性证明
算法描述:在数列s1,..., sn 中找出最大的一个。
输入:s, n
输出:large(序列s 中的最大值)
max (s, n){
large = s1
for i = 2 to n
if (si > large)
large = si
return large
}
6
算法正确性证明(二)
循环不变式:在循环的每次迭代前后均为真的谓词
large=max{s1,..., sn }
7
算法正确性证明(三)-归纳
平凡情况(i = 1)large 是序列中的最大值。
假设large是子序列s1,..., si 中的最大值。
假如i < n 成立,i 变成i + 1。
(1)si+1 > large,赋值large =si+1;
(2)si+1 ≤ large,算法不改变large 的值。
因此, large=max{s1,..., sn } 是一个循环不变量。
for 循环在i = n 时结束,算法正确。
8
文本搜索
假设给定一个文本t(例如一个文档),在t 中找出特定词组p 首次出现的位置。
A
B
C
A
B
C
D
E
A
D
……
E
D
C
E
D
C
E
D
C
E
D
C
9
text_search (p, m, t, n){
for i = 1 to n - m + 1{
j = 1;
while(t i+j-1 == p j){
j = j + 1;
if(j > m) return j;
}
}
return 0
}
10