文獻(xiàn)檢索組合數(shù)學(xué)作業(yè)

1、組合數(shù)學(xué)學(xué)習(xí)心得在研一的下學(xué)期，學(xué)院給安排了組合數(shù)學(xué)的課程。剛開(kāi)始上課并不清楚開(kāi)設(shè)這門(mén)課對(duì)于學(xué)習(xí)的意義，只是印象中一直認(rèn)為宋老師是一個(gè)有實(shí)力并且對(duì)學(xué)生要求嚴(yán)格的好老師，所以上課不由得會(huì)集中注意認(rèn)真聽(tīng)講。與其他課程不同，宋老師為了調(diào)動(dòng)大家學(xué)習(xí)的積極性，每節(jié)課都會(huì)叫同學(xué)回答問(wèn)題，這樣一來(lái)，我們開(kāi)始更加注意聽(tīng)講并做好筆記。后來(lái)證明宋老師的辦法是高明的和高效的，我從心底里佩服宋老師的教學(xué)經(jīng)驗(yàn)和教學(xué)能力，尤其是個(gè)人的學(xué)術(shù)和專(zhuān)業(yè)素養(yǎng)。在短短的六周的學(xué)習(xí)時(shí)間中，經(jīng)歷了從強(qiáng)迫自己學(xué)習(xí)到自己主動(dòng)認(rèn)真學(xué)習(xí)，從開(kāi)始的懵懂不知到深刻認(rèn)識(shí)到組合數(shù)學(xué)的重要性，從缺乏數(shù)學(xué)思維到重點(diǎn)培養(yǎng)鍛煉自己的邏輯思維的幾個(gè)過(guò)程。通過(guò)組合

2、數(shù)學(xué)課程的學(xué)習(xí)，首先，在心態(tài)上積極性上得到很大的改觀，培養(yǎng)了自己主動(dòng)學(xué)習(xí)思考勤于發(fā)現(xiàn)的能力；其次，注重理論結(jié)合實(shí)踐，能將在組合數(shù)學(xué)中學(xué)到的數(shù)學(xué)思維數(shù)學(xué)公式與實(shí)際生活結(jié)合起來(lái)，并應(yīng)用于計(jì)算機(jī)研究領(lǐng)域，這對(duì)的研究方向的研究很有幫助，真正的做到“致知”；再次，對(duì)數(shù)學(xué)的學(xué)習(xí)不深入敲響警鐘。在計(jì)算機(jī)研究領(lǐng)域，數(shù)學(xué)是相當(dāng)重要的，很多專(zhuān)業(yè)知識(shí)都要先轉(zhuǎn)化為數(shù)學(xué)模型，通過(guò)數(shù)學(xué)的辦法加以解決。反映在在學(xué)習(xí)的過(guò)程中，一旦見(jiàn)到復(fù)雜的數(shù)學(xué)公式，就跳過(guò)去，這樣的學(xué)習(xí)方法是不嚴(yán)謹(jǐn)?shù)?。所以，在今后的學(xué)習(xí)中，我一定要見(jiàn)到公式就推導(dǎo)演算，把問(wèn)題由表及里深入研究；最后，將組合數(shù)學(xué)的知識(shí)應(yīng)用于研究方向-醫(yī)學(xué)圖像處理。比如，腦 MRI

3、圖像分割問(wèn)題，圖像分割可以看作不同的劃分問(wèn)題, 而圖可以進(jìn)行不同的劃分,圖割法(graph cut)就是將圖像為圖后, 分割問(wèn)題就可以用圖論方法(如:最小割)求解。下面，我將從組合數(shù)學(xué)的概念及研究?jī)?nèi)容、組合數(shù)學(xué)中的經(jīng)典問(wèn)題、組合數(shù)學(xué)在計(jì)算機(jī)方面的應(yīng)用、組合數(shù)學(xué)與醫(yī)學(xué)圖像處理、結(jié)語(yǔ)這六個(gè)方面詳細(xì)介紹我從組合數(shù)學(xué)課程中學(xué)到的東西。一、組合數(shù)學(xué)的概念及研究?jī)?nèi)容現(xiàn)代數(shù)學(xué)的兩個(gè)重要分支，一是對(duì)連續(xù)對(duì)象的研究，如分析、方程等，還有一類(lèi)就是對(duì)離散對(duì)象的研究，這便是組合數(shù)學(xué)。它是近年來(lái)由于電腦科技的發(fā)展而新興的一門(mén)綜合性和邊緣性的學(xué)科。在世界產(chǎn)業(yè)市場(chǎng)上，一直處于絕對(duì)的地位，其根本原因就是世界上最快最先進(jìn)的電腦

4、總是最早在開(kāi)發(fā)出來(lái)計(jì)算機(jī)界最的也多是研究組合數(shù)學(xué)的出身。在大學(xué)里，最重要的計(jì)算機(jī)科學(xué)系都有一流的組合數(shù)學(xué)家為學(xué)生授課。在國(guó)外一些大公司，如、 等公司，都有全世界最強(qiáng)的組合。關(guān)于對(duì)組合數(shù)學(xué)概念的理解，不同學(xué)者有不同的觀念。但有一點(diǎn)是無(wú)可非議的，那就是組合數(shù)學(xué)是一門(mén)研究離散對(duì)象的學(xué)科，是電腦技術(shù)出現(xiàn)后迅速發(fā)展起來(lái)的一門(mén)數(shù)學(xué)分支。它的快速發(fā)展又加速了電腦技術(shù)的開(kāi)發(fā)。組合數(shù)學(xué)一般可以描述為：組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在，計(jì)數(shù)，分析，和優(yōu)化等問(wèn)題的一門(mén)學(xué)科。與傳統(tǒng)的數(shù)學(xué)課程相比，組合數(shù)學(xué)研究的是對(duì)象是一些離散的事物之間存在的數(shù)學(xué)關(guān)系，包括存在性問(wèn)題、計(jì)數(shù)性問(wèn)題、構(gòu)造性問(wèn)題以及最優(yōu)化問(wèn)題等。其主要內(nèi)容包括

5、：排列組合、生成函數(shù)和遞推關(guān)系、容斥原理、鴿巢原理、定理、線性規(guī)劃等。二、組合數(shù)學(xué)中的經(jīng)典問(wèn)題組合數(shù)學(xué)研究的對(duì)象就是離散構(gòu)形問(wèn)題，如研究符合一定條件的組態(tài)對(duì)象、計(jì)數(shù)及構(gòu)造等方面。象構(gòu)形的存在性問(wèn)題、構(gòu)形的計(jì)數(shù)問(wèn)題、形的最優(yōu)化問(wèn)題等等。數(shù)學(xué)發(fā)展史上幾個(gè)著名的數(shù)學(xué)問(wèn)題的提出和解決都與組合數(shù)學(xué)的基礎(chǔ)內(nèi)容有著密切的關(guān)聯(lián)。組合數(shù)學(xué)中有很多問(wèn)題，如：錯(cuò)排列計(jì)數(shù)問(wèn)題、復(fù)雜數(shù)列遞推關(guān)系的求解問(wèn)題、數(shù)列問(wèn)題。對(duì)于計(jì)數(shù)問(wèn)題的處理方式和技巧有：排列與組合、容斥原理及其應(yīng)用、遞推關(guān)系、生成函數(shù)、整數(shù)分拆、鴿籠原理和 Ramsey 定理。還有數(shù)學(xué)遞推公式的證明方法：數(shù)學(xué)歸納法。組合數(shù)學(xué)中的經(jīng)典問(wèn)題主要包括：（1）地圖問(wèn)

