離散數(shù)學(xué)大報(bào)告

1、 /10離散數(shù)學(xué)大報(bào)告信計(jì)12徐文豪21109020391.交大最短路徑內(nèi)容簡(jiǎn)介圖論中最短路徑算法在現(xiàn)實(shí)中的應(yīng)用很廣泛，包括道路建設(shè)、線(xiàn)路搭建、最優(yōu)公交路線(xiàn)等等，因此親自實(shí)踐一下它是很有意思的。同時(shí)，漫步在美麗寧?kù)o的校園中，有時(shí)會(huì)想到是筆直的康莊大道更快還是曲徑通幽的小路更快，于是交大最短路徑的想法油然而生。在報(bào)告的這一部分，我選了自己在校園里常到的38個(gè)地點(diǎn)作為圖中的頂點(diǎn)構(gòu)造無(wú)向帶權(quán)圖，用Florid算法和matlab解決編程問(wèn)題，最后得到了比較理想的結(jié)果。構(gòu)造無(wú)向帶權(quán)圖（1）確定要測(cè)量的邊頂點(diǎn)的選擇是很容易的一件事，但選擇要測(cè)量的邊就不是那么簡(jiǎn)單了，最簡(jiǎn)單的想法莫過(guò)于每?jī)蓚€(gè)頂點(diǎn)測(cè)一個(gè)邊，但

2、這存在一個(gè)很?chē)?yán)重的問(wèn)題，總共38個(gè)頂點(diǎn),如果這樣測(cè)的話(huà)總共需要測(cè)C2703條邊，這明顯會(huì)累死測(cè)量的人，同時(shí)，38相距較遠(yuǎn)的兩個(gè)頂點(diǎn)的邊中往往會(huì)包含其余的頂點(diǎn)，因此這703條邊有大量的重復(fù)，考慮到要做的是最短路徑，我定的兩條添邊原則如下：原則1：將初始節(jié)點(diǎn)從第一個(gè)節(jié)點(diǎn)循環(huán)到最后一個(gè)節(jié)點(diǎn)，添邊只能從初始節(jié)點(diǎn)到初始節(jié)點(diǎn)后面的節(jié)點(diǎn)。原則2：只有當(dāng)兩點(diǎn)間有一條不包含任何其它節(jié)點(diǎn)的可能最短邊時(shí)才添加該邊。實(shí)踐原則2時(shí)，需參考總體地圖，我參考的交大電子地圖如下：（2）確定測(cè)量邊的方法經(jīng)過(guò)（1）我確定了69條需要測(cè)量的邊，對(duì)于怎么測(cè)量這些邊，最開(kāi)始想到的是用步長(zhǎng)測(cè)，東18寢室的地板磚都是0.5m一塊的，經(jīng)過(guò)測(cè)

3、量我發(fā)現(xiàn)我走一步基本穩(wěn)定在0.75m左右。但在用步長(zhǎng)做實(shí)際測(cè)量的時(shí)候卻出現(xiàn)兩個(gè)問(wèn)題：一是實(shí)際要測(cè)的步數(shù)往往都是幾百的，因此中間很容易數(shù)錯(cuò)；二是這對(duì)測(cè)量者的忍耐力是個(gè)很大的挑戰(zhàn)，很惡心人。測(cè)了兩條邊后我放棄了這種方法，想到了用行走的時(shí)間測(cè)量邊長(zhǎng)，同樣是用東18的瓷磚做實(shí)驗(yàn)，我發(fā)現(xiàn)我的平均步行速度穩(wěn)定在1.645m/s左右，因此若用手機(jī)上的計(jì)時(shí)器計(jì)時(shí)我走過(guò)兩點(diǎn)花的時(shí)間，乘以步長(zhǎng)即得邊長(zhǎng)。不過(guò)即便如此，測(cè)量完所有的邊還是花了差不多四個(gè)多小時(shí)左右。中間有同學(xué)提議說(shuō)可以用百度地圖測(cè)距離或者用交大地圖的比例尺測(cè)距離，但由于這樣只能測(cè)直線(xiàn)距離，忽略了中間的障礙物和坡度，因此準(zhǔn)確度很難保證，而且對(duì)有小地點(diǎn)如夢(mèng)

