信息時代的數(shù)學(xué)

信息時代的數(shù)學(xué)第1頁/共49頁9.1從算籌到電子計算機

中國古代的算籌：

創(chuàng)造了以算法化為特征的中國古代數(shù)學(xué)，并取得了眾多領(lǐng)先于其它民族的中國古代數(shù)學(xué)成就

利用算籌進行數(shù)字計算也有其不便之處：

首先，用籌拼排數(shù)碼，10以內(nèi)的九個數(shù)要用29根籌，平均每個數(shù)需用3.2根，就是說擺放一個數(shù)碼平均要做３.2個動作，所以不利于計算。其次，算籌中國古代的算籌較長，計算時占地方大。以較短的隋籌為例，計算一道4位數(shù)乘4位數(shù)得積數(shù)是8位的乘算題，將算籌分上、中、下三層排列，約占長90厘米、寬40厘米的地位，一張方桌不夠做兩道這樣的乘算題

牛牛文庫文檔分享第2頁/共49頁

算盤由于它構(gòu)造簡單，價格低廉，計算方便，中國自明代開始，籌算很快就為算盤所取代。同時也使得中國的數(shù)學(xué)依然固守著算法化的傳統(tǒng)

國外算盤起源也很早，算盤一詞在古希臘文中是“沙盤”，由此可以推測它的原始形式可能是一種有標記的沙盤。中世紀后期的歐洲，一些主張使用羅馬數(shù)字和算盤進行計算的“算盤家”，與另一些主張使用阿拉伯數(shù)字和適當算法的“算術(shù)家”進行了長達四百年（自1100~1500年）的爭論，最終算術(shù)家占了上風，形成了現(xiàn)在使用的計算方法。到了18世紀，算盤在西歐已經(jīng)絕跡。

牛牛文庫文檔分享第3頁/共49頁

納皮爾算籌（約1590年）

使乘法和除法運算歸結(jié)為簡單的加法和減法運算。對數(shù)的發(fā)現(xiàn)“以其節(jié)省勞力而延長了天文學(xué)家的壽命”（拉普拉斯語）

牛牛文庫文檔分享第4頁/共49頁

納皮爾算籌

牛牛文庫文檔分享第5頁/共49頁對數(shù)計算尺基本原理：

岡特（1581~1626）設(shè)計出了第一個對數(shù)刻度尺這是一個標有數(shù)字的線段，從尺的左端量起的距離與所標之數(shù)的對數(shù)成正比，圖中兩個標有刻度的尺子上,自1到2的長度是log2=0.30，自1到3的長度是log3=0.48，……，自1到10的長度是log10=1。利用兩個滑尺做乘除運算時就可以轉(zhuǎn)化為對數(shù)的加減運算。如，log4=log2＋log2=0.60,這個長度就是上面一個滑尺上自1到4的長度。

牛牛文庫文檔分享第6頁/共49頁

第一臺能做加減運算的機械式計算機（1642，帕斯卡）

十九世紀，英國數(shù)學(xué)家巴貝奇是設(shè)想制造具有程序控制功能的普通四則運算機器的第一位學(xué)者

牛牛文庫文檔分享第7頁/共49頁

進入20世紀，計算機研究有了質(zhì)的變化，這得益于數(shù)理邏輯的純形式化推理的研究成果，同時也依賴于科學(xué)技術(shù)為之提供的技術(shù)保障。二次世界大戰(zhàn)中大量計算問題的需要，使計算機發(fā)展有了更廣泛的社會基礎(chǔ)。數(shù)理邏輯的誕生與“可計算”函數(shù)對某些函數(shù)，能否用有限步、按規(guī)定次序的計算過程，得到函數(shù)的解。如果存在這樣的算法，就稱函數(shù)是“可計算”函數(shù)

牛牛文庫文檔分享第8頁/共49頁1936年，英國數(shù)學(xué)家圖靈（1912~1954）在研究可計算性時提出理想計算機理論——圖靈機。圖靈機原本是對于“可計算性”數(shù)學(xué)概念的一種定義方法，但它卻成為今天計算機運轉(zhuǎn)方式的基本理論設(shè)想。

牛牛文庫文檔分享第9頁/共49頁

1944年，美國哈佛大學(xué)教授艾肯領(lǐng)導(dǎo)和制造了用繼電器為元件的機電計算機

945年，美國賓夕法尼亞大學(xué)與阿伯丁彈道實驗室聯(lián)合開發(fā)了第一臺電子管計算機,1947年投入彈道設(shè)計使用，后經(jīng)多次改進成為能進行各種數(shù)值計算的通用計算機。

牛牛文庫文檔分享第10頁/共49頁

這臺計算機包括1.9萬個真空管，有30噸重，現(xiàn)存在華盛頓的史密斯研究所。這一時期，還生產(chǎn)了許多類似的高速數(shù)值計算的計算機，并且有了自動程序控制的功能。但同時期類似的計算機時常因電子管燒壞而停機檢修。更為嚴重的是，其程序是“外插型”而非“儲存型”。為了進行幾分鐘的運算，計算機的準備程序往往要花費幾小時，這就使得采用電子管而獲得的速度被大大抵消