6、題；（2）船夫過(guò)河問(wèn)題；（3）棋盤(pán)完美覆蓋；（4）切割立方體；（5）幻方；（色問(wèn)題；（7）36軍官問(wèn)題；（8）最短路徑；（9）NIM 取子問(wèn)題；（10）中國(guó)郵遞員問(wèn)題；（11）穩(wěn)定問(wèn)題。這里主要介紹地圖問(wèn)題、船夫過(guò)河問(wèn)題和中國(guó)郵遞員問(wèn)題。地圖問(wèn)題。此問(wèn)題又稱(chēng)為“四色猜想”，即給世界地圖進(jìn)行，不同國(guó)家使用不同的顏色。若要求相鄰國(guó)家的顏色也不同，只用種顏色能不能 解決這個(gè)問(wèn)題？一個(gè)多世紀(jì)以來(lái)，可謂是讓各國(guó)的數(shù)學(xué)家絞盡了腦汁。由于在研究證明的過(guò)程中，對(duì)象問(wèn)題復(fù)雜，又難以建立相應(yīng)的數(shù)學(xué)模型，所以很難由人工來(lái)完成，所以一些組合數(shù)學(xué)家開(kāi)始借助電腦的幫助而最終得以解決，并由此產(chǎn)生了一些新的數(shù)學(xué)理論及計(jì)算技巧

7、，特別是將地圖的問(wèn)題轉(zhuǎn)化為圖論問(wèn)題，又豐富了圖論內(nèi)容。但人類(lèi)的求知是無(wú)止境的，有沒(méi)有一種更簡(jiǎn)捷的證明方法？到現(xiàn)在仍有一些數(shù)學(xué)者在探尋這個(gè)問(wèn)題。船夫過(guò)河問(wèn)題。有一個(gè)問(wèn)題，一船夫要把一只狼、一只羊、一捆白菜運(yùn)到河對(duì)岸去，要求是當(dāng)人不在場(chǎng)時(shí)，要防止“狼吃羊”、“羊吃白菜”的情況發(fā)生，但船夫的船每趟只能運(yùn)其中的一種。問(wèn)怎樣安排過(guò)河順序，才能把三者都運(yùn)到河對(duì)岸去？這便是很典型的線性規(guī)劃問(wèn)題。中國(guó)郵遞員問(wèn)題。一個(gè)郵遞員的工作是：按一定路線遞送他所負(fù)責(zé)的街區(qū)的各條街道的郵件，最后返回郵局，要求郵遞員必須走過(guò)他負(fù)責(zé)的街區(qū)的每一條街道至少一次，并希望選擇一條總路程最短的遞送路線。用圖論的述語(yǔ)，在通的賦權(quán)圖 G（

8、V，E）中，要尋找一條回路，使該回路包含 G 中的每條邊至少一次，且該回路的權(quán)數(shù)最小。 也就是說(shuō)要從包含 G 的每條邊的回路中找一條權(quán)數(shù)最小的回路。如果G 是圖，若圖中有回路，因?yàn)榛芈吠ㄟ^(guò)所有的邊，因此任何一個(gè)回路即為此問(wèn)題的解，則很容易由萊算法求出一個(gè)回路求出一個(gè)回路，但是若 G 不是圖，即存在奇度數(shù)的節(jié)點(diǎn)，則中國(guó)由遞員問(wèn)題的解決要得多。在現(xiàn)實(shí)生活中，很多問(wèn)題都可以轉(zhuǎn)化為中國(guó)郵遞員問(wèn)題，例如道路清掃時(shí)如何使開(kāi)空車(chē)的總時(shí)間最少等等。三、組合數(shù)學(xué)在計(jì)算機(jī)方面的應(yīng)用隨著計(jì)算機(jī)技術(shù)的深入發(fā)展，特別是計(jì)算機(jī)網(wǎng)絡(luò)的廣泛使用，計(jì)算機(jī)的使用已經(jīng)深入到科學(xué)研究和人們?nèi)粘Ｉ畹母鱾€(gè)領(lǐng)域。計(jì)算機(jī)要向更加智能化的方

