數(shù)學(xué)-通往資訊的終南捷徑課件

1、數(shù)學(xué)-通往資訊的終南捷徑張鎮(zhèn)華 臺(tái)灣大學(xué)數(shù)學(xué)系演講內(nèi)容數(shù)學(xué)的基本在於計(jì)算電腦可幫忙數(shù)學(xué)計(jì)算資訊科學(xué)奠基於數(shù)學(xué)電腦應(yīng)用的數(shù)學(xué)理論演算法中小學(xué)老師的角色數(shù)學(xué)的基本在於計(jì)算-13 + 5 = ?8 + 9 = ?2 x 5 = ?384 x 426 = ?1 + 2 + + 100 = ?數(shù)學(xué)的基本在於計(jì)算-23 + 5 = ?*1 *2 *3 *1 *2 *3 *4 *5* * * * * * * *1 2 3 4 5 6 7 8數(shù)學(xué)的基本在於計(jì)算-38 + 9 = ?另類解法: 8 = 10 2, 9 = 10 1,由 2 + 1 = 3,得 8 + 9 = 20 3 = 17.數(shù)學(xué)的基本在於計(jì)

2、算-42 x 5 = ? * * * * * * * * * * * * * * * * * * * * 數(shù)學(xué)的基本在於計(jì)算-5384 x 426 = ? 163584.1 + 2 + + 100 = ? (1+100) x 100/2 = 5050.電腦可幫忙數(shù)學(xué)計(jì)算-16是完全數(shù). 上帝利用6天的時(shí)間創(chuàng)造世界.28是完全數(shù). 月亮繞地球一圈走了28天.電腦可幫忙數(shù)學(xué)計(jì)算-2一個(gè)正整數(shù)如果等於比它小的所有正因數(shù)的和, 則稱為完全數(shù).6 = 1 + 2 + 3.28 = 1 + 2 + 4 + 7 + 14.496 = 1+ 2 + 4 + 8 + 16 + .電腦可幫忙數(shù)學(xué)計(jì)算-3完全數(shù)是不

3、是無限多個(gè)? 到目前為止不知道!是不是有奇完全數(shù)? 到目前為止不知道!除了6, 28, 還有那些偶完全數(shù)?電腦可幫忙數(shù)學(xué)計(jì)算-4歐基里德定理. 一正偶數(shù)是完全數(shù)的充分必要條件是, 這個(gè)數(shù)可以寫成 2(n 1) (2n 1) 的樣子, 其中2n 1為質(zhì)數(shù).6 = 21 (22 1).28 = 22 (23 1).電腦可幫忙數(shù)學(xué)計(jì)算-5形如2n 1的質(zhì)數(shù)稱為梅仙尼質(zhì)數(shù).如果2n 1是質(zhì)數(shù), 則n也是質(zhì)數(shù).到目前為只止找到34個(gè)梅仙尼質(zhì)數(shù).電腦可幫忙數(shù)學(xué)計(jì)算-6n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 512, 607, 1279, 2203

4、, 1257787 電腦可幫忙數(shù)學(xué)計(jì)算-7http:/research/primes/mersenne/黃文璋, 完全數(shù)與梅仙尼質(zhì)數(shù), 數(shù)學(xué)傳播21卷3期, 民國86年9月.http:/.tw電腦可幫忙數(shù)學(xué)計(jì)算-8圓周率就是圓周和半徑的比率.3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 電腦可幫忙數(shù)學(xué)計(jì)算-9利用arctan的Taylor展開式求pi的值.王九逵, 怎樣算pi, 數(shù)學(xué)傳播10卷2期, 民國75年6月.資訊科學(xué)奠基於數(shù)學(xué)-1布耳代數(shù)出自十九世紀(jì)英國學(xué)者布耳(G. Boole, 1815-1864) 所著

5、”思維規(guī)律的研究”.MIT學(xué)生夏濃(C. Shannon, 1916-)的碩士論文以此為基礎(chǔ),定義資訊的計(jì)算單位, 稱為位元.資訊科學(xué)奠基於數(shù)學(xué)-2not 1 = 0 not 0 = 11 and 1 = 1 1 or 1 = 11 and 0 = 0 1 or 0 = 10 and 1 = 0 0 or 1 = 10 and 0 = 0 0 or 1 = 0資訊科學(xué)奠基於數(shù)學(xué)-31 xor 1 = 0 1 or 1 = 11 xor 0 = 1 1 or 0 = 10 xor 1 = 1 0 or 1 = 10 xor 0 = 0 0 or 1 = 0資訊科學(xué)奠基於數(shù)學(xué)-4 00000011