牛牛文庫文檔分享第11頁/共49頁1946年6月，馮·

諾伊曼又提出了更完善的設(shè)計方案，對已有的計算機提出了三方面的改進設(shè)想：是用二進制取代十進制，以充分發(fā)揮電子元件在速度方面的潛力；是設(shè)置程序計數(shù)器，以保存當前欲執(zhí)行指令的地址——改外插型計算程序為內(nèi)置，從而使整個計算過程完全由電子計算機自動控制，并有效地提高了運算速度；是依據(jù)圖靈的理論模型，認為計算機的體系結(jié)構(gòu)應(yīng)由運算器、控制器、儲存器、輸入設(shè)備和輸出設(shè)備等五個部分組成，把“程序”和“數(shù)據(jù)”都放在儲存器中，并首次提出“中央處理器”（簡稱CPU）概念，而CPU則由運算器、控制器和程序計數(shù)器組成，這就是著名的“馮·諾依曼體系結(jié)構(gòu)”。

牛牛文庫文檔分享第12頁/共49頁國際計算機界普遍認為馮·諾依曼體系結(jié)構(gòu)的提出及其實現(xiàn)是現(xiàn)代電子計算機基本完善的重要標志。上述三個方面的改進最終于1949年在英國劍橋大學(xué)完成。

牛牛文庫文檔分享第13頁/共49頁1975年1月，當時還是哈佛大學(xué)法律系二年級的學(xué)生比爾·

蓋茨從《大眾電子學(xué)》封面上看到MITS公司研制的第一臺個人計算機照片。他馬上產(chǎn)生了一種新奇的想法：這種個人計算機體積小、價格低、可以進入家庭，甚至人手一臺，因而有可能引起一場深刻的革命——不僅是計算機領(lǐng)域的革命，而且是整個人類社會生活方式、工作方式的革命。針對當時以大型機、巨型機為主流的計算機發(fā)展的局面，比爾·

蓋茨敢于向傳統(tǒng)、權(quán)威挑戰(zhàn)。他寫信給MITS公司的老板，要為他的個人電腦配BASIC解釋程序（他知道若沒有便于用戶掌握的計算機程序語言，個人電腦難以普及），在他的好友艾倫的幫助下，花了五個星期時間終于出色地完成了這一任務(wù)。接著他從哈佛中途退學(xué)并和艾倫創(chuàng)辦了自己的公司“Microsoft”．聞名遐邇的“微軟”

牛牛文庫文檔分享第14頁/共49頁圖靈（1912~1954）

出生于英國倫敦，19歲進入劍橋皇家學(xué)院研究量子力學(xué)和數(shù)理邏輯。1935年，他從一名學(xué)生直接成為學(xué)院的研究員，并開始了“可計算性”研究。1936年4月，圖靈發(fā)表了“可計算數(shù)及其在判定問題上的一個應(yīng)用”的論文，形成了“圖靈機”的重要思想。用反證法證明，任何可計算其值的函數(shù)都存在相應(yīng)的圖靈機；反之，不存在相應(yīng)圖靈機的函數(shù)就是不具有可計算其函數(shù)值算法的函數(shù)。圖靈到美國學(xué)習(xí)，并于1938年獲美國普林斯頓大學(xué)博士學(xué)位。1939年秋，圖靈應(yīng)召到英國外交部通訊處從事密碼破譯工作，開始了最早的計算機的研究工作。他于1950年發(fā)表了“計算機和潛力”的論文，引發(fā)了“機器是否會思考”的學(xué)術(shù)討論。圖靈思想活躍，但性格內(nèi)向，1954年6月，圖靈在家中因氰化鉀中毒去世，原因則眾說紛紜，至今仍為一個謎。

9.2圖靈機與可計算性

牛牛文庫文檔分享第15頁/共49頁圖靈機（理論）

由三個部分組成：一條帶子，一個讀寫頭和一個控制裝置。帶子分成許多小格，每小格可存一位數(shù)（0或1），也可以是空白的。機器的運作是按逐步進行的方式，每一步由三個不同的動作組成：在任一確定時刻，讀寫頭對準帶子上的一個方格，根據(jù)該格上的內(nèi)容和機器的狀態(tài)決定自己的動作；機器可以抹去帶上的原有符號，使方格保持空白或者寫上另外的（也可以與原來相同的）符號；然后讓帶子通過讀寫頭，朝兩個方向之一移動一個方格

牛牛文庫文檔分享第16頁/共49頁

算法有效性的一種判定法則區(qū)分算法是否有效，要以圖靈機為基本的計算工具，用圖靈機上完成計算的步數(shù)（即圖靈程序）來評估一個算法是否有效。一般地，人們習(xí)慣于依據(jù)“計算時間”的長短來判定算法的有效性

“多項式時間算法”