9、向發(fā)展，其出路仍然是數(shù)學(xué)的算法和數(shù)學(xué)的機(jī)械化。 算法研究是計(jì)算機(jī)科學(xué)的重要研究領(lǐng)域，組合數(shù)學(xué)家在 20 世紀(jì) 70 年代初建立的算法復(fù)雜性 NP 理論為計(jì)算機(jī)算法復(fù)雜性的研究提供了重要的理論基礎(chǔ)。組合數(shù)學(xué)是計(jì)算機(jī)產(chǎn)業(yè)的基礎(chǔ)，開(kāi)發(fā)次的產(chǎn)品離不開(kāi)組合數(shù)學(xué)。組合數(shù)學(xué)在國(guó)外早已成為十分重要的學(xué)科，甚至可以說(shuō)是計(jì)算機(jī)科學(xué)的基礎(chǔ)，計(jì)算機(jī)科學(xué)界的很多都是研究組合數(shù)學(xué)出身的。和之所以能在行業(yè)處于世界領(lǐng)先的地位，與這兩個(gè)國(guó)家在基礎(chǔ)數(shù)學(xué)，特別是組合數(shù)學(xué)方面的儲(chǔ)備分不開(kāi)的，但在國(guó)內(nèi)仍有一部人對(duì)組合數(shù)學(xué)的認(rèn)識(shí)不夠，認(rèn)為組合數(shù)學(xué)只是一門(mén)純粹的基礎(chǔ)學(xué)科，對(duì)經(jīng)濟(jì)發(fā)展實(shí)際意義不大，可實(shí)際情況是產(chǎn)業(yè)、網(wǎng)絡(luò)算法和分析、信息壓縮、

10、編碼技術(shù)、系統(tǒng)都離不開(kāi)組合數(shù)學(xué)的理論和方法上的支持。 以基礎(chǔ)數(shù)學(xué)為代表的基礎(chǔ)理論研究已成為我國(guó)業(yè)發(fā)展的瓶頸，中國(guó)要想能成為一個(gè)大國(guó)，就應(yīng)加強(qiáng)組合數(shù)學(xué)教學(xué)和培養(yǎng)等工作。（1）Ramsey 數(shù)在信息檢索的重要應(yīng)用。信息檢索是計(jì)算機(jī)科學(xué)中一個(gè)基本而又重要。如何組織數(shù)據(jù),使用什么樣的查找方法,對(duì)檢索的效率有很大的影響。所熟知的在有序表結(jié)構(gòu)上的二分搜索算法是一種很有效的方法,那么二分搜索是最好的算法嗎?有研究者利用 Ramsey 數(shù)對(duì)這一問(wèn)題作了肯定的回答。（2）Ramsey 數(shù)在分組交換網(wǎng)設(shè)計(jì)的重要應(yīng)用。網(wǎng)絡(luò)是計(jì)算機(jī)發(fā)展的一個(gè)特點(diǎn),是進(jìn)入信息社會(huì)的巨大推動(dòng)力。分組交換網(wǎng)是采用分組交換技術(shù)的網(wǎng)絡(luò),它從終

11、端或計(jì)算機(jī)接收?qǐng)?bào)文,把報(bào)文分割成分組,并按某種策略選擇最佳路徑在網(wǎng)中傳輸,到達(dá)目的地后再將分組合并成報(bào)文交給目的終端或計(jì)算機(jī)。分組交換技術(shù)在網(wǎng)絡(luò)設(shè)計(jì)中被廣泛采用。有研究者在一個(gè)稱(chēng)作 Bell System SingnalingNetwork(Bell 系統(tǒng)信令網(wǎng)絡(luò))的分組交換網(wǎng)設(shè)計(jì)中用到了 Ramsey 數(shù)。（3）在學(xué)中的應(yīng)用：用組合變換為底的冪剩余函數(shù)作和及斯作加變換、消除了 體制的周期而不能被直接破譯，這是在 體制的基礎(chǔ)上一種新型公鑰體制，是近年來(lái)領(lǐng)域的一次。論證表明，這種新體制安全性是建立在“具有大質(zhì)數(shù)因子的合數(shù)的因子分解，以的計(jì)算方法仍是個(gè)計(jì)算上”這一基礎(chǔ)之上，但這個(gè)新體制的安全性遠(yuǎn)遠(yuǎn)

