数理逻辑-第二章-算法、整数和矩阵-整数和除法

1、数理逻辑Mathematical Logic 第二章 算法、整数和矩阵Chapter 2 Algorithm、Integer and Matrix复习算法复杂性算法的时间复杂性算法的空间复杂性算法的时间复杂性在输入规模一定的情况下用算法使用的运算次数来表示最坏情况分析平均情况分析复习算法的时间复杂性求集合最大元素2(n-1) O(n)线性搜索最坏情况 2n+2 O(n)平均情况 n+2 O(n)对分搜索最多需要2log n+2 O(logn)勿 死记硬背会 计算分析复习算法的时间复杂性常数复杂性、对数复杂性、线性复杂性、nlogn复杂性、多项式复杂性、指数复杂性、阶乘复杂性易处理的问题不易处理

2、的问题不可解的问题2.3 整数和除法The Integers and Division一、引言离散数学中涉及整数及其性质的这一部分内容属于数学中的数论。数论这门学科最初是从研究整数开始的，所以叫做整数论。后来整数论又进一步发展，就叫做数论了。确切的说，数论就是一门研究整数性质的学科。一、引言费尔马大定理、哥德巴赫猜想、孪生素数问题、 圆内整点问题、完全数问题高斯曾经说过“数学是科学的皇后,数论是数学中的皇后”。数论中的基本概念可除性、最大公约数、模运算等一、引言在2.4节结合算法及其复杂性介绍数论中的几个重要算法求两个正整数的最大公约数的算法用二进制展式做计算机运算的算法本节基于可除性，讲解素

3、数、算术基本定理、模运算以及模运算的应用（为文件分配内存地址、生成伪随机数、为信息加密和解密）二、除法定义1：如果a和b是整数，a0，若有整数c使b=ac，就说a整除b。在a整除b时，a是b的一个因子，b是a的倍数。符号a|b表示a整除b。当a不能整除b时写成ab。可被正整数d整除的整数-3d-2d-d0d2d3d二、除法例1：判断6|2, 3|7和3|12？例2：令n和d为正整数。不超过n的正整数中有多少个能被d整除？n/d 二、除法定理1：令a，b，c为整数。有如下结论：若a|b和a|c，则a|(b+c)；若a|b，那么对所有整数c都有a|bc；若a|b，b|c，则a|c。证：假定a|b和

4、a|c。从可除性定义知有整数s和t，使b=as和c=at。因此，b+c=as+at=a(s+t)。于是，a整除b+c。三、素数大于1的每个正整数都至少能被两个整数整除（1和它自身）。恰有两个不同的正整数因子的整数称为素数。定义2：大于1的正整数p称为素数，如果p仅有的正因子是1和p。大于1又不是素数的正整数称为合数。三、素数例3：判断7和9是素数？小于100的素数有哪些？（P113）定理2（算术基本定理）：任意一个正整数n(n1)可以唯一地表示为若干个素数的乘积。这里唯一的意义表示为不考虑素因子的次序。素数是构造正整数的积木。三、素数分解的存在性分解的唯一性，即若不考虑排列的顺序，正整数分解为

5、素数乘积的方式是唯一的。 例4：100=2255=2252641=641999=33337=3337三、素数如何证明一个给定的数是素数？定理3：如果n是合数，那么n必有一个小于或等于 的素因子。证：如果n是合数，它有一个因子a，使1a1，所以10,19和24不是两两互素的。五、最大公约数求两个整数最大公约数的另外一种方法：利用两个整数的素因子分解。假定两个全不为0的整数a和b的素因子分解为 每个指数都是非负整数，出现在a和b分解中的所有素数都包含在两个分解之中，必要时以0为指数出现五、最大公约数证明：P116例14：已知120和500的素因子分解分别为120=2335和500=2253，求它们