:如果存在確定的整數(shù)A和k，對于長度為n的輸入數(shù)據(jù)，計算可以在至多Ank步內(nèi)完成（對任意的n值）。那么，這個算法被稱為“多項式時間算法”

牛牛文庫文檔分享第17頁/共49頁不是多項式時間算法的算法被稱之為“指數(shù)時間算法”。當一個算法處理長度為n的輸入數(shù)據(jù)時，若需要2n（或3n,nn,n!）步，它就是一個指數(shù)時間算法。

“有效”算法規(guī)定為需要多項式時間的算法。而將需要指數(shù)時間的算法規(guī)定為“非有效”算法。這種劃分方法只是“理論”的劃分方法，它與實際應(yīng)用還有一定的區(qū)別。對于相對大的n，后者總是大于前者

牛牛文庫文檔分享第18頁/共49頁假定一臺計算機每10-6秒執(zhí)行一次基本運算，對于已知的數(shù)據(jù)長度n，多項式時間與指數(shù)時間算法在計算機上的運行時間如下表：數(shù)據(jù)長度n

102030405060

n0.00001s0.00002s0.00003s0.00004s0.00005s0.00006sn20.0001s0.0004s0.0009s0.0016s0.0025s0.0036s

n30.001s0.008s0.027s0.064s0.125s0.216s2n

0.001s1.0s17.9分12.7天35.7年366世紀3n

0.059s58分6.5年3855世紀2×108世紀1.3×1013世紀

牛牛文庫文檔分享第19頁/共49頁P型問題，它是可解的。但是諸如旅行推銷員這類問題還不能說是無解的，而是歸入了稱之為NP型問題

人工智能的研究。根據(jù)符號轉(zhuǎn)換的定義，人腦或計算機進行的定理證明、文字處理和一切可歸結(jié)為符號處理的操作，都屬于計算的過程。1947年，圖靈論證了智能機器的可能性。1950年圖靈又根據(jù)計算機能進行符號計算的事實，提出計算機能像人類的思維方式進行思維的觀點，并給出了檢驗計算機是否具有思維的能力的一個實驗，這就是很著名的“圖靈檢驗”。1956年夏，美國的一批年輕的科學(xué)家提出人工智能的概念。1976年西蒙等人提出了假設(shè)：任何一個系統(tǒng)，如果它能表現(xiàn)出智能，則它必須具備執(zhí)行輸入符號、輸出符號、存儲符號、復(fù)制符號、建立符號結(jié)構(gòu)和條件性遷移操作這六種功能。反之，任何能執(zhí)行這六種操作的系統(tǒng)，必然表現(xiàn)出智能，這一假設(shè)有三個推論：第一，因為人有智能，所以人是一個符號系統(tǒng)；第二，因為計算機是一個符號系統(tǒng)，所以計算機可以表現(xiàn)出智能；第三，計算機能模擬人的職能。該假設(shè)為人工智能提供了一個理論基礎(chǔ)

牛牛文庫文檔分享第20頁/共49頁

9.3機器證明與吳法為實現(xiàn)幾何定理的機器證明，一般采用代數(shù)的方法，它需要解決以下幾個問題：

首先，引進數(shù)式與坐標系，使任何幾何定理的條件和結(jié)論都寫成代數(shù)式，從而幾何證明成為純代數(shù)問題。其次，將定理假設(shè)部分的代數(shù)關(guān)系式進行整理，第三，依確定的步驟，驗證定理結(jié)論部分的代數(shù)式可由假設(shè)部分的代數(shù)式推出。最后，按上述步驟編寫程序，并在計算機上實現(xiàn)

20世紀算法設(shè)計者面臨的任務(wù)是解決上述第二、三兩部分的難題。

1975年，吳文俊提出了定理的機器證明的方法：“吳法”

牛牛文庫文檔分享第21頁/共49頁1940年畢業(yè)于上海交通大學(xué)數(shù)學(xué)系，在上海教中學(xué)達五年半。1946年8月，進入陳省身所主持的數(shù)學(xué)研究所，開始拓撲學(xué)研究，1947年11月赴法國留學(xué)，并于1949年獲法國國家博士學(xué)位，1951年回國，任中國科學(xué)院院士，是2002年中國國家科技獎的獲得者吳文俊在拓撲學(xué)上的重要成就，是“復(fù)形在歐氏空間中的實現(xiàn)問題”，他利用拓撲學(xué)的性質(zhì)——示嵌類，開辟了解決這一問題的道路，這一成果被稱為“吳類”載入教科書與辭典吳法，使用變量的“三角化”、多項式除法的技巧，并給出幾何結(jié)論成立的判定準則，為幾何的機器證明創(chuàng)造了有效的算法機器證明研究一般又稱為自動推理研究，其涉及的領(lǐng)域相當廣泛。這一課題一列入在我國近些年的國家重點科研項目——攀登計劃項目中，目前，在幾何定理機器證明方面，我國處于國際領(lǐng)先地位。

吳文俊（1919~）