12、高于舊的 體制。（4）在分區(qū)分級(jí)天氣預(yù)報(bào)中的應(yīng)用：組合數(shù)學(xué)是以集合論和圖論為基礎(chǔ)的數(shù)學(xué)，其用途極為廣泛，幾乎涉及和滲透到所有領(lǐng)域，如運(yùn)籌學(xué)、信息論、系統(tǒng)工程、計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)、電路網(wǎng)絡(luò)、人工智能等。隨著電子計(jì)算機(jī)的發(fā)展，組合數(shù)學(xué)的許多繁重計(jì)算，都可在計(jì)算機(jī)上實(shí)現(xiàn)，因而組合數(shù)學(xué)的應(yīng)用，更加廣泛和深入。（5）在不定方程中的應(yīng)用：第一個(gè)例子就是世界著名的四色問(wèn)題，它的魅力在于其結(jié)論可以很簡(jiǎn)單地說(shuō)清楚，但從來(lái)沒(méi)有人能從頭至尾完整地在理論上用人力去證明它。直至年才由兩位數(shù)學(xué)家宣布他們用計(jì)算機(jī)證明了這個(gè)結(jié)論。四、組合數(shù)學(xué)與醫(yī)學(xué)圖像處理組合數(shù)學(xué)不是干巴巴的數(shù)學(xué)公式，而是生動(dòng)的數(shù)學(xué)思維和模型，可以應(yīng)用于生

13、活中的方方面面。研究方向是醫(yī)學(xué)圖像處理，組合數(shù)學(xué)當(dāng)然也可以應(yīng)用于醫(yī)學(xué)圖像處理。如我之前所說(shuō)，醫(yī)學(xué)圖像分割中的圖割（graph cut）方法就是一個(gè)經(jīng)典的實(shí)例。圖論方法的主要是將圖像成圖,把圖像像素看作圖的頂點(diǎn), 鄰接像間的關(guān)系看作圖的邊, 鄰接像間的相似性看作邊的權(quán)值, 根據(jù)邊的權(quán)值設(shè)計(jì)能量函數(shù), 通過(guò)最小化能量函數(shù)完成對(duì)圖的分割, 從而實(shí)現(xiàn)圖像分割?；趫D割的圖像分割步驟, 主要包括三步: 1) 能量函數(shù)的設(shè)計(jì); 2) 圖的構(gòu)造; 3) 最小割/最大流方法。除此之外，基于數(shù)學(xué)形態(tài)學(xué)的分水嶺分割算法也是數(shù)學(xué)在醫(yī)學(xué)圖像分割中的重要應(yīng)用。五、結(jié)語(yǔ)隨著計(jì)算機(jī)的普及推廣，組合數(shù)學(xué)這門(mén)古老的學(xué)科煥發(fā)出蓬勃的生機(jī)。組合數(shù)學(xué)是一門(mén)研究?jī)?nèi)容豐富、應(yīng)用廣泛的學(xué)科，同時(shí)它也是一門(mén)講究方法，講究技巧的學(xué)科。 組合數(shù)學(xué)的在于一個(gè)組合數(shù)學(xué)問(wèn)題的能否得到完善的解決往往取決于能否找到巧妙的解法，計(jì)算機(jī)強(qiáng)大的計(jì)算能力為尋求組合數(shù)學(xué)問(wèn)題的巧妙解法提供了無(wú)限的可能，同時(shí)組合數(shù)學(xué)也反過(guò)來(lái)有效地推動(dòng)了計(jì)算機(jī)科學(xué)的發(fā)展。組合數(shù)學(xué)是一門(mén)思考才有收獲和體驗(yàn)的學(xué)科，但是