1、數(shù)理邏輯Mathematical Logic 第二章 算法、整數(shù)和矩陣Chapter 2 Algorithm、Integer and Matrix復(fù)習(xí)算法復(fù)雜性算法的時(shí)間復(fù)雜性算法的空間復(fù)雜性算法的時(shí)間復(fù)雜性在輸入規(guī)模一定的情況下用算法使用的運(yùn)算次數(shù)來(lái)表示最壞情況分析平均情況分析復(fù)習(xí)算法的時(shí)間復(fù)雜性求集合最大元素2(n-1) O(n)線(xiàn)性搜索最壞情況 2n+2 O(n)平均情況 n+2 O(n)對(duì)分搜索最多需要2log n+2 O(logn)勿 死記硬背會(huì) 計(jì)算分析復(fù)習(xí)算法的時(shí)間復(fù)雜性常數(shù)復(fù)雜性、對(duì)數(shù)復(fù)雜性、線(xiàn)性復(fù)雜性、nlogn復(fù)雜性、多項(xiàng)式復(fù)雜性、指數(shù)復(fù)雜性、階乘復(fù)雜性易處理的問(wèn)題不易處理

2、的問(wèn)題不可解的問(wèn)題2.3 整數(shù)和除法The Integers and Division一、引言離散數(shù)學(xué)中涉及整數(shù)及其性質(zhì)的這一部分內(nèi)容屬于數(shù)學(xué)中的數(shù)論。數(shù)論這門(mén)學(xué)科最初是從研究整數(shù)開(kāi)始的，所以叫做整數(shù)論。后來(lái)整數(shù)論又進(jìn)一步發(fā)展，就叫做數(shù)論了。確切的說(shuō)，數(shù)論就是一門(mén)研究整數(shù)性質(zhì)的學(xué)科。一、引言費(fèi)爾馬大定理、哥德巴赫猜想、孿生素?cái)?shù)問(wèn)題、 圓內(nèi)整點(diǎn)問(wèn)題、完全數(shù)問(wèn)題高斯曾經(jīng)說(shuō)過(guò)“數(shù)學(xué)是科學(xué)的皇后,數(shù)論是數(shù)學(xué)中的皇后”。數(shù)論中的基本概念可除性、最大公約數(shù)、模運(yùn)算等一、引言在2.4節(jié)結(jié)合算法及其復(fù)雜性介紹數(shù)論中的幾個(gè)重要算法求兩個(gè)正整數(shù)的最大公約數(shù)的算法用二進(jìn)制展式做計(jì)算機(jī)運(yùn)算的算法本節(jié)基于可除性，講解素

3、數(shù)、算術(shù)基本定理、模運(yùn)算以及模運(yùn)算的應(yīng)用（為文件分配內(nèi)存地址、生成偽隨機(jī)數(shù)、為信息加密和解密）二、除法定義1：如果a和b是整數(shù)，a0，若有整數(shù)c使b=ac，就說(shuō)a整除b。在a整除b時(shí)，a是b的一個(gè)因子，b是a的倍數(shù)。符號(hào)a|b表示a整除b。當(dāng)a不能整除b時(shí)寫(xiě)成ab。可被正整數(shù)d整除的整數(shù)-3d-2d-d0d2d3d二、除法例1：判斷6|2, 3|7和3|12？例2：令n和d為正整數(shù)。不超過(guò)n的正整數(shù)中有多少個(gè)能被d整除？n/d 二、除法定理1：令a，b，c為整數(shù)。有如下結(jié)論：若a|b和a|c，則a|(b+c)；若a|b，那么對(duì)所有整數(shù)c都有a|bc；若a|b，b|c，則a|c。證：假定a|b和