牛牛文庫文檔分享第22頁/共49頁四色問題猜想（英國古色里，1852年）：

對平面或球面上的任意一個地圖著色，至多用四種顏色就可以使相鄰（即有一段公共邊界而不是一點或有限點）兩個國家或地區(qū)（這里所謂的“國家”或地區(qū)是指連通的區(qū)域）的顏色不同一個淺顯易懂的命題引發(fā)了無數(shù)專家學(xué)者的極大興趣一個遲遲得不到解決的的命題1975年由美國計算機專家給出了機器的證明9.4四色猜想的機器證明

牛牛文庫文檔分享第23頁/共49頁英國數(shù)學(xué)家德·摩根（1806~1871）的工作

1、從特殊的構(gòu)圖（如右上圖）中認定：僅用三色是無法使相鄰國家著不同色，至少需要四種顏色。2、證明了：“五個國家，不能每個都和其余的（4個）相鄰”。由此使他相信四色猜想是對的。即，德·摩根假定了：著色所需要的顏色種數(shù)，與圖中相互毗鄰的國家的最大個數(shù)總是相等的然而，如右下圖所示：任意四個國家都與其它三個國家相鄰，但只用三種顏色著色是不行的（需使用A、B、C、D四種顏色）。因此，毗鄰國家的最大數(shù)不恒等于著色所需的種數(shù)。地圖上不能有五個彼此都相鄰的國家的論據(jù)，并不能保證四色猜想的成立。

牛牛文庫文檔分享第24頁/共49頁1879年，英國律師肯普（1849~1922）

英國律師肯普（1849~1922）的開創(chuàng)性工作（1879年）

1、證明了“五色定理”：一張畫在球面上的（完全任意的）地圖，可以用五種或更少的顏色來著色

2、肯普方法－－用機器證明四色猜想的基礎(chǔ)肯普四色猜想證明的漏洞機器后人的修補，形成了肯普方法

圖形可約性的概念:給定一張畫在一個球面上的（完全任意的）地圖，將兩個或更多個相鄰國家合并為一的過程（稱為約化過程）使得約化過程中所使用的每步操作不減少地圖著色所需要的顏色數(shù)如果最后可以得到一張至多有五個國家的地圖，就證明最初的地圖著色用五種顏色就夠了，即“五色定理”成立。這種證法的關(guān)鍵在于，描述將已知地圖約化為更簡單的形式(即有較少國家)而又不減少所需的著色顏色數(shù)的特殊過程

牛牛文庫文檔分享第25頁/共49頁肯普“五色定理”證明中的六種不同的約簡過程

（1）若一個區(qū)域完全被其他區(qū)域所包圍，（圖Ⅰ)，那么可以將里面的區(qū)域與包圍它的區(qū)域相合并．任何至少要用兩種顏色的新地圖的著色，都可以拓展成原地圖的需要同樣種數(shù)顏色的著色（2）若有四個或四個以上的區(qū)域在一點相接觸，那么這些區(qū)域中必定有一對區(qū)域沒有(在地圖上任何地方)公共邊界線，而這兩個區(qū)域就可以合并為一個(圖Ⅱ)．給了修改地圖的一種著色，原地圖也就可用同樣多種顏色來著色，只要使被合并的兩個區(qū)域在原圖中著相同的顏色，而其他區(qū)域的著色在兩種情形都保持一樣．反復(fù)應(yīng)用這一約簡過程，就可以將地圖修改成在每一頂點都只有三個接觸區(qū)域的情況．（3）若一個區(qū)域只有兩個相鄰區(qū)域，(圖Ⅲ)，那么可以使它與其他兩個區(qū)域中的一個相合并．如果新的地圖可以用至少三種顏色著色，那么原地圖也可以用同樣多種顏色來著色，只要給后被取消的中央?yún)^(qū)域著上與兩個外圍區(qū)域都不相同的顏色．

牛牛文庫文檔分享第26頁/共49頁

（4）若任何區(qū)域都有三個相鄰區(qū)域的話，都可以通過將它與鄰域之一合并而被“取消”(圖Ⅳ)，并且如果新地圖可以用至少四種顏色著色，那么原地圖也必可用同樣多種顏色著色，做法與上一種情形一樣（5）任何有四個相鄰區(qū)域的區(qū)域可以與它的一個鄰域合并(圖v)，在可以使用五種顏色的情況下，這樣做不會引起所需著色數(shù)的任何改變（6）考慮這樣一個有五條邊的區(qū)域P，如圖42(譏)所示，其鄰域為Q，R，S，T，U．P有一對鄰域相互沒有公共邊界，設(shè)為Q和S．將P，Q，S合并起來．如果新地圖可以用五種顏色來著色，那么原地圖也可以用五種顏色著色．使被合并的區(qū)域Q和S在原圖中著相同顏色這樣包圍P的區(qū)域用了四種顏色，剩下一種顏色用于P

