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

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

2、Algorithms一、歐幾里德算法用整數(shù)的素因子分解求兩個(gè)整數(shù)最大公約數(shù)的算法效率不高；因?yàn)榍笏匾蜃臃纸庀奶鄷r(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)簡(jiǎn)化為gcd(91,14)一、歐幾里德算法以gcd(91,287)為例再用14去除91，91=146+7；又轉(zhuǎn)

3、化為求gcd(14,7)；繼續(xù)用7去除14，14=72；因?yàn)?整除14，所以gcd(14,7)=7；因此，gcd(287,91)=gcd(91,14)=gcd(14,7)=7。一、歐幾里德算法用輾轉(zhuǎn)相除把求兩個(gè)正整數(shù)最大公約數(shù)的問(wèn)題化簡(jiǎn)為求兩個(gè)較小整數(shù)的最大公約數(shù)，直到兩個(gè)整數(shù)中的一個(gè)為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是最后一個(gè)非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ù)表示日常生活中都用十進(jìn)制符號(hào)表示整數(shù)；965=9102+610+5；計(jì)算機(jī)常用的還有2進(jìn)制、8進(jìn)制和16進(jìn)制；我們可以用1以外的任何正整數(shù)為基數(shù)來(lái)表示整數(shù)。二、整數(shù)表示定理1：令b為大于1的正整數(shù)。那么如果n是個(gè)正整數(shù)，就可以唯一地表示為下面的形式：n=akbk+ak-1bk-1+a1b+a0 ，其中k是非負(fù)整數(shù)，a0,a1,ak是小于b的非負(fù)整數(shù)，ak0。

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

6、表示例：十六進(jìn)制展開(kāi)(2AE0B)16的十進(jìn)制展開(kāi)是什么？(2AE0B)16=2164+10163+14162+016+11=(175627)10十六進(jìn)制數(shù)可以用4個(gè)字位表示一個(gè)字節(jié)是8位所以，一個(gè)字節(jié)可以用兩個(gè)十六進(jìn)制數(shù)表示。二、整數(shù)表示例 (1110 0101)2(E5)16整數(shù)n的基數(shù)b展開(kāi)的算法：首先，用b除n得到商和余數(shù)，n=bq0+a0，0a0b；余數(shù)就是n的基數(shù)b展開(kāi)的最右邊一個(gè)數(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)置和冪用大小合適的單位矩陣乘一個(gè)矩陣，不改變?cè)摼仃?。若A是mn矩陣，則有：AIn=ImA=A。方陣的冪：若A是nn矩陣，則有：A0=InAr=AAAA（r個(gè)）四、矩陣的轉(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稱(chēng)為對(duì)稱(chēng)矩陣。A=aij為對(duì)稱(chēng)矩陣的條件是：對(duì)所有i，j，1in，1jn，aij=aji。方陣對(duì)主對(duì)角線對(duì)

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

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