4、a|c。從可除性定義知有整數(shù)s和t，使b=as和c=at。因此，b+c=as+at=a(s+t)。于是，a整除b+c。三、素?cái)?shù)大于1的每個(gè)正整數(shù)都至少能被兩個(gè)整數(shù)整除（1和它自身）。恰有兩個(gè)不同的正整數(shù)因子的整數(shù)稱(chēng)為素?cái)?shù)。定義2：大于1的正整數(shù)p稱(chēng)為素?cái)?shù)，如果p僅有的正因子是1和p。大于1又不是素?cái)?shù)的正整數(shù)稱(chēng)為合數(shù)。三、素?cái)?shù)例3：判斷7和9是素?cái)?shù)？小于100的素?cái)?shù)有哪些？（P113）定理2（算術(shù)基本定理）：任意一個(gè)正整數(shù)n(n1)可以唯一地表示為若干個(gè)素?cái)?shù)的乘積。這里唯一的意義表示為不考慮素因子的次序。素?cái)?shù)是構(gòu)造正整數(shù)的積木。三、素?cái)?shù)分解的存在性分解的唯一性，即若不考慮排列的順序，正整數(shù)分解為

5、素?cái)?shù)乘積的方式是唯一的。 例4：100=2255=2252641=641999=33337=3337三、素?cái)?shù)如何證明一個(gè)給定的數(shù)是素?cái)?shù)？定理3：如果n是合數(shù)，那么n必有一個(gè)小于或等于 的素因子。證：如果n是合數(shù)，它有一個(gè)因子a，使1a1，所以10,19和24不是兩兩互素的。五、最大公約數(shù)求兩個(gè)整數(shù)最大公約數(shù)的另外一種方法：利用兩個(gè)整數(shù)的素因子分解。假定兩個(gè)全不為0的整數(shù)a和b的素因子分解為 每個(gè)指數(shù)都是非負(fù)整數(shù)，出現(xiàn)在a和b分解中的所有素?cái)?shù)都包含在兩個(gè)分解之中，必要時(shí)以0為指數(shù)出現(xiàn)五、最大公約數(shù)證明：P116例14：已知120和500的素因子分解分別為120=2335和500=2253，求它們

6、的最大公約數(shù)？解： 六、最小公倍數(shù)定義7：正整數(shù)a和b的最小公倍數(shù)是能被a和b整除的最小正整數(shù)。記作：lcm(a,b)。lcm: lowest common multiple素因子分解也可用于求兩個(gè)整數(shù)的最小公倍數(shù) 六、最小公倍數(shù)例15 求233572和2433的最小公倍數(shù)解：定理5：令a和b為正整數(shù)，則 ab=gcd(a,b)lcm(a,b)七、模運(yùn)算定義8：令a為整數(shù)，m為正整數(shù)。a mod m表示a被m除的余數(shù)。a mod m是使a=qm+r且0rm的整數(shù)r。例16：17mod5 -133mod9定義9：若a和b為整數(shù)而m為正整數(shù)，如果m整除a-b，就說(shuō)a與b是模m同余，記作：ab(mo

7、d m)，否則記作ab(mod m)。七、模運(yùn)算例17：判斷17是否和5模6同余？24是否和14模6同余？解：由于6整除17-5=12，所以175(mod 6)24-14=10不能被6整除，所以2414(mod 6)定理6：令m為正整數(shù)，整數(shù)a和b模m同余的充分必要條件是存在整數(shù)k，使a=b+km。證明：P118七、模運(yùn)算定理7：令m為正整數(shù)，若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)八、同余應(yīng)用可以用同余為計(jì)算