整個約簡過程到此結(jié)束．每一步約簡都使地圖的區(qū)域數(shù)有所減少，反復(fù)約簡后最終可以得到一張至多有五個區(qū)域的地圖

牛牛文庫文檔分享第27頁/共49頁

“正規(guī)”地圖的概念：

沒有一個國家能包圍其它國家，也沒有三個以上的國家相遇于一點利用可約性方法不難證明：可以把一張非正規(guī)地圖修改成至少需要同樣多顏色的正規(guī)地圖。所以要想證明四色猜想，只要證明不存在正規(guī)的五色地圖就夠了

肯普證明了在每張正規(guī)地圖中，包括有兩個鄰國、三個鄰國、四個鄰國及五個鄰國組成的一組“構(gòu)形”是“不可避免”的，即每張正規(guī)地圖必定含有這組構(gòu)形的某一個通過檢驗地圖構(gòu)形的可約性，就成為解決四色猜想的重要途徑。然而使用這些方法來證明大的構(gòu)形可約，需要檢查大量的細節(jié)，似乎只有用計算機才能做到

牛牛文庫文檔分享第28頁/共49頁可約構(gòu)型檢驗的歷史積累

美國著名數(shù)學(xué)家伯克霍夫（1884~1944），用肯普的想法和他自己的新技巧，能夠證明某些大的構(gòu)形可約（1913年）弗蘭克林（1898~1965）利用這些結(jié)果證明了至多包括25個國家的地圖都可以用四種顏色著色（1938）伯克霍夫發(fā)展的方法在1913年至1950年間被許多數(shù)學(xué)家使用和改進，用這些方法建立了大量的可約構(gòu)形。在阿佩爾和黑肯給出猜想的最后證明之前，人們只證明了不超過包括96個國家的地圖上的四色猜想。但是，在伯克霍夫之后的四十年間所證明的全部可約構(gòu)形還不能證明四色猜想。

牛牛文庫文檔分享第29頁/共49頁1、利用地圖的平面網(wǎng)絡(luò)性質(zhì)來編制可約性的計算機的證明程序．

地圖的“對偶”形（又稱為網(wǎng)絡(luò)）：將每個國家變?yōu)橐粋€點（稱為頂點），相鄰國家用一條線段連接（稱為邊），邊將平面分為區(qū)域（稱為面），這樣正規(guī)圖的面就都由三角形組成。將每個頂點連接的邊數(shù)稱為頂點的次數(shù)。從一個頂點出發(fā)又回到同一頂點的邊、而且邊之間又不相交的路線把圖分為內(nèi)部與外部兩部分。這樣的一條路線稱為回路．德國數(shù)學(xué)家希爾的“放電法”－－四色猜想的機器證明的突破（1950年）

牛牛文庫文檔分享第30頁/共49頁

如圖，用細線表示的六個周圍國家在對偶圖形中就構(gòu)成有六個頂點、六條邊的一條回路。邊界回路稱為構(gòu)形的環(huán)。圖中的構(gòu)形（畫成對偶形式）稱為“六環(huán)”構(gòu)形，它的環(huán)有六個頂點，是由包圍了原構(gòu)形的六個國家組成的環(huán)。在對偶圖中，“構(gòu)形”是三角形的剖分（每個面都是三角形），，它由一組頂點加上連接這些點的所有邊組成，

牛牛文庫文檔分享第31頁/共49頁

2、“放電法”－－研究不可避免組的關(guān)鍵技術(shù)，而不可避免組在更加復(fù)雜的形式下它成為證明四色定理的中心要素

將平面網(wǎng)絡(luò)的每個頂點配置一個電荷：如果我們對每個次數(shù)為k（即有k個鄰國）的頂點指定6－k這個數(shù)（電荷量），則頂點次數(shù)為5的就帶有1個正電荷，次數(shù)6的頂點不帶電荷；次數(shù)為7的頂點帶電荷－1，依此類推。再由肯普的研究結(jié)論可知，整個網(wǎng)絡(luò)的電荷的和恰為12。這就表明每個平面三角剖分網(wǎng)絡(luò)的這個電荷之和恒為正值。

移動網(wǎng)絡(luò)中的正電荷，使正電荷從某些帶正電的（五級）頂點移動到帶負電的頂點，并且使全系統(tǒng)中的電荷不增不減。雖然這些移動不改變電荷的總和，但帶正電的頂點卻是可以變的；例如某些五次頂點可能失去全部正電荷（放電），而某些大頂點可能得到的電太多，結(jié)果變?yōu)檎姾身旤c（充電）。

牛牛文庫文檔分享第32頁/共49頁

“放電”的目的，是想找出一個明確的過程來精確描述怎樣移動電荷才能保證所剩下的每個帶正電的頂點一定屬于可約構(gòu)形。于是經(jīng)過“放電”使每個三角剖分必有電荷為正的頂點，用這種放電方法得到的構(gòu)形必然是“不可避免”的。如果這些構(gòu)形又都是可約的，則四色猜想就被證明了。這樣，四色猜想的證明就需要解決兩個問題：找出放電過程，同時證明它所產(chǎn)生的不可避免構(gòu)形是可約的。希爾自1936年開始研究四色問題，于1950年認識到只有借助能處理巨量數(shù)據(jù)的計算機裝置，才能解決四色問題。他提出的地圖的平面網(wǎng)絡(luò)、放電法，為編制可約性的計算機的證明程序提供了技術(shù)準備

