數(shù)理邏輯-第二章-算法、整數(shù)和矩陣-矩陣

1、數(shù)理邏輯Mathematical Logic 第二章 算法、整數(shù)和矩陣Chapter 2 Algorithm、Integer and Matrix復(fù)習(xí)素數(shù)合數(shù)算術(shù)基本定理每個大于1的正整數(shù)都可以唯一地表示為素數(shù)的乘積。如果n是合數(shù)，那么必有一個小于或等于根號n的素因子。判斷素數(shù)（101）整數(shù)的素因子分解（7007）復(fù)習(xí)判斷整數(shù)互素或兩兩互素利用素因子分解求最大公約數(shù)和最小公倍數(shù)ab=gcd(a,b)lcm(a,b)模運算a與b是模m同余同余和加法乘法的關(guān)系思考題判斷下列各數(shù)是否為素數(shù)，如果不是，它的素因子分解是什么？131 素數(shù)471931111132.4 整數(shù)和算法Integers and

2、Algorithms一、歐幾里德算法用整數(shù)的素因子分解求兩個整數(shù)最大公約數(shù)的算法效率不高；因為求素因子分解消耗太多時間；歐幾里德算法（輾轉(zhuǎn)相除法）效率更高；以古希臘數(shù)學(xué)家歐幾里德的名字命名，已有2000多年的歷史。一、歐幾里德算法以gcd(91,287)為例用兩數(shù)中的小的去除大的，即91除287，287=913+14；91和287的任何公約數(shù)必定也是14的因數(shù)，而且91和14的公約數(shù)也必定是287的因數(shù)，所以，287和91的最大公約數(shù)和91與14的最大公約數(shù)相同；gcd(91,287)簡化為gcd(91,14)一、歐幾里德算法以gcd(91,287)為例再用14去除91，91=146+7；又轉(zhuǎn)

3、化為求gcd(14,7)；繼續(xù)用7去除14，14=72；因為7整除14，所以gcd(14,7)=7；因此，gcd(287,91)=gcd(91,14)=gcd(14,7)=7。一、歐幾里德算法用輾轉(zhuǎn)相除把求兩個正整數(shù)最大公約數(shù)的問題化簡為求兩個較小整數(shù)的最大公約數(shù)，直到兩個整數(shù)中的一個為0。引理1：令a=bq+r，其中a,b,q,r為整數(shù)，則gcd(a,b)=gcd(b,r)。證明：P125一、歐幾里德算法例：用歐幾里德算法求414和662的最大公約數(shù)解：輾轉(zhuǎn)使用除法算法：662=4141+248414=2481+166248=1661+82166=822+282=241因此，gcd(414,

4、662)=22是最后一個非0余數(shù)。一、歐幾里德算法偽碼描述Procedure gcd (a,b: 正整數(shù))x:=a; y:=bwhile y0 y為余數(shù)begin r:=x mod y x:=y y:=rend gcd(a,b)是x二、整數(shù)表示日常生活中都用十進制符號表示整數(shù)；965=9102+610+5；計算機常用的還有2進制、8進制和16進制；我們可以用1以外的任何正整數(shù)為基數(shù)來表示整數(shù)。二、整數(shù)表示定理1：令b為大于1的正整數(shù)。那么如果n是個正整數(shù)，就可以唯一地表示為下面的形式：n=akbk+ak-1bk-1+a1b+a0 ，其中k是非負整數(shù)，a0,a1,ak是小于b的非負整數(shù)，ak0。

5、定理1中給出的n的表示稱為n的以b為基數(shù)的展開。n的基數(shù)b展開表示為(ak,a1,a0)b；(245)8表示282+48+5=165。二、整數(shù)表示以2為基數(shù)就得到整數(shù)的二進制展開；在二進制符號中每位數(shù)字或0，或1；整數(shù)的二進制展開就是位串；計算機用二進制展開表示整數(shù)并做整數(shù)算術(shù)運算。二、整數(shù)表示例：以(101011111)2為二進制展開的整數(shù)，其十進制展開是什么？解： (101011111)2=28+26+24+23+22+2+1=35116是計算機科學(xué)中使用的另一個基數(shù)通常使用的數(shù)字是：0,1,2,9, A, B,C, D, E, F0,1,2,9,10,11,12,13,14,15二、整數(shù)

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

7、轉(zhuǎn)置和冪定義：n階單位矩陣是nn矩陣In=ij，其中ij=1若i=j，ij=0若ij。四、矩陣的轉(zhuǎn)置和冪用大小合適的單位矩陣乘一個矩陣，不改變該矩陣。若A是mn矩陣，則有：AIn=ImA=A。方陣的冪：若A是nn矩陣，則有：A0=InAr=AAAA（r個）四、矩陣的轉(zhuǎn)置和冪定義：令A(yù)=aij為mn矩陣。A的轉(zhuǎn)置，用At表示，是交換A的行和列得到的nm矩陣。若At=bij，則bij=aji，i=1,2,n，j=1,2,m。例：四、矩陣的轉(zhuǎn)置和冪定義：若方陣A和它的轉(zhuǎn)置相等，即A= At，則A稱為對稱矩陣。A=aij為對稱矩陣的條件是：對所有i，j，1in，1jn，aij=aji。方陣對主對角線對

8、稱四、矩陣的轉(zhuǎn)置和冪五、0-1矩陣元素非0即1的矩陣稱為0-1矩陣。0-1矩陣常用來表示離散結(jié)構(gòu)。使用這些結(jié)構(gòu)的算法的基礎(chǔ)是以0-1矩陣做布爾運算（和）。五、0-1矩陣定義：令A(yù)=aij和B=bij為mn階0-1矩陣。A和B的并，用AB表示，是個0-1矩陣，其(i,j)元素為aijbij。A和B的交，用AB表示，是個0-1矩陣，其(i,j)元素為aijbij。五、0-1矩陣?yán)何濉?-1矩陣定義：令A(yù)=aij為mk階0-1矩陣，B=bij為kn階0-1矩陣。A和B的布爾乘積，用AB表示，是mn矩陣cij，其中：類似于兩個矩陣的普通乘積，但要用代替加法，用代替乘法。五、0-1矩陣?yán)何濉?-1矩

9、陣偽碼：五、0-1矩陣定義：令A(yù)為0-1方陣，r為正整數(shù)。A的r次布爾冪是r個A的布爾乘積。A的r次布爾冪用Ar表示。Ar=AAAA（r個）A0=In五、0-1矩陣?yán)篈r=A5對所有大于或等于5的正整數(shù)n均成立五、0-1矩陣?yán)喝鬉和B為nn階0-1矩陣，計算AB需要做多少次字位運算？解： AB有n2個元素；用上述算法，需要n次和n次來計算AB的一個元素；因此，需要2n次字位運算；所以計算AB需要2n3次字位運算。五、0-1矩陣實例蛋白質(zhì)互作網(wǎng)絡(luò)（Protein-Protein Interaction Network）基因調(diào)控網(wǎng)絡(luò)（Gene Regulatory Network） 五、0-1矩陣實例Ar表示兩點間長度為r的通路小結(jié)歐幾里德算法輾轉(zhuǎn)相除法二進制八進制十六進制n的基數(shù)b展開小結(jié)整數(shù)運算算法表示為二進制展開的整數(shù)的加法加法的算法復(fù)雜性表示為二進制展開的整數(shù)的乘法乘法的算法復(fù)雜性小結(jié)矩陣的加法和乘法矩陣運算的偽碼描述矩陣的轉(zhuǎn)置和冪0-1矩陣ABABAB（布爾乘積）掌握