(繁)互联网的数学数学在今日社会的应用.ppt

丘成桐教授 美 國 哈 佛 大 學 數 學 系 教 授 香 港 中 文 大 學 數 學 講 座 教 授 香 港 中 文 大 學 數 學 科 學 研 究 所 所 長 菲 爾 茲 獎 得 獎 人,The Value of Mathematics in,Todays Society,數學在今日社會的應用,今日很高興的在這裏和公開大學的同學談談我自己對數學服務社會的看法。 公開大學這麼多年來訓練了許多有上進心的青年，使我欽佩，在五十年代，除了香港大學外，沒有一家政府承認的大學，中文大學前身的崇基、新亞、聯合和當時的浸會學院吸收了香港很多人材，當時無論老師和學生都很窮苦，但是以後卻成為社會的中堅份子。我想公開大學的學生也會成為香港的人材，為二十一世紀的新中國服務。,這十多年來，香港、中國和整個亞洲社會都逐漸轉型，尤其是中國改革開放以後，香港社會所需要的人材更多姿多采。亞洲各國要與全世界的經濟、文化、科學接軌，而中國大陸和日本會領導亞洲的發展，所以香港的青年也應當訓練自己來適應這個趨勢。沒有辦法迎接這個新時代來臨的青年恐怕要吃虧。 縱觀全世界大學訓練人材的最基本要求乃是語文和數學，所有美國大學都看SAT的成績，而SAT中最基本的乃是這兩門學問的考試。這為的是甚麼呢？,語文訓練使我們能夠表達自己的意思，數學訓練讓我們具有推理的能力，沒有這兩種能力，我們實在很難說我們是具有文化氣息的現代人。 很多人對於數學不切實際的看法，以為數學家都躲在象牙塔裏，不食人間煙火，這是極為錯誤的看法。事實上，整個智識型的現代社會極度需要經濟、工程、管理等等方面的人材，而在現代化的前提下，這些人材都需要相當程度的數學訓練。,一般來說，數學訓練分兩個層次，一個層次是在象牙塔裏的為了追求純真純美的研究，表面上這些研究與實用毫無關係，從前我們知道這些研究十多年或數十年後總會有大的用場，但是近二十多年來，我們發覺純數學和應用的距離愈來愈縮小距離了。 數學的第二個層次就是在各行業上的應用，這是今天演講的主題。,二十一世紀的重要科學,近年的科技發展,都需要很多數學的支援,醫學素描，生物色素分佈(豹紋、虎紋)，DNA結構，量子物理，材料科學，半導體，財經科學，大型晶體結構，互聯網,Radon Transform, Diffusion Equation, Knot Theory, Gauge Theory, Mathematics Computation on Quantum Mechanics, Many Body Model, Inverse Problems,數學研究對科學的貢獻,美國政府Labor Dept. 關於大學畢業生報告的一段話,Other (non-mathematics) occupations that require extensive knowledge of mathematics include actuary, statistician, computer programmer, system analyst, system engineer, operation research analyst. A strong background in mathematics also facilitates employment in engineering, economics, finance, and physics.,其他需要深入數學知識的行業包括精算、統計師、程式編寫、系統分析、系統工程、運籌分析等。而數學基礎良好往往有助於發展工程、經濟、財務及物理等事業。,美國政府Labor Dept. 關於大學畢業生報告的一段話,數學為基礎的多元發展,從事其他學科研究的，包括：,電子計算、經濟、統計、財務、風險管理、社科、哲學,還有從事非學術研究的各行業的,圖像壓縮,數據保安,數學與社會,物流,風險管理,數據壓縮 (JPEG 2000),小波 (Wavelet) 壓縮,如果 A 是平滑的，那麼 Di 就很小,Si = A 的平滑部份,Di = A 的高頻部份,A,一個信號和它的小波變換,原始信號,變換後信號,圖像是平滑的 壓縮 = 刪除小的 Di,小波壓縮：,考慮以下 16 個數字：,A = 1, 2, 3, 4, 5, 6, 7, 8, 8, 7, 6, 5, 4, 3, 2, 1,S1 = 3, 7, 11, 15, 15, 11, 7, 3,D1 = 1, 1, 1, 1, 1, 1, 1, 1,兩兩相加：,A = S1 D1,兩兩相減：,對S1重複剛才的程序： S2 = 10, 26, 26, 10 D2 = 4, 4, 4, 4,對S2重複剛才的程序： S3 = 36, 36 D3 = 16, 16,S1 = S2 D2,S2 = S3 D3,最後，我們有 S4 = 72，D4 = 0,S3 = S4 D4,以魚骨來表示：,因此 A = S4 D1 D2 D3 D4,JPEG (Fourier) 對 JPEG 2000 (小波),未經壓縮處理的 原有圖像的大小 為 15 MBytes,再壓縮,幾何訊息的壓縮,將三維圖形影射到球上 在球上找一組互相垂直的多項式 ( 球面調和多項式 ) 將三維訊息由這組多項式展開 壓縮訊息只要保持其中足夠多的多項式,圖像影射到圓球體上,壓縮 256 倍後的圖像,原來的圖像,數據保安,數學與社會,RSA 公鑰密碼,傳統密碼需要大量密鑰以至密鑰的分配及管理極為困難 現代保密的常用做法是由 Rivest, Shamir, Adleman 於1978年提出 安全性是基於大整數分解 ( 已知是一個計算來說極為困難的問題 ) 加密鑰可以公開因此稱為公鑰密碼,解密算法依賴數論中的 Fermat 定理 破解 RSA 密碼的主要方法大數分解是數論中一個重要課題 現今最快的全面性大數分解算法依次為：二次域篩法，數域篩法，橢圓曲線法均建基於深刻的數學上,RSA 公鑰密碼的數學,n = 63,978,486,879,527,143,858,831,415,041,一個例子,我們取公鑰 e = 1193及,轉化為一個84位的數字：,2305000118050021140405180001 2020010311001201211403080020 0805001309191909120500141523,加密後變成：,C1 = 1060546943595003247867569919 C2 = 2485275951856773770355929250 C3 = 13101173280250715817550140912,前述的 n 是兩個大素數 p 和 q 的乘積 要破解密碼必須找到 p 和 q，大數分解就派上用場,n = 63,978,486,879,527,143,858,831,415,041 = p q = 440,334,654,777,631145,295,143,558,111 取 r = (p-1) (q-1) = 63,978,486,879,526,558,229,033,679,300,用公鑰 e 算出一個密鑰 d 滿足 e d 1 (mod r) , 1 d r d = 30,568,095,156,186,201,333,234,581,057 解密算法： Cd (Me)d M (mod n),原文,這個大數經過十七年才給人用二次域篩法分解出來,3490529510847650949147849619903898133417764638493387843990820577,32769132993266709549961988190834461413177642967992942539798288533,RSA 於 1977 年提出用,n = RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541,在2002年，三位印度數學家，Agrawal, Kayak 和 Saxena 發現如何用快速方法來決定一個大整數是素數的方法。這個方法有助於上述 RSA 中因子分解的問題。主要的觀念如下：,設 p 為奇正整數，而 a 為任一與 p 無公約數的整數，則 p 為素數的充份必要條件為 (x-a)p = xp - a (mod p),三位印度數學家發現去驗證上述的條件的最佳手法為找到另一正整數 r，使得 (x-a)p = xp - a (mod xr-1, p) 這個計算極為快速，只須大約 r2 log p 步的計算即可。,數學與社會,物流,貨物及訊息傳輸的數量和容量，都正在急劇上升，令目前的網絡架構設施不勝負荷，引致用戶不勝其煩,互聯網之應用日益廣泛 如：電子商貿、網上電台等,物流與互聯網絡,國際及中港商貿 (CEPA, 9+2) JIT 以減少存倉成本,到達時間,離開時間,貨運大樓,香港空運貨站中的貨物傳輸,航機班次和容量,重量,裝載/拆卸貨物,服務時間,自動化貨物處理及貯存系統,超前時間,路徑的取捨,以最短路徑傳遞貨物及訊息 假如網絡暢通無阻，我們會以最短路徑傳遞貨物及訊息，節省傳遞時間,減低擠塞 若網絡十分擠塞，我們需要尋找別的路徑，避免擠進閉塞的路徑,排隊論 (Queuing Theory),如何建立一個有效的數學模型？,預算不同地域、不同時間網絡的使用量,預算貨物及訊息的到達時間和大小 避免眾多貨物及訊息在同一時間擠進單一伺 服器或同一地域內,圖論 (Graph Theory),在網絡上尋找最短路徑,尋找所有發送人與接受者之間的可行路徑,國際互聯網絡,1,1,3,1,2,公開大學,中文大學,4,4,2,5,3,7,5,8,2,4,6,7,8,2,1,1,1,1,4,1,由中文大學往公開大學的最短路徑,一個數學家創富的故事 F. Thomson Leighton,麻省理工學院應用數學系教授 Akamai Technologies Incorporate (網路數據快遞服務商) 的創辦人 市場總值逾廿多億美元,Akamai 的成功之道,傳統的網絡架構,單一訊息來源 網絡呈樹狀形態 若某一伺服器發生故障，其分枝將會癱瘓，訊息將無法傳遞至使用者,系統在首次發出訊息時，會將訊息複製及傳播至網絡邊緣 無間斷地傳遞訊息至全世界每一個角落 若部份伺服器、甚至網絡中樞發生故障，Akamai 仍能在鄰近的伺服器內提取使用者所需的訊息,Akamai 分配系統,利用圖論、運籌學計算伺服器的最佳擺放位置,Akamai 的網絡覆蓋全球 54 個國家,數學與社會,風險管理,風險管理,甚麼叫風險 (Risk)？ 一般來說，風險是關乎災難發生的可能性。 災難的例子： 911 事件 (紐約) SARS 地震,風險可以定義作由災難而導致損失的或然率，這個觀念可以用統計學上的標準偏差 (Standard Deviation) 來描述。現在我們來解釋客觀風險 (Objective Risk) 這個觀點。,例如，某保險公司一年接受 1000 次火險的投保，由過去 5 年的數據得知在兩個不同區域有如下數據：,在這兩區域上，平均值為 10，所以損失的概率為 10/1000 = 0.01，可是在這兩個不同區域有不同的標準偏差，在第一個區域為 2，在第二個區域為 4。,正態分佈 (Normal Distribution) 例子：學生某次測驗成績的分佈,正態分佈主要取決於兩個參數：平均值和標準偏差,現在假定出事事件的發生分佈為正態分佈。 在區域一，它會有平均值 10 和標準偏差 2。 在區域二，它會有平均值 10 和標準偏差 4。,於是，在區域一，我們應當預期明年的數量會在 10 2 x 2 = 6, 14 中間。 在區域二，則為 10 2 x 4 = 2, 18 中間。 所以在第一區域，可能發生的事件為 8 件。 在第二區域，可能發生的事件為16件。,客觀風險,雖然可能發生的或然率在區域一和區域二是一樣的，但是區域一的風險為 8/2 x 1/10 = 0.4，而區域二為 16/2 x 1/10 = 0.8，所以我們知道第二區域比第一區域風險為大。,現在假設保險人數增加一百倍，由一千人增加到一萬人，則預期事件會增加為 100 x 10 = 1000。 但第一區域的標準偏差則為 而第二區域的標準偏差則改為,因此，對區域一，發生的事件會在 1,000 2 x 20 = 960, 1040 中間，而客觀風險等於 0.04。 對區域二，則會在 1,000 2 x 40 = 920, 1080 中間，而客觀風險為 0.08。 可見當數目增加後，客觀風險大量減少，這是 Law of Large Number 的一部份。,保險業,保險業的做法乃是將個人的風險分散到眾人身上。 當人數夠多時，我們對損失的或然率會估計得較為準確，而使得公司風險減少。 但這些都由所謂 Law of Large Number 得出的結果，我們必須由假設每次損失的事件互不相關，不能預測並且並非人為的。,金融科學裏面的數學： 在對沖基金中有不同的手法來減少投資