4、婷阿姨店等甚至都沒(méi)有標(biāo)記。最終測(cè)量出的邊數(shù)據(jù)見(jiàn)附錄1。（3）最短路徑算法簡(jiǎn)介目前常用的最短路徑算法主要為Dijkstra算法和Florid算法，兩者的區(qū)別是Dijkstra次算一個(gè)起點(diǎn)到其它起點(diǎn)的最短路徑，而Florid算法一次性算出所有頂點(diǎn)到其它頂點(diǎn)的最短路徑。雖然用N次Dijkstra算法同樣可以算出所有頂點(diǎn)到其它頂點(diǎn)的最短路徑，且復(fù)雜度同樣為O（n3），但因?yàn)镕lorid算法的循環(huán)更加緊湊，所以實(shí)際速度更快。另外，值得一提的是，對(duì)固定圖的最短路徑，當(dāng)把最短距離矩陣和前驅(qū)矩陣算出來(lái)并保存之后，就不必再進(jìn)行之前的運(yùn)算了，以后查詢(xún)時(shí)只需用常數(shù)時(shí)間。Florid算法見(jiàn)附錄2,從前驅(qū)矩陣得到路徑的

5、函數(shù)間附錄3。（4）程序運(yùn)行結(jié)果主程序見(jiàn)附錄4，程序運(yùn)行結(jié)果如下：:-壬13苦2-良勺由.3-去廣址壬|j1-中24|1&1J_7-fe.lZB屁性氏皆：1喃百hil一1|匚1舊壬門(mén)?；i.l:洛圭13騎ishl嗎山u南門(mén)15-虻韋儀LE-F為:L7-：-：.店-書(shū)沖：.:良引小咗盤(pán)航-吃21-Z=1-22-E-7.ST-23-3-7.S.-=-26-.-西-丙工里:卞花酉口芯287西-丙蘭勻：30-a：.11=3i-IaI!=-IL強(qiáng)-匹乂.克:E亠坷吉冃冃33-13八.土呂廣切點(diǎn)Pin-匣獷死由U寧霜口蘭-臣岳西西市丨寧路口前-m込莒.“一公奩二匚陰-匹氏匕匹匡+詁口泊潅7,匕三囁呂：請(qǐng)輸

6、入錢(qián)點(diǎn)塢號(hào):JISTl面屋的最迴號(hào)高約拘;.575225e+002-涉行孝的4.：D5JQ0e+a02b示遼於任士：曲l暗一屋橋小蠟盤(pán)屋橋苑南門(mén)-屋橋苑西南+圭話(huà)口-：西負(fù)堂西-面星維續(xù)語(yǔ)ffiXt-咼止語(yǔ)輸入日：2.謂詞邏輯與反定義2.1背景介紹對(duì)于給出的數(shù)學(xué)定義，比如數(shù)列極限，函數(shù)連續(xù)，函數(shù)一致連續(xù)等等，我們可以比較容易地記住它們。但對(duì)這些定義的反定義，我們憑直覺(jué)去給出它們的條件時(shí)，通常會(huì)比較麻煩，而且容易犯錯(cuò)誤，比如，對(duì)于給定實(shí)數(shù)列a和實(shí)數(shù)a,nlima=a的定義如下：nnsVs0,3NeN*,當(dāng)neN*且N時(shí),|a-aN時(shí),|a-a(2)n而這種定義是不正確的，因?yàn)樗髄ima工a當(dāng)

7、且僅當(dāng)a的某個(gè)有界鄰域內(nèi)nnTg只有a的有限項(xiàng)，比如數(shù)列a二(-l)n，它是發(fā)散的，卻明顯不滿(mǎn)足之上(2)nn給出的定義。的問(wèn)題在于實(shí)際上“當(dāng)”字是有V的意思的，構(gòu)造反定義時(shí)要把其改為3(不是說(shuō)看英文文獻(xiàn)就能避免這個(gè)問(wèn)題了，因?yàn)橛⑽奈墨I(xiàn)也喜歡用when)。這種某個(gè)詞匯沒(méi)被標(biāo)準(zhǔn)化還只是小問(wèn)題，注意到(1)中同樣是比較符號(hào)，nN中的大于號(hào)被保留了下來(lái)，|a-a|s中的小于號(hào)被倒轉(zhuǎn)了。在(1)中，n我們可以簡(jiǎn)單的解釋為一個(gè)是在條件中，一個(gè)是在結(jié)論中，只需逆轉(zhuǎn)結(jié)論中的比較符號(hào)就行了。但如果我們面對(duì)的是一個(gè)很復(fù)雜的定義，那我們還能夠很簡(jiǎn)單地判斷哪些是條件哪些是結(jié)論嗎？更關(guān)鍵的是，即便我們通過(guò)直觀(guān)給出了一

