課程概述 |
一、內容:
組合學研究離散物件的存在、計數、分析與最佳化的問題。組合學具有廣泛的應用性,物理、化學、統計、計算機科學、社會科學、生命科學都有用到組合工具的機會,也提供了新興的問題來源,刺激了組合學的進展。
本課程以一年時程,每學期三學分,介紹組合學的基本理論與方法。除了數學系、所同學可以選修外,也歡迎外系同學選修。第二學期講授要目如下:
1、Steiner 三元組:直接建構法,遞迴建構法,裝填與覆蓋
2、有限幾何學:有限體上的線性代數,Gauß 係數,射影幾何,射影平面
3、Ramsey 理論:鴿籠原理,Ramsey 定理,Ramsey 數的界,無窮型
4、偏序,束,擬陣:偏序與束,偏序的線性擴充,可分配束,鏈與反鏈,偏序的Möbius 函數
5、劃分與對稱函數:圖表與共軛類,Euler 五角數定理,表格與對稱函數
6、自同構群,置換群:軌道與遞移性,Schreier - Sims 演算法,本原性與多重遞移性
7、在群作用下的計數:軌道計算引理,循環圈指標,直積與圈積,重訪 Stirling 數
8、組合設計:實例,Fisher 不等式,從有限幾何來的設計
9、揪錯碼:線性碼,Hamming 碼,完美碼,線性碼與射影空間
二.參考書(教科書):
Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994
三.成績評量方式:
作業:30%
期中考試:30%
學期考試:40% |