8、機(jī)分配內(nèi)存地址例19：散列（哈希）函數(shù)散列就是無(wú)需查找，直接用元素的查找鍵來(lái)確定元素索引的方法。實(shí)現(xiàn)了散列這種方法的函數(shù)就叫散列函數(shù)。散列函數(shù)接受查找鍵，產(chǎn)生一個(gè)稱(chēng)為散列表的數(shù)組中的元素的索引。八、同余應(yīng)用設(shè)一個(gè)查找表S有n個(gè)數(shù)據(jù)元素S=R1, R2, , Rn。對(duì)于每個(gè)指定的Ri，設(shè)key是其關(guān)鍵字的值。則建立一個(gè)從Ri.key到Ri的存貯地址函數(shù)H為 H(Ri. key)=addr(Ri) 稱(chēng)H為哈希函數(shù)（Hash），函數(shù)值H(Ri. key)稱(chēng) 為哈希地址。按該方法所建立的表稱(chēng)為哈希表。八、同余應(yīng)用散列函數(shù)的一般特性： 1 使沖突最小 2 使元素均勻分布在散列表里 3 計(jì)算要快。最常用的

9、散列函數(shù)之一是： h(k)=k mod mm是可供使用的內(nèi)存地址的數(shù)目八、同余應(yīng)用例如，當(dāng)m=111時(shí)，064212848這個(gè)學(xué)生的記錄分配到地址14，因?yàn)?h(064212848)=064515848 mod 111=14 類(lèi)似的，由于 h(037149212)=037149212 mod 111=65由于散列函數(shù)不是一對(duì)一的（關(guān)鍵碼的個(gè)數(shù)大于內(nèi)存地址數(shù)），有可能多個(gè)紀(jì)錄分配到同一內(nèi)存地址。（沖突）八、同余應(yīng)用消除沖突的一個(gè)方法是使用散列函數(shù)給出的但已被占用的地址后面第一個(gè)未被占用的地址。我們把15分配給107405723，因?yàn)閔(107405723)= 107405723 mod 111=

10、14，14已經(jīng)被占用。八、同余應(yīng)用偽隨機(jī)數(shù)用系統(tǒng)的方法產(chǎn)生的數(shù)不可能是真正隨機(jī)的，就稱(chēng)為偽隨機(jī)數(shù)最常用的產(chǎn)生偽隨機(jī)數(shù)的過(guò)程稱(chēng)為線(xiàn)性同余法xn+1=(axn+c) mod mP120九、密碼學(xué)最重要的同余應(yīng)用之一涉及研究信息保密的密碼學(xué)最早使用密碼的例子之一是凱撒他把每個(gè)字母在字母表中往下移動(dòng)3位以獲得保密信息（最后三位移到最前）字母b移到e，字母x移到a用數(shù)學(xué)來(lái)表示凱撒的加密過(guò)程九、密碼學(xué)用0表示a，25表示z凱撒的加密過(guò)程可以用函數(shù)f表示，f(p)=(p+3)mod26，其中0p25，在加密信息中，p代表的字母用f(p)代表的字母代替。“red” “uhg”例21：“meet you in

11、the park”，用凱撒密碼加密。“PHHWBRXLQWHKSDUN”九、密碼學(xué)要把凱撒密碼的加密信息還原為原來(lái)的信息，需要使用f的反函數(shù)f-1。f-1(p)=(p-3)mod26，每個(gè)字母向前移3位，最前3個(gè)字母移到最后。從加密信息恢復(fù)成原信息的過(guò)程稱(chēng)為解密。九、密碼學(xué)凱撒密碼的推廣把每個(gè)字母移動(dòng)k位，于是f(p)=(p+k)mod26，這樣的密碼稱(chēng)為移位密碼，解碼用f-1(p)=(p-k)mod26來(lái)完成凱撒的方法和移位密碼不能提供高度安全，稍稍提高一點(diǎn)安全性的一種辦法是使用f(p)=(ap+b)mod26，其中a和b為整數(shù)。九、密碼學(xué)例22：若用f(p)=(7p+3)mod26加密，用什么字母來(lái)代替k？解：10代表k，f(10)=(710+3)mod26=73 mod 26=21，21代表v，所以，在加密信息中，用v代表k。更復(fù)雜一些的加密方法是用一段字母取代另一段字母。小結(jié)素?cái)?shù)合數(shù)算術(shù)基本定