Type of Credit: Required
Credit(s)
離散數學是學習數學的基礎課程，將生活中的事物利用邏輯思考程序描述出來，是一門「看的到」的學問。主要研究的對象為整數，使用數學方法進行有系統的計數。
首先，我們學會使用數學語言，包含數學符號、邏輯敘述和簡單的推導證明。為了讓證明描述更明確，課本會介紹一 些基本數學名詞，函數、集合、數列的定義與相關概念。有了基礎概念後， 我們便可將較困難的問題化簡。
其次，我們會先學一些基本的計數方法來做排列組合，然後介紹一些進階的技巧，將日常生活實例用遞迴方式敘述出來，並解出答案。另外，我們還會利用生成函數和排容原理來幫助我們解決更深入的問題。
離散數學對於學習資訊科學有相當大的幫助，程式設計需要很多邏輯推 導程序以及主程式呼叫子程式的遞迴關係。網路間的連線方式、貨物運送的 路徑設計和航空路線會用圖論的方法來達成最大效益。最近在研究的生物科 技也需要圖論方面的人才來推測基因相連的關係。
能力項目說明
學習離散數學，學會使用數學語言，包含數學符號、邏輯敘述和簡單的推導證明，做為修習進一步學科的基礎。
| 週次 | 主題 | 內容 | 活動與作業 | 課堂講授 | 課程前後 |
|
1 |
集合與邏輯 |
Sets, Propositions, Conditional Propositions |
探討集合以及邏輯的概念，並使學生了解集合與邏輯的應用及其重要性。 |
3.0 |
6.0 |
|
2 |
命題與量詞 |
Conditional Propositions, Logical Equivalence, Arguments |
深入介紹命題與量詞，奠定日後研 習離散數學領域之基礎。 |
3.0 |
6.0 |
|
3 |
證明的方法以及種類 |
Quantifiers, Nested Quantifiers, Proofs |
說明證明的方法分為直接證明法和反證法，而種類分為: 演繹證明、歸 納證明、類比證明，清楚分別各方 法的差異性以及運用時間。 |
3.0 |
6.0 |
|
4 |
歸結原理、數學歸納法 |
Mathematical Systems, Proofs, Counterexamples |
延續上一周的課程，更詳細的介紹 證明方法中的歸結原理和學歸納法，作為證明理論的入門和基本功。 |
3.0 |
6.0 |
|
5 |
函數、數列 |
Functions, Sequences |
演示函數定義及功能。 |
0.0 |
0.0 |
|
6 |
函數、數列 |
Functions, Sequences |
除了演示函數定義及功能外，彈性進行小考來檢測學生學習狀況。 |
3.0 |
6.0 |
|
7 |
等價關係、關係矩陣型證明的方法以及種類 |
Relations, Equivalence Relations |
更深入的了解關係的定義以及其在 應用上功用，且在課後做隨堂測驗 來以簡單矩陣快速檢視同學之學習狀況。 |
3.0 |
6.0 |
|
8 |
演算法簡介及實例 |
Algorithms, Examples of Algorithms |
初步介紹演算法的歷史，並探討如何了解在電腦中該如何轉換及計算，以及介紹演算法的架構，從輸入，最後輸出結果。 |
3.0 |
6.0 |
|
9 |
期中考試 |
1-8週內容 |
1-8週內容 |
3.0 |
6.0 |
|
10 |
計算的複雜度
|
Analysis of Algorithms |
學習比較演算法的效率 |
3.0 |
6.0 |
|
11 |
遞迴演算法初探 |
Analysis of Algorithms |
介紹何謂遞迴演算法，並以數學中的階乘的概念加以說明，並教導學 生如何計算及其概念與應用，且在課後進行以robot walking algorithm作結。 |
3.0 |
6.0 |
|
12 |
質數判別法 |
Divisors, Representations of Integers |
介紹簡單質數之概念，以及教導同學如何用定理敘述證明輔以習題演示應用，並以演算法的形式讓同學 更深入了解。 |
3.0 |
6.0 |
|
13 |
同餘定理 |
Divisors, Representations of Integers |
從頭簡述同餘的符號、性質和與除法原理之相關性並提出同餘關係式的重要性，且在課後進行隨堂測驗檢視學生學習狀況。 |
3.0 |
6.0 |
|
14 |
歐幾里德演算法 |
The Euclidean Algorithm |
結合上一個章節演算法之所學將數論中著名的歐幾里得演算法，以較 佳的效率求得最大公因數並嘗試以紙筆計算與電腦結果互相驗證，增 進學生計算能力。 |
3.0 |
6.0 |
|
15 |
數位系統及二維碼 |
RSA |
利用例題導入二維瑪的計算方法，進而介紹數位系統在機器運算的意 涵，使學生更能了解各個位數轉換之用處。且在課後進行小考以檢視學生之學習狀況。 |
3.0 |
6.0 |
|
16 |
密碼系統及數論 |
RSA |
了解數論之意涵並學習如何證明算術基本定理，以檢視同學直至目前之證明能力。 |
3.0 |
6.0 |
|
17 |
期末考試 |
10-16週內容 |
10-16週內容 |
3.0 |
6.0 |
|
18 |
期末考試檢討 |
1-17週內容 |
1-17週內容 |
3.0 |
9.0 |
Textbook:
Discrete Mathematics and Its Applications
Seventh Edition
by Kenneth H. Rosen
References: