离散数学中许多有趣的问题.ppt
《离散数学中许多有趣的问题.ppt》由会员分享,可在线阅读,更多相关《离散数学中许多有趣的问题.ppt(40页珍藏版)》请在三一文库上搜索。
1、離散數學中許多有趣的問題,By 孫一凡 老師,簡介,離散數學亦稱組合數學。自古的數學,算術與幾何便分別代表了離散與連續觀念的源頭。 兩種思維相互發展,造就了數學世界。但自牛頓開創微積分以後,連續性數學便獨領風騷三百年。今日離散數學的若干題材,雖可在數論、代數、機率、幾何等學科中發現其身影,但始終是理論深度不明的研究課題。,本世紀以來,離散的工具與方法,逐漸在各個學科中被發展及使用,而產生出新的焦點及新的科學意識。一些彼此關連的研究領域,開始匯聚。 特別自三十年代以後,計算科學在理論與實用上都有突破性的發展。這是因為電腦的出現。電腦利用離散的表示處理資訊,離散現象的重要開始被重視。此外,電腦幫人
2、處理大量的有限數及有限結構,跑出了很多新層次的問題需研究。,離散數學包含了什麼?,包羅了許多學域,比較重要的包括下列幾種: 古典計算問題,包括有限集合上的各類排列組合問題 以代數、拓樸方法建立組合學體系的研究 以群論、有限幾何為主要工具的設計理論(Design Theory) 圖形、網路與超圖的理論(Hypergraphs),請修:組合設計初步,請修:圖論初步、離散專題,請修:離散數學,離散數學包含了什麼?,最佳化、運籌學(Operation Research)與賽局理論(Game Theory) 編碼(Coding Theory)與密碼理論(Cryptography) 擬陣(Matroid)
3、、廣義擬陣論(Greedoid) 離散與計算幾何學 演算法則的設計與分析,請修:代數編碼學、密碼學,請修:演算法,離散數學有些什麼應用?,在應用方面,最大的市場之一是資訊科學,已成為資訊系的必修課程。數位化的產物,如光碟、大哥大、衛星通訊等等都仰賴錯誤糾正碼(Error Correcting Code)設計以增加可靠性;提款卡、簽帳卡等也是密碼學的附產品;另外,DNA的定序問題,選舉權力的分析,生物食物網的平衡,實驗設計的安排,處處可見離散數學應用的例子。,討論整數 也可說是組合數學的重要關鍵,整數(Z)與實數(R)不同,兩者分別代表了離散觀念與連續觀念。 因此離散數學中,整數的觀念通常相當重
4、要,整數與整數的關係也是如此,可以廣泛的應用在許多事上。,正整數 : 1,2,3,4,5,6, 零 : 0 負整數 : -1,-2,-3,-4, 單數(奇數) : 1,3,5, 雙數(偶數) : 0,2,4,6, ,先看一些整數的性質 來熱熱身!,性質 1 :,奇數: (odd) 被2除餘1的數字 任何奇數都可表為 2n+1 的形式 偶數: (even)可被2整除的數字 任何偶數都可表為 2n 的形式,動動腦 1 某班49位同學,坐成七行七列。每個座位的前後左右稱做它的鄰座。要同時讓這49位同學中的每一位都換到他的鄰座上去,是否能辦到?,提示,當一聲令下,所有同學都換到他們的鄰座時,原本坐 位
5、子的同學會換到原本就坐 的位子,可是 . . . . :24個 :25個 所以,不可能!,性質 2 :,奇數 + 奇數 = 偶數 偶數 + 偶數 = 偶數 奇數 + 偶數 = 奇數 奇數 - 奇數 = 偶數 偶數 - 偶數 = 偶數 奇數 - 偶數 = 奇數,動動腦 2 設 a1, a2, a3, ,a8 是1,2,3,8的一種任意排列。 (如:1,8,7,6,5,2,3,4) 令 b1=|a1-a2|,b2=|a3-a4|, ,b4=|a7-a8| c1=|b1-b2|,c2=|b3-b4| =|c1-c2| 這樣一直做下去,最後得到的整數一定會為偶數。,例如:,1, 8, 7, 6, 5,
6、 2, 3, 4 7 1 3 1 6 2 4,4, 8, 1, 6, 5, 3, 2, 7 4 5 2 5 1 3 2,Why?,1. a1+ a2+ a3+ + a8 = 1+ + 8 = 36 2. b1=|a1-a2|,b2=|a3-a4|, b3=|a5-a6|,b4=|a7-a8| 則 b1+b2+b3+b4 =|a1-a2|+|a3-a4|+|a5-a6|+|a7-a8| = ? 如何將絕對值拆掉? 3. 若a1a2 則|a1-a2|= a1-a2 a1a2 則|a1-a2|= a2-a1,4. 假設絕對值都拆掉了,上式會變成如 = (a1-a2)+(a4-a3)+(a6-a5)+
7、(a7-a8) = (a1+a4+a6+a7)-(a2+a3+a5+a8) 之類的 (總之,有4個數字在前括號中,另外4 個數字在後括號中) 5. (a1+a4+a6+a7)+(a2+a3+a5+a8) = 36 因為A+B=偶數,則A,B必同為偶數或同為 奇數,所以A-B必為奇-奇或偶-偶 = 偶數 6. 如此一來,上一列的總和為偶數,下一列 的總和也必為偶數,則最後的必為偶數,動動腦 3 在平面上任意標出五個整數座標的點。 證明:其中必至少有兩個點,它們的連線的中點也是整數座標的點。 提示1:(x1,y1)與(x2,y2)的連線中點座標為 (x1+x2)/2,(y1+y2)/2) 提示2:
8、整數點只會有以下四種奇偶性: (奇,奇) (偶,偶) (奇,偶) (偶,奇),根據鴿洞原理,5個整數點中必有某兩點的奇偶性相同! (因為奇偶性總共只有四種,點有五個) 而當兩點(x1, y1), (x2, y2)有相同奇偶性時 x1+ x2 與 y1 + y2都是偶數 即 (x1+x2)/2 與 (y1+y2)/2皆為整數 (x1+x2)/2,(y1+y2)/2)為整數點,性質 3,1. 奇數個奇數的和必為奇數 2. 如果若干個整數a1a2a3的連乘積 是奇數,則其中每個數ai都是奇數,動動腦 4 設 n 為一奇數。又設 a1,a2, ,an 是1,2, ,n 的任意一種排列。 求證: (1-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 许多 有趣 问题
链接地址:https://www.31doc.com/p-2608332.html