課程名稱 |
組合學一 Combinatorics (Ⅰ) |
開課學期 |
104-1 |
授課對象 |
理學院 數學研究所 |
授課教師 |
張鎮華 |
課號 |
MATH7701 |
課程識別碼 |
221 U3290 |
班次 |
|
學分 |
3 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期三6(13:20~14:10)星期五3,4(10:20~12:10) |
上課地點 |
天數305天數305 |
備註 |
總人數上限:40人 |
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1041MATH7701_comb_I |
課程簡介影片 |
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
This course contains two parts, one on counting theory and the other on design theory. For the part of counting theory, we will cover pigeonhole principle, permutation, generating function, inclusion-exclusion principle, Polya counting, and some advanced topics. For the part of design theory, we will cover PBD design, finite geometry, Hadamard matrices, orthogonal Latin squares, as well as the applications of design theory. |
課程目標 |
Combinatorics is concerned with arrangements of the objects of a set into patterns satisfying specified rules. Two general types of problems occur repeatedly: existence of arrangement, enumeration or classification of the arrangements. The goal of this course is to introduce counting theory and design theory. |
課程要求 |
*Grading scheme:
作業、期中考、期末考各占三分之一成績。
|
預期每週課後學習時數 |
|
Office Hours |
每週五 14:10~17:00 備註: 也可以另約時間 |
指定閱讀 |
待補 |
參考書目 |
R.A. Brualdi, Introductory Combinatorics, Third Edition, Prentice Hall, Upper
saddle River, 1999.
L. Lovasz, Combinatorial Problems and Exercises, North-Holland Pub. Comp.,
Amsterdam, 1979.
R.P. Stanley, Enumerative Combinatorics, Volume I, Wadsworth & Brooks,
Monterey, CA, 1986.
J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Second Edition,
Cambridge 2002.
沈灝,組合設計理論,第二版,上海角通大學出版社,2008。 |
評量方式 (僅供參考) |
|
週次 |
日期 |
單元主題 |
第0週 |
|
主要以 "P. J. Cameron, Combinatorics Topics,
Techniques, Algorithm, Cambridge University
Press, 1994" 為主,必要時另加材料。 |
第1週 |
9/16,9/18 |
Counting |
第2週 |
9/23,9/25 |
Subsets, partitions, permutations |
第3週 |
9/30,10/02 |
Recurrence reations and generating functions |
第4週 |
10/07,10/09 |
Recurrence reations and generating functions
The principle of inclusion and exclusion |
第5週 |
10/14,10/16 |
The principle of inclusion and exclusion
|
第6週 |
10/21,10/23 |
Latin squares and SDRs |
第7週 |
10/28,10/30 |
Extremal set theory |
第8週 |
10/04,10/06 |
Steiner triple systems |
第9週 |
11/11,11/13 |
Finite geometry
11/13 晚上 6 點期中考,時間不限,範圍到第 8 章。
|
第10週 |
11/18,11/20 |
Ramsey's theorem |
第11週 |
11/25,11/27 |
本系自主學習週 |
第12週 |
12/02,12/04 |
Posets, latices and matroids |
第13週 |
12/09,12/11 |
More on partitions and permutations |
第14週 |
12/16,12/18 |
Automorphsim groups and permutation groups |
第15週 |
12/23,12/25 |
Enumeration under group action |
第16週 |
12/30,1/1 |
Designs |
第17週 |
1/06,1/08 |
Error-correcting codes |
第18週 |
1/15 |
期末考 1/15 (Fri) 10:00 ~ *** (Chapters 9, 10, 12, 13) |
|