A l g o r i t h m s
算法基础部分一：
1、逻辑,命题逻辑、谓词逻辑
2、集合,集合、函数基础部分二：
1、算法
2、数论
3、代数系统
A l g o r i t h m s
算法
2.1 算法
Algorithms
A l g o r i t h m s
算法算法是计算机科学中的一个最基本也是最重要的概念之一。其基本原理可以追溯到自然数 N。
用数学的方法来完整地描述自然数的是一个由皮亚诺（ G,Peano）定义的公理。
A l g o r i t h m s
算法皮亚诺公理
（ 1） 0∈ N；
（ 2） 对每一个 n∈ N,唯一定义了一个自然数 n',n' 称为 n的后邻；
（ 3） 不同的自然数,其后邻也不同；
（ 4） 没有一个自然数的后邻是 0；
（ 5） 如果有一个子集 M?N满足：
① 0∈ M； ② n∈ M时必 n'∈ M,则 M = N
自然数全体 N通过皮亚诺公理的五条公理组成。
这些公理缺一不可，其中性质（ 5）称为归纳公理，并指出了自然数是满足公理（ 1） ~（ 4）的最小集合。
A l g o r i t h m s
算法
DEFINITION 1
定义 1 如果一个对象部分地由自己所组成,
或 者 按 它 自 己 定 义,则 称 为 是 递归 的
（ Recursion） 。
递归不仅是数学上的一种重要表达方法，也是计算机科学中的一个基本概念。
A l g o r i t h m s
算法自然数阶乘 n!就是采用递归方法计算出来的 。
令 f (n) = n!,则 f(n)可以表示为：
f (0) = 1
f (n) = n·f (n–1) n>0
example
A l g o r i t h m s
算法菲波那契数,
F(0) = 1,F(1) = 1
F(n) = F (n–1) + F (n–2) n>1
由上述公式,我们得到：
F (2) = 2,F (3) = 3,F (4) = 5，
F (5) = 8,F (6) = 13,……
利用菲波那契数可以推算出兔子繁衍规律。
example
A l g o r i t h m s
算法这类推算表达也称为 递推,即通常从初值开始计算 。 自然数表示也是一种递推 。
递归与递推：
一般地并不是所有的递归都能够用递推的方法来表达 。
1,有解
2,有终点
A l g o r i t h m s
算法
DEFINITION 2,
算法（ Algorithm） 是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。
An algorithm is a finite set of precise
instructions for performing a computation or
for solving a problem.
A l g o r i t h m s
算法一个算法通常应具有下列特征：
（ 1） 输入：一个算法具有零个或多个取自指定集合的输入值；
（ 2） 输出：对算法的每一次输入,算法具有一个或多个与输入值接联系的输出值；
（ 3） 确定性：算法的每一个指令步骤都是明确的；
（ 4） 有限性：对算法的每一次输入,算法都必须在有限步骤 （ 即有限时间 ） 内结束；
（ 5） 正确性：对每一次输入,算法应产生出正确的输出值；
（ 6） 通用性：算法的执行过程可应用于所有同类求解问题,而不是仅适用于特殊的输入 。
A l g o r i t h m s
算法算法的概念与程序十分相似，但实际上有很大不同。程序并不都满足算法所要求的上述特征，例如有限性特征。算法代表了对特定问题的求解，而程序则是算法在计算机上的实现。因此算法也常常称为是一个 能行过程 。一个函数如果可以用一个算法来计算，
那么我们称该函数是 能行可计算 的。
A l g o r i t h m s
算法
example
算法的一个精典的例子：
在正整数中，给定两个正整数 x和 y，
求它们的最大公因子 GCD（ x,y）的 欧几里德算法 （ Euclid）
A l g o r i t h m s
算法其中 x,y为初始输入值,输出值在 y中 。 由于 x,y是正整数,所以算法在有限时间内结束 。 例如与 x=90,
y=924,算法的执行过程描述为：
924=10× 90+24
90=3× 24+18
24=1× 18+6
18=3× 6
所以,GCD（ 90,924） =6。
A l g o r i t h m s
算法从命题逻辑的角度来考虑,欧几里德算法也可称为一个判定过程 。 对于给定的 x,y，
该过程可以判定,x和 y是互质的,（ 即除了 1
之外,x和 y没有此因子 ） 这样一个具有真假意义的命题的真值 。
A l g o r i t h m s
算法算法的计算量问题
A l g o r i t h m s
算法
Let f and g be functions from the set of R or I to
the set of R,Call that f(x) is O(g(x)) if there are
constants C and k such that
|f(x)| <= C|g(x)|
Wherever x > k.
Read as,f(x) is big-oh of g(x)”
O:Landau symbol
Definition 3
A l g o r i t h m s
算法关于 C和 k 的说明：
1,不唯一
2、是有序对作为元素的一个无限集
3、尽可能小例,f(x)=x2+2x+1
A l g o r i t h m s
算法
f(x)=x2+2x+1 g(x)= x2
f(x) is O(g(x)) and g(x) is O(f(x))
Example 2,
7 x2 is O(x3)?
Example 3.
x3 is O(7 x2 )?
A l g o r i t h m s
算法
Theorem 1
If f(x)=an xn +an-1 xn-1+…+a 1 x1+a0
where ai?R,i=0,1,…,n
Then f(x) is O(xn)
Theorem 1
A l g o r i t h m s
算法
Theorem 2
If f1(x) is O(g1(x)),f2(x) is O(g2(x)),
Then (f1 + f2 )(x) is O(max(g1(x),g2(x)) )
Theorem 2
A l g o r i t h m s
算法
Corollary 1
If f1(x) is O(g(x)),f2(x) is O(g(x)),
Then (f1 + f2 )(x) is O(g(x) )
Theorem 2
A l g o r i t h m s
算法
Theorem 3
If f1(x) is O(g1(x)),f2(x) is O(g2(x)),
Then (f1 f2 )(x) is O(g1(x)g2(x) )
Theorem 3
A l g o r i t h m s
算法
Let f and g be functions from the set of R or I to
the set of R,Call that f(x) is?(g(x)) if there are
constants C and k such that
|f(x)| >= C|g(x)|
Wherever x > k.
Read as,f(x) is big-omega of g(x)”
Definition 4
A l g o r i t h m s
算法
Let f and g be functions from the set of R
or I to the set of R,Call that f(x) is?(g(x))
if f(x) is O(g(x)) and f(x) is?(g(x))
Read as,f(x) is big-theta of g(x)”
“f(x) is of order g(x)”
Definition 5
A l g o r i t h m s
算法
Theorem 4
If f(x)=an xn +an-1 xn-1+…+a 1 x1+a0
where ai?R,i=0,1,…,n
with an? 0
Then f(x) is?(xn)
Theorem 4
A l g o r i t h m s
算法算法的计算复杂性
(computational complexity)：
问题的规模 n
空间复杂度 (space complexity):S(n)
时间复杂度 (time complexity):T(n)
A l g o r i t h m s
算法常用的算法复杂性分类：
O(1),constant complexity
O(log n),logarithmic complexity
O(n),linear complexity
O(n log n),n log n complexity linear
O(nb),polynomial complexity polynomial
O(bn),exponential complexity(b>1) exponential
O(n!),factorial complexity
A l g o r i t h m s
算法小结一、算法的概念
Peano公理,递归，递推,可计算，特征二、算法复杂性表达形式，分类
A l g o r i t h m s
算法进一步的思考：
P问题与 NP问题
A l g o r i t h m s
算法练习题
pp90 2,15,16
算法基础部分一：
1、逻辑,命题逻辑、谓词逻辑
2、集合,集合、函数基础部分二：
1、算法
2、数论
3、代数系统
A l g o r i t h m s
算法
2.1 算法
Algorithms
A l g o r i t h m s
算法算法是计算机科学中的一个最基本也是最重要的概念之一。其基本原理可以追溯到自然数 N。
用数学的方法来完整地描述自然数的是一个由皮亚诺（ G,Peano）定义的公理。
A l g o r i t h m s
算法皮亚诺公理
（ 1） 0∈ N；
（ 2） 对每一个 n∈ N,唯一定义了一个自然数 n',n' 称为 n的后邻；
（ 3） 不同的自然数,其后邻也不同；
（ 4） 没有一个自然数的后邻是 0；
（ 5） 如果有一个子集 M?N满足：
① 0∈ M； ② n∈ M时必 n'∈ M,则 M = N
自然数全体 N通过皮亚诺公理的五条公理组成。
这些公理缺一不可，其中性质（ 5）称为归纳公理，并指出了自然数是满足公理（ 1） ~（ 4）的最小集合。
A l g o r i t h m s
算法
DEFINITION 1
定义 1 如果一个对象部分地由自己所组成,
或 者 按 它 自 己 定 义,则 称 为 是 递归 的
（ Recursion） 。
递归不仅是数学上的一种重要表达方法，也是计算机科学中的一个基本概念。
A l g o r i t h m s
算法自然数阶乘 n!就是采用递归方法计算出来的 。
令 f (n) = n!,则 f(n)可以表示为：
f (0) = 1
f (n) = n·f (n–1) n>0
example
A l g o r i t h m s
算法菲波那契数,
F(0) = 1,F(1) = 1
F(n) = F (n–1) + F (n–2) n>1
由上述公式,我们得到：
F (2) = 2,F (3) = 3,F (4) = 5，
F (5) = 8,F (6) = 13,……
利用菲波那契数可以推算出兔子繁衍规律。
example
A l g o r i t h m s
算法这类推算表达也称为 递推,即通常从初值开始计算 。 自然数表示也是一种递推 。
递归与递推：
一般地并不是所有的递归都能够用递推的方法来表达 。
1,有解
2,有终点
A l g o r i t h m s
算法
DEFINITION 2,
算法（ Algorithm） 是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。
An algorithm is a finite set of precise
instructions for performing a computation or
for solving a problem.
A l g o r i t h m s
算法一个算法通常应具有下列特征：
（ 1） 输入：一个算法具有零个或多个取自指定集合的输入值；
（ 2） 输出：对算法的每一次输入,算法具有一个或多个与输入值接联系的输出值；
（ 3） 确定性：算法的每一个指令步骤都是明确的；
（ 4） 有限性：对算法的每一次输入,算法都必须在有限步骤 （ 即有限时间 ） 内结束；
（ 5） 正确性：对每一次输入,算法应产生出正确的输出值；
（ 6） 通用性：算法的执行过程可应用于所有同类求解问题,而不是仅适用于特殊的输入 。
A l g o r i t h m s
算法算法的概念与程序十分相似，但实际上有很大不同。程序并不都满足算法所要求的上述特征，例如有限性特征。算法代表了对特定问题的求解，而程序则是算法在计算机上的实现。因此算法也常常称为是一个 能行过程 。一个函数如果可以用一个算法来计算，
那么我们称该函数是 能行可计算 的。
A l g o r i t h m s
算法
example
算法的一个精典的例子：
在正整数中，给定两个正整数 x和 y，
求它们的最大公因子 GCD（ x,y）的 欧几里德算法 （ Euclid）
A l g o r i t h m s
算法其中 x,y为初始输入值,输出值在 y中 。 由于 x,y是正整数,所以算法在有限时间内结束 。 例如与 x=90,
y=924,算法的执行过程描述为：
924=10× 90+24
90=3× 24+18
24=1× 18+6
18=3× 6
所以,GCD（ 90,924） =6。
A l g o r i t h m s
算法从命题逻辑的角度来考虑,欧几里德算法也可称为一个判定过程 。 对于给定的 x,y，
该过程可以判定,x和 y是互质的,（ 即除了 1
之外,x和 y没有此因子 ） 这样一个具有真假意义的命题的真值 。
A l g o r i t h m s
算法算法的计算量问题
A l g o r i t h m s
算法
Let f and g be functions from the set of R or I to
the set of R,Call that f(x) is O(g(x)) if there are
constants C and k such that
|f(x)| <= C|g(x)|
Wherever x > k.
Read as,f(x) is big-oh of g(x)”
O:Landau symbol
Definition 3
A l g o r i t h m s
算法关于 C和 k 的说明：
1,不唯一
2、是有序对作为元素的一个无限集
3、尽可能小例,f(x)=x2+2x+1
A l g o r i t h m s
算法
f(x)=x2+2x+1 g(x)= x2
f(x) is O(g(x)) and g(x) is O(f(x))
Example 2,
7 x2 is O(x3)?
Example 3.
x3 is O(7 x2 )?
A l g o r i t h m s
算法
Theorem 1
If f(x)=an xn +an-1 xn-1+…+a 1 x1+a0
where ai?R,i=0,1,…,n
Then f(x) is O(xn)
Theorem 1
A l g o r i t h m s
算法
Theorem 2
If f1(x) is O(g1(x)),f2(x) is O(g2(x)),
Then (f1 + f2 )(x) is O(max(g1(x),g2(x)) )
Theorem 2
A l g o r i t h m s
算法
Corollary 1
If f1(x) is O(g(x)),f2(x) is O(g(x)),
Then (f1 + f2 )(x) is O(g(x) )
Theorem 2
A l g o r i t h m s
算法
Theorem 3
If f1(x) is O(g1(x)),f2(x) is O(g2(x)),
Then (f1 f2 )(x) is O(g1(x)g2(x) )
Theorem 3
A l g o r i t h m s
算法
Let f and g be functions from the set of R or I to
the set of R,Call that f(x) is?(g(x)) if there are
constants C and k such that
|f(x)| >= C|g(x)|
Wherever x > k.
Read as,f(x) is big-omega of g(x)”
Definition 4
A l g o r i t h m s
算法
Let f and g be functions from the set of R
or I to the set of R,Call that f(x) is?(g(x))
if f(x) is O(g(x)) and f(x) is?(g(x))
Read as,f(x) is big-theta of g(x)”
“f(x) is of order g(x)”
Definition 5
A l g o r i t h m s
算法
Theorem 4
If f(x)=an xn +an-1 xn-1+…+a 1 x1+a0
where ai?R,i=0,1,…,n
with an? 0
Then f(x) is?(xn)
Theorem 4
A l g o r i t h m s
算法算法的计算复杂性
(computational complexity)：
问题的规模 n
空间复杂度 (space complexity):S(n)
时间复杂度 (time complexity):T(n)
A l g o r i t h m s
算法常用的算法复杂性分类：
O(1),constant complexity
O(log n),logarithmic complexity
O(n),linear complexity
O(n log n),n log n complexity linear
O(nb),polynomial complexity polynomial
O(bn),exponential complexity(b>1) exponential
O(n!),factorial complexity
A l g o r i t h m s
算法小结一、算法的概念
Peano公理,递归，递推,可计算，特征二、算法复杂性表达形式，分类
A l g o r i t h m s
算法进一步的思考：
P问题与 NP问题
A l g o r i t h m s
算法练习题
pp90 2,15,16