8、個(gè)反定義，貌似還沒(méi)有很好的方法可以直接驗(yàn)證我們給的反定義是正確的，這對(duì)講究嚴(yán)謹(jǐn)，所謂“沒(méi)證過(guò)的定理不敢用”的數(shù)學(xué)系學(xué)生來(lái)說(shuō)似乎略顯尷尬。而如果我們把定義化為離散數(shù)學(xué)謂詞邏輯中的謂詞公式，求反定義不過(guò)是求整個(gè)公式的否定罷了，這無(wú)疑更加有說(shuō)服力。而謂詞邏輯之所以能夠做到這一點(diǎn)是因?yàn)閜oq等值于-pOq。謂詞邏輯求反定義步驟(1)給定變?cè)膫€(gè)體域這一步很重要，因?yàn)槲覀兾覀冇懻摰男再|(zhì)只在變?cè)膫€(gè)體域內(nèi)有效，如果對(duì)個(gè)體域不加限定的話(huà)，則會(huì)造成難以察覺(jué)的錯(cuò)誤。對(duì)(1)，s的個(gè)體域?yàn)镽+，N和n的個(gè)體域?yàn)镹*(2)將原定義轉(zhuǎn)換為謂詞公式定義謂詞和運(yùn)算如下：F(x,y):x0,對(duì)任意NeN*,nnT8存在ne

9、N*且nN，滿(mǎn)足|a一a|。更多例子說(shuō)明(1)不一致連續(xù)的定義常庚哲和史濟(jì)懷的數(shù)學(xué)分析教程中關(guān)于函數(shù)一致連續(xù)的定義如下：如果對(duì)任意給定的0，總存在一個(gè)80，使得當(dāng)x,xeI且|x-x|8時(shí)，有121121f(x)-f(x)，則稱(chēng)函數(shù)f在區(qū)間I上是一致連續(xù)的。設(shè),8的個(gè)體域?yàn)镽+，x,x的個(gè)體域?yàn)镮,定義謂詞和運(yùn)算如下：12F(x,y):x0，對(duì)任意80，存在x,xeI滿(mǎn)足lx一x|。i211r1121而數(shù)學(xué)分析教程中給出的不一致連續(xù)的定義為：函數(shù)f在區(qū)間I上不是一致連續(xù)的，當(dāng)且僅當(dāng)存在一個(gè)0，對(duì)每一個(gè)neN*，都可以在I中找到兩0個(gè)點(diǎn)，記為s和t，使得雖然有|s-t|。nnnnnn0比較這兩個(gè)

10、定義，我們很容易發(fā)現(xiàn)它們是完全等價(jià)的。相對(duì)而言，前者的數(shù)學(xué)意義更加直觀(guān)，而后者更容易應(yīng)用。2)線(xiàn)性無(wú)關(guān)的定義李炯生、查建國(guó)和王新茂的線(xiàn)性代數(shù)中關(guān)于數(shù)域F上線(xiàn)性空間中的向量集合S是線(xiàn)性相關(guān)的定義如下：如果存在向量a,a,aeS，以及不全為零的12k純量九,九，,九eF，使得九a+九a+九a=0，則向量集合S稱(chēng)為線(xiàn)性相12k1122kk關(guān)的。,Xk)。為了敘述簡(jiǎn)便，令a=(a,a,a的個(gè)體域?yàn)閤la,a,12義謂詞和運(yùn)算如下：F(X)：X,X,X不全為零，12k則原定義轉(zhuǎn)換為謂詞公式如下：S線(xiàn)性相關(guān)oBaBX(F(X)aG(f(a,X)(7)的否定如下：S線(xiàn)性無(wú)關(guān)oVaVX(F(X)tG(f(a,

11、X)根據(jù)(8)得到S線(xiàn)性無(wú)關(guān)的定義如下：如果任意向量a,a,12,a)，X=(X,X,12k11,aeSJ，X的個(gè)體域?yàn)?X|X,X,kG(x):x=0，f(a,X):Xa+Xa+1122(7)(8),aeS，任k意純量九,九，,九gF，當(dāng)九,九，,九不全為零，有皿+Xa+九a豐0,12k12k1122kk則向量集合S稱(chēng)為線(xiàn)性無(wú)關(guān)的。對(duì)（8）做一次等值演算，結(jié)果如下：S線(xiàn)性無(wú)關(guān)oVaVX（G（f（a,九）tF（九）（9）根據(jù)（9）即得到了我們常用的線(xiàn)性無(wú)關(guān)的充要條件：向量集合S線(xiàn)性無(wú)關(guān)的充分必要條件是，對(duì)于S的任意一組a,a,a，由12k九a+Xa+Xa=0，一定能得到九二九=X=0，其中九,

12、九，,九gF。1122kk12k12k3謂詞邏輯求逆否定理3.1背景介紹當(dāng)你弄懂了一個(gè)定理，給了你定理的條件，你可以很容易得到定理的結(jié)果，但我們往往會(huì)忽略了定理的另一種用法，就是當(dāng)給了定理結(jié)論的否定時(shí)，我們可以得到定理?xiàng)l件的否定，因?yàn)樵}和它的逆否命題是等價(jià)的。我覺(jué)得，造成忽略的有兩個(gè)可能原因：一是只憑直覺(jué)看出定理的逆定理會(huì)給人不靠譜的感覺(jué)，而且如果定理很復(fù)雜的話(huà)還還很難看出來(lái)；二是定理的意義往往很直觀(guān)，而逆否定理往往比較艱澀，因此很難記住。但如果我們把原定理轉(zhuǎn)化為相應(yīng)的謂詞公式，求逆否定理只不過(guò)是做一次等值演算罷了，這顯然更有說(shuō)服力，而我們能做到這一點(diǎn)的依據(jù)是如下的等值演算：ptqo-pV