牛牛文庫文檔分享第33頁/共49頁美國數(shù)學(xué)教授阿佩爾與黑肯的工作（20世紀七十年代）－－完成四色猜想的機器證明

1、面臨的問題

其一，可約構(gòu)形的任何一個不可避免組都可能含有很大的構(gòu)形（鄰國環(huán)含有多至十八個頂點），計算機所需的時間、存儲量的迅速增加，造成技術(shù)工具的困難，檢查14點環(huán)的構(gòu)形所需要的平均時間只有25分鐘，那么檢驗18點環(huán)的構(gòu)形所需要的平均時間就會超過100個小時，并且計算機所需的存儲量也大大超過當時的任何一種計算機的存儲量。其二，沒人知道恰好需要多少個可約構(gòu)形來形成一個不可避免組，這個數(shù)目似乎可能大到幾千。從計算時間來說，假如要想證明18點環(huán)的構(gòu)形可約，在有足夠存儲的計算機上需要100個小時。那么，當不可避免組里有一千個18點環(huán)構(gòu)形時，在一個極大的計算機上證明可約的時間將需要10萬個計算機時，這就超過了11年

牛牛文庫文檔分享第34頁/共49頁四色猜想的“機器證明”是否真的可靠－－方法、理念的沖突2、艱苦的嘗試（1972~1974）

“好構(gòu)形”的圖上進行放電過程的計算機檢驗工作修訂計算程序和放電過程

3、最后的沖刺（1976）

利用三部計算機運轉(zhuǎn)了一千多個小時，分析了兩千多個構(gòu)形的可約性，并通過人工分析了約一萬個帶正電頂點的鄰近區(qū)域，終于用不可避免組的證法證明了四色問題。在證明過程中，放電過程經(jīng)過500多次的修改設(shè)計，計算機檢驗了2000多個構(gòu)形并證明了1482個構(gòu)形的可約性。

牛牛文庫文檔分享第35頁/共49頁美籍數(shù)學(xué)家曼德勃羅特（1824~）發(fā)表的《分形：構(gòu)形、機遇和維數(shù)》(1975),

“fractal”（即“分形”）表示“不規(guī)則”、“碎片”的意思。分形幾何以研究不規(guī)則圖形（如分析學(xué)中的病態(tài)函數(shù)）性質(zhì)為目標，開創(chuàng)了不同于歐幾里得和牛頓模型的新的數(shù)學(xué)結(jié)構(gòu)的研究，并將計算機技術(shù)應(yīng)用于這一研究之中．分形概念、分形方法一經(jīng)問世，就呈現(xiàn)出極大的生命力。據(jù)美國科學(xué)情報研究所的統(tǒng)計，世界上一千二百多種權(quán)威學(xué)術(shù)刊物在80年代后期發(fā)表的論文中，與分形有關(guān)的就占37.5/%，其中包括自然科學(xué)、社會科學(xué)的諸多領(lǐng)域9.5分形幾何

牛牛文庫文檔分享第36頁/共49頁

經(jīng)典的幾何學(xué)（歐幾里得幾何學(xué)、解析幾何、射影幾何、微分幾何、拓撲學(xué)等）利用規(guī)則、簡單的、光滑的形態(tài)去近似地表達復(fù)雜的事物形態(tài)。它們以規(guī)則的、光滑的（或可微分）的空間形態(tài)為自己的研究對象，為我們研究規(guī)則圖形的空間關(guān)系和性質(zhì)提供了有效的工具

病態(tài)函數(shù)的出現(xiàn)，打破了傳統(tǒng)觀念，引起人們對曲線的關(guān)注

經(jīng)典的幾何學(xué)無法描述具有分形結(jié)構(gòu)的事物形態(tài)。曼德勃羅特對此評述道（1982）：傳統(tǒng)幾何學(xué)不能描述云、山脈、海岸線、樹木等物體的自然形狀。由于云團不是球形，山脈不是錐形，海岸線不是圓的，樹皮不是平滑的，閃電不是沿直線行進。自然界里還有許多其它種類的形態(tài)，都是一些非常不規(guī)則和破碎物體形狀的模型。這些被歐幾里得幾何認為無定型的表面幾何學(xué)要求我們?nèi)パ芯克中螌W(xué)的一個重要思想是曲線的維數(shù)可以是分數(shù)

19世紀末，人們利用一一對應(yīng)的方法，將二維（正方形）與一維（直線）圖形聯(lián)系在一起。原本屬于一維的曲線卻能“填滿”二維的平面，顯然傳統(tǒng)的維數(shù)概念就需要重新加以認識9.5.1不規(guī)則圖形與病態(tài)函數(shù)

