web.math.isu.edu.tw/yeh/2009fall/TIAM/Lectures/week7/sunifan.ppt
以代數、拓樸方法建立組合學體系的研究; 以群論、有限幾何為主要工具的設計 ... 簽帳卡等也是密碼學的附產品；另外，DNA的定序問題，選舉權力的分析，生物食物網 ...
研究領域．離散數學與最優化
快速連結
一、「離散數學」簡介
- 「離散數學」是什麼？
「離散數學」亦稱「組合數學」。自遠古數學活動肇始之初，算術與幾何便分別代表了離散與連續觀念的源頭。兩種思維方式相互的辯證發展，造就了內容繽紛的數學世界。但自牛頓開創微積分以後，以分析為首的連續性數學獨領風騷近三百年之久。今日所謂離散數學的若干題材，雖然可在數論、代數、機率、初等幾何等學科中，發現其萌芽之跡，但終未能成氣候。甚至有局限於益智遊戲形式，是理論深度未被辨識的研究課題。
本世紀以來，離散的工具與方法，逐漸在廣泛的學科中，被發展及使用起來。因此慢慢產生出新的焦點，以及新的科學意識。一些彼此關連掛鉤的研究領域，開始匯聚在離散數學(或稱組合數學)這張大傘之下。特別自三十年代以後，計算科學在理論與實用上都有突破性的發展。電子計算機這種能力巨大的資訊處裡工具，把人類文明帶入一個嶄新的階段。它不僅提供了生活的方便，更深深影響人的思惟方式與知識發展的進步。計算機必須通過離散的表徵才能處裡資訊，古典連續數學經由它的離散化，反而產生了深刻的離散問題，同時彰顯了離散現象的重要性。此外，計算機幫助人處理極大量的有限數及有限結構，踏入前人無法想像的天地，更開展了新意義、新層次的問題以供研究。 - 「組合數學」這個領域包含了什麼？
組合數學這個名詞只是一個通稱，其中包羅了許多學域，比較居樞紐地位的包括下列幾種：
- 由古典計算問題一脈相傳而下，包括有限集合族上的各類組合問題；
- 以代數、拓樸方法建立組合學體系的研究；
- 以群論、有限幾何為主要工具的設計理論(Design Theory)；
- 群作用所產生的組合現象；
- 圖形、網路與超圖的理論(Hypergraphs)；
- 最佳化、運籌學(Operation Research)與賽局理論(Game Theory)；
- 編碼(Coding Theory)與密碼理論(Cryptography)；
- 擬陣(Matroid)、廣義擬陣論(Greedoid)；
- 離散與計算幾何學；
- 演算法則的設計與分析；
- 離散機率方法的應用；
- 利用微積分、複變方法進行演算分析；
- 特徵值估計及其應用。
Top
- 「組合數學」這個領域有些什麼應用？
在應用方面，最大的市場之一是計算機科學，已成為該領域的必修課程。所有數位化的產物，如雷射唱盤、光碟、大哥大、衛星通訊等等都仰賴錯誤糾正碼(Error Correcting Code)的設計以增加它們的可靠性；提款卡、簽帳卡等也是密碼學的附產品；少了這些，人類的生活都不知道要如何繼續下去!另外，DNA的定序問題，選舉權力的分析，生物食物網的平衡，實驗設計的安排，處處可見組合數學應用的例子。由此可預見，非數學科系對組合數學的需求將日漸增高，甚至已經有人呼籲，以「組合數學」取代微積分，作為大一的基礎數學課程。 - 本系與「組合數學領域」之關連？
本系在組合數學方面的師資充實，其人數之多，在台灣各大學數學系所稱冠，研究領域亦涵蓋各主要方向。分述如下：
- 傅恆霖教授：圖論、組合設計
- 陳秋媛教授：演算法、圖論、離散數學
- 翁志文教授：代數組合學、矩陣理論
- 符麥克教授：賦距數論(Metric Number Theory)、演算分析
二、老師的研究興趣
傅恆霖 老師 http://hlfu.math.nctu.edu.tw/profile_content.php?N_ID=5
在組合數學方面的研究目前的研究工作有下列幾項：- 在圖論方面主要的內容為圖的分割、圖的覆蓋以及圖的著色。
- 在組合設計方面主要是應用圖設計於網路設計與生物計算中的群試理論。
- 在代數圖論方面則致力於探討二分圖的最大及次大的特徵值。
陳秋媛 老師 http://www.math.nctu.edu.tw/~cychen/
我主要研究的興趣在於「圖論」及「演算法」。在「圖論」方面，主要著眼於problems related to triangulations, planar graphs, perfect graphs, hamiltonian cycles, and graph embedding。在「演算法」方面，主要著眼於problems related to double-loop networks, triple-loop networks, and interconnection networks。Top
翁志文 老師 "http://www.math.nctu.edu.tw/~weng/weng.htm
我的研究環繞距離正則圖為中心。早期以尋找距離正則圖的「弱測地封閉性子圖」(weak-geodetically closed subgraphs; strongly closed subgraphs) 為目標，之後探討一類有許多弱測地封閉性子圖的距離正則圖，稱之為 「D-封閉距離正則圖」(D-bounded distance-regular graphs)，然後對「負型古典距離正則圖」(classical distance-regular graphs of negative type) 進行分類探討。距離正則圖的研究包含組合方法、代數方法、矩陣方法，因此我也從事「設計編碼」、「結合代數」、「組合矩陣論」相關的研究。如我曾參與「群試設計」(group testing)、「量子群」 (quantum groups)、「矩陣群」 (matrix group) 等研究。最近我較關心「組合矩陣論」，與李光祥合作推廣「值譜剩餘定理」 (Spectral Excess Theorem)，「奇圍長定理」 (Odd Girth Theorem) 到非正則圖上。另一方面，我對距離正則圖或一般圖的「特徵值」 (eigenvalues) 之具組合意義的上下界及達到此界的圖刻畫也感興趣。Top
符麥克 老師 http://jupiter.math.nctu.edu.tw/~mfuchs/
我的研究興趣是解析組合以及其在演算分析和生物數學上的應用。 解析組合這一數學分支使用複變函數分析以及漸進分析等工具研究 組合問題，它的精神和解析數論是共通的。我最近幾年的工作主要集中於研究由資訊科學和生物數學所衍生出 來的各種隨機樹。更仔細的說，我在研究於不同機率模型下的各種 隨機樹的「形狀」。和我的研究夥伴一起，我們探討了隨機樹狀結 構的種種參數，例如邊緣子樹的數量，特定模式的發生，結點深度 和結點路徑總長，結點總數等等。這些形狀參數都和相關演算法的 複雜度分析有著密切的關連。
目前我的研究主題之一是數位樹（digital tree）的機率分法分析。 數位樹是資訊科學中最基本的資料結構之一。
Top
三、相關選修課程
本系歷年開授之組合數學課程包括下列各科目，其中研究所課程以兩年開一次為原則，目的是在讓碩士班同學，於兩年就學期間有機會修到較多的課程：- 離散數學(一)(大學部必修)，
- 編碼理論(研究所及大學部)，
- 組合編碼(研究所)，
- 密碼學(研究所及大學部)，
- 離散數學專題(研究所必修)，
- 圖論(研究所必修)，
- 組合學導論(研究所必修)，
- 設計理論(研究所)，
- 代數組合學(研究所)，
- 代數圖論(研究所)，
- 機率圖論(研究所)，
- 演算法(研究所及大學部)，
- 圖論演算法(研究所及大學部)，
- 演算分析(研究所)，
- 組合最優化(研究所及大學部)，
- 連接網路(研究所)，
- 群試理論(研究所)，
- 最優分割(研究所)。
本校各系所亦開設極多組合數學相關課程，舉例如下：
- 離散數學(電控系大學部，資工系大學部、資科系大學部)
- 組合數學(資科系大學部)
- 作業研究(經管所、管科系大學部、運管系大學部、工工系大學部)
- 線性規劃(資工系大學部)
- 圖論(資工系研究所、資科系研究所、資科系大學部)
- 連結網路(資工系研究所、資科系研究所)
- 密碼方法(資工系研究所、資科系研究所)
- 密碼學與理論簡介(資工系研究所、資科系研究所)
- 高等密碼學(資科系研究所)
- 通道編碼(電工系研究、電工系大學部)
- 編碼理論(電信系研究所、電信系大學部)
- 消息理論(電信系研究所)
- 演算法(資工系大學部、資工系研究所、資科系研究所)
- 演算法概論(資工系大學部)
- 演算法與架構(資工系研究所、資工系大學部)
- 分散式演算法(資工系研究所、資科系研究所)
- 基因演算法(資科系研究所)
No comments:
Post a Comment