ALgoRIthms 算法 基础部分一: 逻辑:命题逻辑、谓词逻辑 2、集合:集合、函数 基础部分二 1、算法 2、数论 3、代数系统
A l g o r i t h m s 算 法 基础部分一： 1、逻辑：命题逻辑、谓词逻辑 2、集合：集合、函数 基础部分二： 1、算法 2、数论 3、代数系统
ALgoRIthms 算法 21算法 Algorithms
A l g o r i t h m s 算 法 2.1 算法 Algorithms
AInoPIthns 算法 算法是计算机科学中的一个最基本也是最重 要的概念之一。其基本原理可以追溯到自然数N。 用数学的方法来完整地描述自然数的是一个由皮 亚诺(G. Peano)定义的公理
A l g o r i t h m s 算 法 算法是计算机科学中的一个最基本也是最重 要的概念之一。其基本原理可以追溯到自然数N。 用数学的方法来完整地描述自然数的是一个由皮 亚诺（G. Peano）定义的公理
皮亚诺公理 ALgoRIthms 算法 (1)0∈N: (2)对每一个n∈N,唯一定义了一个自然数n’,n'称为n的后邻; (3)不同的自然数,其后邻也不同; (4)没有一个自然数的后邻是0; (5)如果有一个子集McN满足: ①0∈M;②n∈M时必n'∈M,则M=N 自然数全体N通过皮亚诺公理的五条公理组成。 这些公理缺一不可,其中性质(5)称为归纳公理,并指出了自然数 是满足公理(1)~(4)的最小集合
A l g o r i t h m s 算 法 皮亚诺公理 （1）0∈N； （2）对每一个n∈N，唯一定义了一个自然数n'，n'称为n的后邻； （3）不同的自然数，其后邻也不同； （4）没有一个自然数的后邻是0； （5）如果有一个子集MN满足： ① 0∈M；② n∈M时必n'∈ M, 则M = N 自然数全体N通过皮亚诺公理的五条公理组成。 这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数 是满足公理（1）~（4）的最小集合
DEFINITION 1 ALgoRIthms 算法 定义1如果一个对象部分地由自己所组成, 或者按它自己定义,则称为是递归的 ( Recursion)。 递归不仅是数学上的一种重要表达方法,也 是计算机科学中的一个基本概念
A l g o r i t h m s 算 法 DEFINITION 1 定义1 如果一个对象部分地由自己所组成， 或 者 按 它 自 己 定 义 ， 则 称 为 是 递 归 的 （Recursion）。 递归不仅是数学上的一种重要表达方法，也 是计算机科学中的一个基本概念
example ALgoRIthms 算法 自然数阶乘n!就是采用递归方法计算出来的。 令f(m)=m,则f(n)可以表示为 f(0)=1 f(n)=n f(n-1)
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
example ALgoRIthms 算法 菲波那契数, 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, 利用菲波那契数可以推算出兔子繁衍规律
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
AInoPIthns 算法 这类推算表达也称为递推,即通常从初值开始 计算。自然数表示也是一种递推。 递归与递推: 般地并不是所有的递归都能够用递推的方法 来表达。 有解 2、有终点
A l g o r i t h m s 算 法 这类推算表达也称为递推，即通常从初值开始 计算。自然数表示也是一种递推。 递归与递推： 一般地并不是所有的递归都能够用递推的方法 来表达。 1、有解 2、有终点
DEFINITION 2 ALgoRIthms 算法 算法( 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 算 法 DEFINITION 2. 算法（Algorithm）是通过一个有限的指 令序列集合对特定问题进行求解的一种计算执 行描述。 An algorithm is a finite set of precise instructions for performing a computation or for solving a problem
ALgoRIthms 一个算法通常应具有下列特征: (1)输入:一个算法具有零个或多个取自指定集合的输入值 (2)输出:对算法的每一次输入,算法具有一个或多个与输入值接联 系的输出值; (3)确定性:算法的每一个指令步骤都是明确的; (4)有限性:对算法的每一次输入,算法都必须在有限步骤(即有限 时间)内结束; (5)正确性:对每一次输入,算法应产生出正确的输出值; (6)通用性:算法的执行过程可应用于所有同类求解问题,而不是仅 适用于特殊的输入
A l g o r i t h m s 算 法 一个算法通常应具有下列特征： （1）输入：一个算法具有零个或多个取自指定集合的输入值； （2）输出：对算法的每一次输入，算法具有一个或多个与输入值接联 系的输出值； （3）确定性：算法的每一个指令步骤都是明确的； （4）有限性：对算法的每一次输入，算法都必须在有限步骤（即有限 时间）内结束； （5）正确性：对每一次输入，算法应产生出正确的输出值； （6）通用性：算法的执行过程可应用于所有同类求解问题，而不是仅 适用于特殊的输入