6、 + 00000101 = 00001000 第1位得0 (= 1 xor 1 ) 進(jìn)1 (= 1 and 1)資訊科學(xué)奠基於數(shù)學(xué)-5英國數(shù)學(xué)家杜林(A. Turing, 1912-1954)於1937年提出通用電腦的概念, 現(xiàn)在俗稱杜林機(jī).為紀(jì)念杜林, 後人成立杜林獎(jiǎng), 是現(xiàn)在理論計(jì)算機(jī)界的最大獎(jiǎng).姚期智獲得2000年杜林機(jī).資訊科學(xué)奠基於數(shù)學(xué)-6Daniel Hills著, 林遠(yuǎn)志與陳振男譯, 電腦如何思考, 天下文化, 科學(xué)大師系列(13).電腦應(yīng)用的數(shù)學(xué)理論-1楊重駿,楊照崑, 數(shù)論在密碼上的應(yīng)用, 數(shù)學(xué)傳播26卷2期及3期, 民國86年9月及12月.R.L. Rivest, A. S

7、hcmir and L. Adleman, Communication of ACM, 1978, pp. 120-126.電腦應(yīng)用的數(shù)學(xué)理論-2代換法: 我有一個(gè)秘密對你說 3314 1432 0001 (0 1 2 3 4 5 6 7 8 9)(2 3 5 7 6 4 9 0 8 1) 7736 3675 2223 電腦應(yīng)用的數(shù)學(xué)理論-3置換法: 7736367522231456 7 52 6 7 7 2 5 3 6 2 4 63 31 7526 7725 3624 6331電腦應(yīng)用的數(shù)學(xué)理論-4費(fèi)馬小定理. 如果a不被質(zhì)數(shù)n整除, 則a的n1次方除以n得到的餘數(shù)是1.尤拉定理. 如果a和

8、n互質(zhì), 界於1和n之間恰有m數(shù)和n互質(zhì),則a的n1次方除以n得到的餘數(shù)是1.電腦應(yīng)用的數(shù)學(xué)理論-5利用尤拉定理及mod運(yùn)算的基本性質(zhì), 可造出“公開式密碼”, 著名的如Rivest-Schmir-Adleman (RSA) 法.電腦應(yīng)用的數(shù)學(xué)理論-6射影幾何與虛擬實(shí)境.離散數(shù)學(xué)與網(wǎng)路理論.排隊(duì)理論與通訊網(wǎng)路.網(wǎng)頁的搜尋.指紋及臉形判別.演算法-1演算法 Algorithm代數(shù) AlgebraA step-by-step procedure for solving a problem or accomplishing some end.演算法-2時(shí)間複雜度的重要性排序?qū)1, a2, , an

9、由大到小排序.例如: 3, 11, 4, 38, 9, 10.排成: 38, 11, 10, 9, 4, 3.演算法-3 3, 11, 4, 38, 9, 1011, 3, 4, 38, 9, 1011, 4, 3, 38, 9, 1011, 4, 38, 3, 9, 1011, 4, 38, 9, 3, 1011, 4, 38, 9, 10, (3)演算法-4Bubble sort 所費(fèi)時(shí)間O(n2).Insertion sort 所費(fèi)時(shí)間亦同.Selection sort 所費(fèi)時(shí)間亦同.Quick sort 平均較快.Heap sort 費(fèi)時(shí)O(n log n) .演算法-5給定n個(gè)實(shí)數(shù)a1, a2, , an, 找出和為最大的一段連續(xù)部份.3 -1 -4 1 -5 7 -5 6 -9 4 7 -5 6有O(n3)算法. 能不能更快?演算法-6各種設(shè)計(jì)方法: 分治法, 動(dòng)態(tài)規(guī)劃, 貪求法, 分枝法. 演算法-7近似算法.平行演算法.隨機(jī)演算法.量子計(jì)算.中小學(xué)老師的角色-1教學(xué)生數(shù)的表示法.十進(jìn)位: 92 二進(jìn)位: 1011100八進(jìn)位: 134 (1011100)十六進(jìn)位: 5C (1011100)中小學(xué)老師的角色-2數(shù)學(xué)歸納法與遞迴. gcd(90, 48)= gcd(48, 42)= gcd(42, 6