研究領域．離散數學與最優化
快速連結
一、「離散數學」簡介
- 「離散數學」是什麼？
「離散數學」亦稱「組合數學」。自遠古數學活動肇始之初，算術與幾何便分別代表了離散與連續觀念的源頭。兩種思維方式相互的辯證發展，造就了內容繽紛的數學世界。但自牛頓開創微積分以後，以分析為首的連續性數學獨領風騷近三百年之久。今日所謂離散數學的若干題材，雖然可在數論、代數、機率、初等幾何等學科中，發現其萌芽之跡，但終未能成氣候。甚至有局限於益智遊戲形式，是理論深度未被辨識的研究課題。
本世紀以來，離散的工具與方法，逐漸在廣泛的學科中，被發展及使用起來。因此慢慢產生出新的焦點，以及新的科學意識。一些彼此關連掛鉤的研究領域，開始匯聚在離散數學(或稱組合數學)這張大傘之下。特別自三十年代以後，計算科學在理論與實用上都有突破性的發展。電子計算機這種能力巨大的資訊處裡工具，把人類文明帶入一個嶄新的階段。它不僅提供了生活的方便，更深深影響人的思惟方式與知識發展的進步。計算機必須通過離散的表徵才能處裡資訊，古典連續數學經由它的離散化，反而產生了深刻的離散問題，同時彰顯了離散現象的重要性。此外，計算機幫助人處理極大量的有限數及有限結構，踏入前人無法想像的天地，更開展了新意義、新層次的問題以供研究。
- 「組合數學」這個領域包含了什麼？
組合數學這個名詞只是一個通稱，其中包羅了許多學域，比較居樞紐地位的包括下列幾種：
- 由古典計算問題一脈相傳而下，包括有限集合族上的各類組合問題；
- 以代數、拓樸方法建立組合學體系的研究；
- 以群論、有限幾何為主要工具的設計理論(Design Theory)；
- 群作用所產生的組合現象；
- 圖形、網路與超圖的理論(Hypergraphs)；
- 最佳化、運籌學(Operation Research)與賽局理論(Game Theory)；
- 編碼(Coding Theory)與密碼理論(Cryptography)；
- 擬陣(Matroid)、廣義擬陣論(Greedoid)；
- 離散與計算幾何學；
- 演算法則的設計與分析；
- 離散機率方法的應用；
- 利用微積分、複變方法進行演算分析；
- 特徵值估計及其應用。
Top
- 「組合數學」這個領域有些什麼應用？
在應用方面，最大的市場之一是計算機科學，已成為該領域的必修課程。所有數位化的產物，如雷射唱盤、光碟、大哥大、衛星通訊等等都仰賴錯誤糾正碼(Error Correcting Code)的設計以增加它們的可靠性；提款卡、簽帳卡等也是密碼學的附產品；少了這些，人類的生活都不知道要如何繼續下去!另外，DNA的定序問題，選舉權力的分析，生物食物網的平衡，實驗設計的安排，處處可見組合數學應用的例子。由此可預見，非數學科系對組合數學的需求將日漸增高，甚至已經有人呼籲，以「組合數學」取代微積分，作為大一的基礎數學課程。
- 本系與「組合數學領域」之關連？
本系在組合數學方面的師資充實，其人數之多，在台灣各大學數學系所稱冠，研究領域亦涵蓋各主要方向。分述如下：
- 傅恆霖教授：圖論、組合設計
- 陳秋媛教授：演算法、圖論、離散數學
- 翁志文教授：代數組合學、矩陣理論
二、老師的研究興趣
Top陳秋媛 教授 （圖論、演算法、連接網路及無線網路）
|
近年研究計劃 (1)圖論在無線感測網路的定位及訊息傳送等問題上的應用 |
 |
 |
翁志文 教授 （距離正則圖、群試設計、代數示表與表示理論、組合矩陣理論、圖論）
|
Yu-pei Huang, Yeh-jong Pan and Chih-wen Weng, Nonexistence of a Class of Distance-Regular Graphs, the electronic journal of combinatorics, Volume 22, Issue 2 (2015), #P2.37 Jun Guo, Kaishun Wang, Chih-wen Weng, Pooling semilattices and non-adaptive pooling designs, Discrete Mathematics 320(2014), 64-72 Chia-an Liu, Chih-wen Weng, Spectral radius of bipartite graphs, Linear Algebra and its Applications, 474(2015), 30–43 Yen-Jen Cheng, Feng-lei Fan, Chih-wen Weng, An extending result on spectral radius of bipartite graphs, arXiv:1509.07586 |
 |
 |
三、相關選修課程
本系歷年開授之組合數學課程包括下列各科目，其中研究所課程以兩年開一次為原則，目的是在讓碩士班同學，於兩年就學期間有機會修到較多的課程：
- 離散數學(一)(大學部必修)，
- 編碼理論(研究所及大學部)，
- 組合編碼(研究所)，
- 密碼學(研究所及大學部)，
- 離散數學專題(研究所必修)，
- 圖論(研究所必修)，
- 組合學導論(研究所必修)，
- 設計理論(研究所)，
- 代數組合學(研究所)，
- 代數圖論(研究所)，
- 機率圖論(研究所)，
- 演算法(研究所及大學部)，
- 圖論演算法(研究所及大學部)，
- 演算分析(研究所)，
- 組合最優化(研究所及大學部)，
- 連接網路(研究所)，
- 群試理論(研究所)，
- 最優分割(研究所)。
組合數學為本系碩士班兩組之一。每年招收的碩士班學生，由早年的五名到現在增為十三名。博士班招生視情況而定，截至目前為止，畢業的博士班學生超過三十位，分別在全國各大專院校任教，極受肯定。
本校各系所亦開設極多組合數學相關課程，舉例如下：
- 離散數學(電控系大學部，資工系大學部、資科系大學部)
- 組合數學(資科系大學部)
- 作業研究(經管所、管科系大學部、運管系大學部、工工系大學部)
- 線性規劃(資工系大學部)
- 圖論(資工系研究所、資科系研究所、資科系大學部)
- 連結網路(資工系研究所、資科系研究所)
- 密碼方法(資工系研究所、資科系研究所)
- 密碼學與理論簡介(資工系研究所、資科系研究所)
- 高等密碼學(資科系研究所)
- 通道編碼(電工系研究、電工系大學部)
- 編碼理論(電信系研究所、電信系大學部)
- 消息理論(電信系研究所)
- 演算法(資工系大學部、資工系研究所、資科系研究所)
- 演算法概論(資工系大學部)
- 演算法與架構(資工系研究所、資工系大學部)
- 分散式演算法(資工系研究所、資科系研究所)
- 基因演算法(資科系研究所)