6、的最大公约数？解： 六、最小公倍数定义7：正整数a和b的最小公倍数是能被a和b整除的最小正整数。记作：lcm(a,b)。lcm: lowest common multiple素因子分解也可用于求两个整数的最小公倍数 六、最小公倍数例15 求233572和2433的最小公倍数解：定理5：令a和b为正整数，则 ab=gcd(a,b)lcm(a,b)七、模运算定义8：令a为整数，m为正整数。a mod m表示a被m除的余数。a mod m是使a=qm+r且0rm的整数r。例16：17mod5 -133mod9定义9：若a和b为整数而m为正整数，如果m整除a-b，就说a与b是模m同余，记作：ab(mo

7、d m)，否则记作ab(mod m)。七、模运算例17：判断17是否和5模6同余？24是否和14模6同余？解：由于6整除17-5=12，所以175(mod 6)24-14=10不能被6整除，所以2414(mod 6)定理6：令m为正整数，整数a和b模m同余的充分必要条件是存在整数k，使a=b+km。证明：P118七、模运算定理7：令m为正整数，若ab(mod m)， cd(mod m)，那么a+cb+d(mod m)以及acbd(mod m)。证明：P118例18：由于72(mod 5)和111(mod 5)，从定理7知： 183(mod 5) 772(mod 5)八、同余应用可以用同余为计算

8、机分配内存地址例19：散列（哈希）函数散列就是无需查找，直接用元素的查找键来确定元素索引的方法。实现了散列这种方法的函数就叫散列函数。散列函数接受查找键，产生一个称为散列表的数组中的元素的索引。八、同余应用设一个查找表S有n个数据元素S=R1, R2, , Rn。对于每个指定的Ri，设key是其关键字的值。则建立一个从Ri.key到Ri的存贮地址函数H为 H(Ri. key)=addr(Ri) 称H为哈希函数（Hash），函数值H(Ri. key)称 为哈希地址。按该方法所建立的表称为哈希表。八、同余应用散列函数的一般特性： 1 使冲突最小 2 使元素均匀分布在散列表里 3 计算要快。最常用的

9、散列函数之一是： h(k)=k mod mm是可供使用的内存地址的数目八、同余应用例如，当m=111时，064212848这个学生的记录分配到地址14，因为 h(064212848)=064515848 mod 111=14 类似的，由于 h(037149212)=037149212 mod 111=65由于散列函数不是一对一的（关键码的个数大于内存地址数），有可能多个纪录分配到同一内存地址。（冲突）八、同余应用消除冲突的一个方法是使用散列函数给出的但已被占用的地址后面第一个未被占用的地址。我们把15分配给107405723，因为h(107405723)= 107405723 mod 111=

10、14，14已经被占用。八、同余应用伪随机数用系统的方法产生的数不可能是真正随机的，就称为伪随机数最常用的产生伪随机数的过程称为线性同余法xn+1=(axn+c) mod mP120九、密码学最重要的同余应用之一涉及研究信息保密的密码学最早使用密码的例子之一是凯撒他把每个字母在字母表中往下移动3位以获得保密信息（最后三位移到最前）字母b移到e，字母x移到a用数学来表示凯撒的加密过程九、密码学用0表示a，25表示z凯撒的加密过程可以用函数f表示，f(p)=(p+3)mod26，其中0p25，在加密信息中，p代表的字母用f(p)代表的字母代替。“red” “uhg”例21：“meet you in

11、the park”，用凯撒密码加密。“PHHWBRXLQWHKSDUN”九、密码学要把凯撒密码的加密信息还原为原来的信息，需要使用f的反函数f-1。f-1(p)=(p-3)mod26，每个字母向前移3位，最前3个字母移到最后。从加密信息恢复成原信息的过程称为解密。九、密码学凯撒密码的推广把每个字母移动k位，于是f(p)=(p+k)mod26，这样的密码称为移位密码，解码用f-1(p)=(p-k)mod26来完成凯撒的方法和移位密码不能提供高度安全，稍稍提高一点安全性的一种办法是使用f(p)=(ap+b)mod26，其中a和b为整数。九、密码学例22：若用f(p)=(7p+3)mod26加密，用什么字母来代替k？解：10代表k，f(10)=(710+3)mod26=73 mod 26=21，21代表v，所以，在加密信息中，用v代表k。更复杂一些的加密方法是用一段字母取代另一段字母。小结素数合数算术基本定