牛牛文庫文檔分享第37頁/共49頁希爾伯特建立了單位線段到正方形上的連續(xù)映射（1891）

把單位線段和正方形都分成4個相等的部分，如圖左、中，得到4個一級子線段和4個一級子正方形，將它按順序編號，并按號數(shù)依次連接所有的子正方形中心，可得到一條無重疊點的折線l1。顯而易見，單位線段可以連續(xù)映射到折線l1上

再把每個一級子線段和每個一級子正方形分別四等分，再次對它們進行編號，同時按號連接二級子正方形的中心，得到一條無重疊點的折線l2。同樣，單位線段可以連續(xù)映射到l2上，如圖右。如此不斷地進行下去，會得到一系列折線序列l(wèi)n?？梢宰C明，當n趨于無限時，序列極限圖形是一條能夠填滿正方形的曲線

牛牛文庫文檔分享第38頁/共49頁傳統(tǒng)測量方法不適應(yīng)于分形圖形可微函數(shù)所對應(yīng)的曲線長度，可用積分公式求解。那么，沒有導(dǎo)數(shù)的函數(shù)曲線長度又怎樣確定呢？英國一位科學(xué)家在查閱了西班牙、葡萄牙、比利時、荷蘭的百科全書之后，驚奇的發(fā)現(xiàn)各國各自測量的共同的國境海岸線長度競相差20%。事實上，假設(shè)A、B分別用1公里、1米作度量單位測量海岸線，它們得到的值很不一樣。B測得的長度比A測得的長度要大得多，這里的問題就出在所用的度量單位上。B用的度量單位小，可以把1公里以內(nèi)的彎曲部分也量進去。如果A使用50厘米作為度量單位重新測量，那么測得的數(shù)值比B用1米作為度量單位的結(jié)果就大了很多。從這里就可以發(fā)現(xiàn)一個重要的數(shù)學(xué)問題：不可微曲線的長度將隨著度量單位的無限變小而趨于無窮大。曼德勃羅特認為：因為不可微曲線的維數(shù)是大于1的分數(shù)，而度量它的尺子的維數(shù)是1；根據(jù)分形的維數(shù)理論，其測量結(jié)果必然隨著量尺的縮短而變成無窮長。，傳統(tǒng)測量方法只能應(yīng)用于具有規(guī)整的、光滑的、可微的幾何圖形的量度，而不適合于度量不規(guī)整的、粗糙的、不可微的幾何圖形

牛牛文庫文檔分享第39頁/共49頁9.5.2“游牧者”的形象思維——分形幾何創(chuàng)立者曼德勃羅特的奇特思維方式與廣闊應(yīng)用研究領(lǐng)域

布爾巴基學(xué)派的叛逆者曼德勃羅特從小沒受過正規(guī)教育。據(jù)說他從來就沒有學(xué)過字母表，也沒有學(xué)過乘法表，但是他喜歡數(shù)學(xué)，而且?guī)缀沃庇X天賦出奇地好

廣泛涉取

的博學(xué)家1947年畢業(yè)于巴黎理工學(xué)院，1948年獲美國加利福尼亞理工學(xué)院碩士學(xué)位。1952年獲巴黎大學(xué)哲學(xué)（數(shù)學(xué)）博士學(xué)位，1958年，曼德勃羅特接受了國際商用機器公司沃森研究中心的聘請，并于同年移居美國。他曾先后在哈佛大學(xué)教過經(jīng)濟學(xué)，在耶魯大學(xué)教過工程學(xué)，在愛因斯坦醫(yī)學(xué)院教過生理學(xué)。曼德勃羅特的研究領(lǐng)域橫跨數(shù)學(xué)、物理學(xué)、地學(xué)、經(jīng)濟學(xué)、生理學(xué)、計算機、天文學(xué)、情報學(xué)、信息與通訊、城市與人口、哲學(xué)與藝術(shù)等眾多學(xué)科與專業(yè)。曼德勃羅特曾形象地稱自己是一位“游牧者”。他在《大自然的分形幾何》中寫道：“非常感謝這些研究領(lǐng)域的變化，正是因為對這些領(lǐng)域的問題的研究，才使得整個理論漸漸地形成……，最后導(dǎo)致了分形幾何的建立?！?/p>

牛牛文庫文檔分享第40頁/共49頁

標度不變性——分形幾何學(xué)的基本性質(zhì)

所謂標度不變性，是指在不規(guī)則點集（即分形集）上任選一局部區(qū)域?qū)λM行放大或縮小量尺，這時原來看上去是光滑的部分又會再現(xiàn)出原圖的復(fù)雜性質(zhì)。因此，對于分形圖，不論將其放大或縮小，它的形態(tài)、復(fù)雜程度、不規(guī)則性等各種特征都不會發(fā)生變化。標度不變性刻畫了一種圖形的自相似性質(zhì)。應(yīng)用標度不變性處理問題的方法稱為“標度不變性”方法

