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

1、数理逻辑Mathematical Logic 第二章 算法、整数和矩阵Chapter 2 Algorithm、Integer and Matrix复习素数合数算术基本定理每个大于1的正整数都可以唯一地表示为素数的乘积。如果n是合数，那么必有一个小于或等于根号n的素因子。判断素数（101）整数的素因子分解（7007）复习判断整数互素或两两互素利用素因子分解求最大公约数和最小公倍数ab=gcd(a,b)lcm(a,b)模运算a与b是模m同余同余和加法乘法的关系思考题判断下列各数是否为素数，如果不是，它的素因子分解是什么？131 素数471931111132.4 整数和算法Integers and

2、Algorithms一、欧几里德算法用整数的素因子分解求两个整数最大公约数的算法效率不高；因为求素因子分解消耗太多时间；欧几里德算法（辗转相除法）效率更高；以古希腊数学家欧几里德的名字命名，已有2000多年的历史。一、欧几里德算法以gcd(91,287)为例用两数中的小的去除大的，即91除287，287=913+14；91和287的任何公约数必定也是14的因数，而且91和14的公约数也必定是287的因数，所以，287和91的最大公约数和91与14的最大公约数相同；gcd(91,287)简化为gcd(91,14)一、欧几里德算法以gcd(91,287)为例再用14去除91，91=146+7；又转

3、化为求gcd(14,7)；继续用7去除14，14=72；因为7整除14，所以gcd(14,7)=7；因此，gcd(287,91)=gcd(91,14)=gcd(14,7)=7。一、欧几里德算法用辗转相除把求两个正整数最大公约数的问题化简为求两个较小整数的最大公约数，直到两个整数中的一个为0。引理1：令a=bq+r，其中a,b,q,r为整数，则gcd(a,b)=gcd(b,r)。证明：P125一、欧几里德算法例：用欧几里德算法求414和662的最大公约数解：辗转使用除法算法：662=4141+248414=2481+166248=1661+82166=822+282=241因此，gcd(414,

4、662)=22是最后一个非0余数。一、欧几里德算法伪码描述Procedure gcd (a,b: 正整数)x:=a; y:=bwhile y0 y为余数begin r:=x mod y x:=y y:=rend gcd(a,b)是x二、整数表示日常生活中都用十进制符号表示整数；965=9102+610+5；计算机常用的还有2进制、8进制和16进制；我们可以用1以外的任何正整数为基数来表示整数。二、整数表示定理1：令b为大于1的正整数。那么如果n是个正整数，就可以唯一地表示为下面的形式：n=akbk+ak-1bk-1+a1b+a0 ，其中k是非负整数，a0,a1,ak是小于b的非负整数，ak0。

5、定理1中给出的n的表示称为n的以b为基数的展开。n的基数b展开表示为(ak,a1,a0)b；(245)8表示282+48+5=165。二、整数表示以2为基数就得到整数的二进制展开；在二进制符号中每位数字或0，或1；整数的二进制展开就是位串；计算机用二进制展开表示整数并做整数算术运算。二、整数表示例：以(101011111)2为二进制展开的整数，其十进制展开是什么？解： (101011111)2=28+26+24+23+22+2+1=35116是计算机科学中使用的另一个基数通常使用的数字是：0,1,2,9, A, B,C, D, E, F0,1,2,9,10,11,12,13,14,15二、整数

6、表示例：十六进制展开(2AE0B)16的十进制展开是什么？(2AE0B)16=2164+10163+14162+016+11=(175627)10十六进制数可以用4个字位表示一个字节是8位所以，一个字节可以用两个十六进制数表示。二、整数表示例 (1110 0101)2(E5)16整数n的基数b展开的算法：首先，用b除n得到商和余数，n=bq0+a0，0a0b；余数就是n的基数b展开的最右边一个数字；下一步用b除q0；q0=bq1+a1，0a1 3040304010=12000 一共36000次A1(A2A3)204010=8000 - 2010302010=6000 一共14000次四、矩阵的

7、转置和幂定义：n阶单位矩阵是nn矩阵In=ij，其中ij=1若i=j，ij=0若ij。四、矩阵的转置和幂用大小合适的单位矩阵乘一个矩阵，不改变该矩阵。若A是mn矩阵，则有：AIn=ImA=A。方阵的幂：若A是nn矩阵，则有：A0=InAr=AAAA（r个）四、矩阵的转置和幂定义：令A=aij为mn矩阵。A的转置，用At表示，是交换A的行和列得到的nm矩阵。若At=bij，则bij=aji，i=1,2,n，j=1,2,m。例：四、矩阵的转置和幂定义：若方阵A和它的转置相等，即A= At，则A称为对称矩阵。A=aij为对称矩阵的条件是：对所有i，j，1in，1jn，aij=aji。方阵对主对角线对

8、称四、矩阵的转置和幂五、0-1矩阵元素非0即1的矩阵称为0-1矩阵。0-1矩阵常用来表示离散结构。使用这些结构的算法的基础是以0-1矩阵做布尔运算（和）。五、0-1矩阵定义：令A=aij和B=bij为mn阶0-1矩阵。A和B的并，用AB表示，是个0-1矩阵，其(i,j)元素为aijbij。A和B的交，用AB表示，是个0-1矩阵，其(i,j)元素为aijbij。五、0-1矩阵例：五、0-1矩阵定义：令A=aij为mk阶0-1矩阵，B=bij为kn阶0-1矩阵。A和B的布尔乘积，用AB表示，是mn矩阵cij，其中：类似于两个矩阵的普通乘积，但要用代替加法，用代替乘法。五、0-1矩阵例：五、0-1矩

9、阵伪码：五、0-1矩阵定义：令A为0-1方阵，r为正整数。A的r次布尔幂是r个A的布尔乘积。A的r次布尔幂用Ar表示。Ar=AAAA（r个）A0=In五、0-1矩阵例：Ar=A5对所有大于或等于5的正整数n均成立五、0-1矩阵例：若A和B为nn阶0-1矩阵，计算AB需要做多少次字位运算？解： AB有n2个元素；用上述算法，需要n次和n次来计算AB的一个元素；因此，需要2n次字位运算；所以计算AB需要2n3次字位运算。五、0-1矩阵实例蛋白质互作网络（Protein-Protein Interaction Network）基因调控网络（Gene Regulatory Network） 五、0-1矩阵实例Ar表示两点间长度为r的通路小结欧几里德算法辗转相除法二进制八进制十六进制n的基数b展开小结整数运算算法表示为二进制展开的整数的加法加法的算法复杂性表示为二进制展开的整数的乘法乘法的算法复杂性小结矩阵的加法和乘法矩阵运算的伪码描述矩阵的转置和幂0-1矩阵ABABAB（布尔乘积）掌握