13、qo（q）Vp（10）o-qt-p3.2謂詞邏輯求逆否命題流程圖開(kāi)始結(jié)束舉例說(shuō)明（1）數(shù)論中的引理潘承洞和潘承彪的初等數(shù)論中提到一個(gè)引理如下：設(shè)素?cái)?shù)p2，一定存在整數(shù)x,y及m，000設(shè)p的個(gè)體域?yàn)閙gN*11mp。0101m2),x,y的個(gè)體域?yàn)閆,m的個(gè)體域?yàn)?00定義謂詞和運(yùn)算如下：(11)F(x):x是素?cái)?shù)，G(x,y):x=y,f(x,y):xy,g(x,y):1+x2+y2則原定理的謂詞公式如下：Vp(F(p)3xBy3m(G(f(m,p),g(x,y)000000(11)的逆否如下：Vp(VxVyVm(G(f(m,p),g(x,y)F(p)(000000由(12)得到逆否定理如下

14、：對(duì)整數(shù)p2,若對(duì)任意整數(shù)x,y和滿(mǎn)足1mp000的整數(shù)m，若mp主1+x2+y2，則p不是素?cái)?shù)。0000(2)Jensen不等式Jensen不等式的定理形式如下：設(shè)f是區(qū)間I的凸函數(shù)，則對(duì)任何x,x,xgI，以及九,九，,九0，且九+九+九=1都有f(工九x)工九f(x)。TOC o 1-5 h z12n12n12niiiii=1i=1為了敘述簡(jiǎn)便，令x=(x,x,x)，九=(入,九,九)。12n11nA九的個(gè)體設(shè)f的個(gè)體域?yàn)镮上的實(shí)泛函，x的個(gè)體域?yàn)?x|x,x,xgI,12n域?yàn)樨伴T(mén),九，,九0且九+九+九=1,定義謂詞和運(yùn)算如下：12n12nx九iii=1F(f):f是凸函數(shù)，G(x,

15、y):xy，-g(x):(f(x),f(x),f(x)，h(x,九)：為12則原定理的謂詞公式如下：.(13)(14)xgI，nVfVxV九(F(f)TG(h(x,九),h(g(x),九)(13)的逆否形式如下：VfVxV九(G(h(x,九),h(g(x),九)TF(f)由(14)得到逆否定理如下：對(duì)區(qū)間I上的任意函數(shù)f，則對(duì)任何x,x,12以及九,九，,九0，且九+九+12n12數(shù)。九=1，若f(工九x)工九f(x)，則f不是凸函iiiii=1i=14.附錄附錄1：頂點(diǎn)間的步行時(shí)間112167.0113177.7114235.4119208.2125197.023419.823543.831

16、917.233642.943723.843827.25921.051037.952063.7531236.06922.261138.0622217.471867.372051.0817120.1818283.3820180.6830337.2837351.8101145.81017107.2121321.11215122.41216132.7121987.81314303.31419314.3142576.61429209.2151653.2152376.2153635.81720148.41730319.41822189.71830184.81831155.7192818.7193662.8

17、2022273.5212950.2213062.7213738.2222361.62231107.7223463.4242546.42429163.62433183.12435140.0263896.0272926.2273813.3283521.1293076.02935145.8303179.9303234.5303383.1313276.8313333.5323375.9333465.2343639.8附錄2：%弗洛伊德算法求正帶權(quán)圖或無(wú)賦值回路一般帶權(quán)圖算法functiondist,front=Florid(G)%將矩陣中的0元素轉(zhuǎn)化為infn=length(G);fori=1:nforj=1:nifG(i,j)=0G(i,j)=in