曼德勃羅特通過對詞頻分布、價格波動、海岸線長度以及湍流的實際問題的研究，找到了共同的研究方法——標度不變性方法，并且發(fā)現(xiàn)了這類對象的共同特點：粗糙和自相似。使自己的感性認識上升為理性認識，用數(shù)學(xué)模型描述這些現(xiàn)象的標度不變性，便成為曼德勃羅特進一步的研究課題。此后曼德勃羅特對于噪聲——這個工程技術(shù)的問題研究，使他把“病態(tài)函數(shù)”進一步做為“粗糙和自相似”形態(tài)的數(shù)學(xué)模型詞頻分布研究（１９５１年）曼德勃羅特注意到美國語言學(xué)家齊普夫關(guān)于詞頻（即單詞在一篇文章中或一本書中出現(xiàn)的頻率）分布研究結(jié)果，由此引發(fā)了曼德勃羅特對分形幾何的研究。

牛牛文庫文檔分享第41頁/共49頁

詞頻分布是各種情報學(xué)的基本問題。齊普夫通過大量實驗數(shù)據(jù)的統(tǒng)計分析，得到了齊普夫定律（1949），曼德勃羅特運用標度不變性概念，進一步對詞頻分布的規(guī)律進行了分析，得到了比齊普夫定律更精確的結(jié)果：詞頻分布幾乎完全服從雙曲分布，齊普夫定律代表著中頻區(qū)的詞頻分布情況，而在高頻區(qū)或低頻區(qū)的分布表現(xiàn)著不同程度的自相似，而這恰恰是分形圖形的基本特征

價格變動規(guī)律

在曼德勃羅特之前的學(xué)者，一般采用巴舍勒（1900）的觀點；任何競爭價格都遵從“一維的布朗運動”的函數(shù)B(t)，這是一個關(guān)于時間t的連續(xù)（或幾乎處處連續(xù)）的函數(shù)。曼德勃羅特通過棉花價格的研究，再一次使用了標度不變性方法。他從實驗中獲得的結(jié)果表明，實際數(shù)據(jù)并不能很好的滿足B(t)，而競爭價格也不必是連續(xù)的，用一個連續(xù)函數(shù)去刻劃一個不連續(xù)的隨機變量顯然是不合理的。受詞頻研究中所使用的標度不變性方法的啟發(fā)，曼德勃羅特對價格規(guī)律作了適當?shù)男拚?，而得出一個猜想：價格變化是服從穩(wěn)定的非正態(tài)分布

曼德勃羅特在1963年和1967年把自己的理論用于許多商品的價格、利率以及19世紀的一些證券價格的檢驗，法瑪在1963年對當時的證券價格，羅爾于1970年對其他的利率的研究，都驗證了他的猜想對實踐是有效的

牛牛文庫文檔分享第42頁/共49頁湍流研究與海岸線長度的分維思想（1962~1964年）曼德勃羅特在哈佛大學(xué)任客座教授期間，經(jīng)伯克霍夫教授的指點，注意到標度方法與湍流研究方法很類似，于是從幾何學(xué)的角度探討了湍流的機理，并形成了海岸線長度的分維思想。由于湍流的幾何研究的首要問題是區(qū)域的邊界形態(tài)，這確實是一個比較復(fù)雜的問題。為了研究的方便，曼德勃羅特先選取比較簡單的形狀，把它限制在平穩(wěn)的范圍內(nèi)，即湍流尾流或?qū)嶒灁嗝妗Ｋㄟ^對這樣的邊界的仔細考察后發(fā)現(xiàn)，這個相當明顯而復(fù)雜的“局部”結(jié)構(gòu)，明顯地具有自相似的特點

噪聲研究與康托三分集（自相似圖形的數(shù)學(xué)模型之一）噪聲是表示不規(guī)則的、隨機的波動和誤差。在當代物理學(xué)中，誤差分布造成的噪聲分布是離散的，用指標函數(shù)加以刻劃：在沒有誤差的的時刻t1內(nèi)取值為0，而在有誤差的時刻t2內(nèi)取值為1

曼德勃羅特對于誤差的分析是采用如下逐漸加細的方法。首先，初步確定一段沒有誤差的時間段，就稱這段時間為0級中斷，稱在這個0級中斷兩側(cè)的時間間隔為0級誤差脈沖；然后再對這個0級誤差脈沖分為三段來考慮，這時稱比較短的沒有誤差的時間段為1級中斷，相應(yīng)地稱其兩邊的時間間隔為1級誤差脈沖。同樣的辦法，我們會繼續(xù)得到2級中斷和2級誤差脈沖，等等，每次都將上一級的誤差脈沖分為三段

。他很快把自己的研究和三分康托集聯(lián)系了起來。

牛牛文庫文檔分享第43頁/共49頁三分康托集

——

自相似圖形的數(shù)學(xué)模型曼德勃羅特認為可以用三分康托集作為描述噪聲主要特征的數(shù)學(xué)模型。但是，三