離散數學

離散數學 (Discrete Mathematics)

修課說明

離散數學主要是將計算機科學上所探討到相關數學課題，集合成一門學門，它所涵蓋的內容相當廣，但各個部分之關聯性不大，若有一、二個地方不太熟悉，亦不會影響其他部分的學習。本科目可說是各校資訊相關科系研究所必考之學科。

將離散數學學好對計算機科學的相關科目的理論探討將有極大的助益，例如代數及有限狀態機對於邏輯設計有著蠻大的幫助，生成函數對於演算法時間複雜度的討論亦有相當程度的助益。後續用到離散數學的課程包括資料結構、演算法、編譯器、形式語言、電腦網路、作業系統、計算機結構、資料庫系統、密碼學、圖形理論等，可以說幾乎每一門資訊工程相關課程都用得著它。

課程目標

學生修完本課程後應具備創造性的邏輯思考能力，並達成以下的能力指標：

	能檢查簡單邏輯參數的真假值。
	能檢查簡單演算法之正確性。
	能建構簡單之有效邏輯參數。
	建構簡單之演算法。
	能描述不同形式的離散結構之定義與性質。
	能使用標準的符號正確的讀、寫、及分析不同形式的結構。

教科書

Discrete Mathematics and Its Application（第五版）

by Kenneth H. Rosen McGraw Hill 2003 ISBN:0071233741 (歐亞書局代理)

教學大綱

本課程內容大致可以分為四大部分(基礎數學、圖形理論、代數系統、組合數學)，其中與資訊工程密切相關的有三個主要部分(基礎數學、圖形理論、代數系統)，如下表所示：

	重點	主題
基礎數學	集合、布林代數與邏輯	集合論
		布林函數之基本性質及各種表示法
		應用邏輯閘製作組合電路
		利用 Karnaugh Map及 Quine-McCluskey Table化簡布林函數
		邏輯推演之基本性質
		判斷簡單陳述及複合陳述之真偽
		First Order Logic
	二元關係	二元關係之基本性質及各種表示法
		研判各種特殊關係：Reflexive, Symmetric, Transitive, Irreflexive(Antireflexive), Asymmetric, Antisymmertic, Partial Ordering, Total Ordering, Compatabe, Equivalent等等
		利用Washall's Algorithm求遞移包
		證明等價關係，求出相對應之等價類與商
		分割及分割之運算
	偏序集、絡	偏序集之基本性質及各種表示法
	偏序集、絡	絡及絡之應用
	函數	研判或證明各種特殊函數：一對一，映成，一對一且映成
		鴿籠原理之應用
		證明集合為無限可數或不可數
圖形理論	圖形理論	圖形之基本性質及各種表示法
		研判各種特殊圖及其應用：Complete, Cube, Regular, Wheel, Cycle, Bipartite,Planar Complemented, Hamiltonian, Euler等
		圖形之同構及同胚
		找出圖形之漢明頓路徑，漢明頓迴路，尤拉路徑，尤拉迴路，最短路徑，最大流量，最少色數等等
		尤拉公式
	樹	樹之基本性質及各種表示法
		樹之各種應用
		利用Kruskall's及Prim's Algorithm找出圖形之最小生成樹
		配對問題
代數系統	代數系統	研判及證明各種代數系統：Groupoid, Semigroup, Monoid, Group, Abelian Group等
		代數系統之同構及同態
		Coset, Normal subgroup, Kernel, Quotient structure之探討
	環	研判及證明各種代數系統：Ring, Intergal domain, Filed, Ideal等等
		環在傳統算數之應用：Division algorithm, Prime factorization, congruences, Euclidean algorithm, Chinese remainder theorem, Euler function, and Fermat little theorem等等.
		Polynomial ring及Gloid's filed之探討
	有限狀態機	有限狀態機之基本性質及各種表示法
		有限狀態機之化簡
		有限狀態機之同構、同態、等價及模擬
		有限狀態機之連接及分解
		Turing Machine
	編碼理論	編碼之探討
	編碼理論	解碼之探討
	玻理雅定理	Polya's Theory在著色問題上之應用

配合教科書的章節，本課程可略分為以下24個模組，每個模組講述時間約需要1~3節課。由於時間關係，部分屬於離散數學的內容，我們可能將無法在本課程中涵蓋(如紫色部分)：

	模組	對應章節	授課時數	備註
0	課程簡介		1	期中考試範圍
1	Logic	(§1.1-4)	3~4
2	Proof methods	(§1.5)	1
3	Set theory	(§1.6-7)	2~3
4	Functions	(§1.8)	2~3
5	Algorithms	(§2.1)	1
6	Orders of Growth	(§2.2)	1
7	Complexity	(§2.3)	1
8	Number theory	(§2.4-5)	3
9	Number theory apps.	(§2.6)	3
10	Matrices	(§2.7)	1
11	Proof strategy	(§3.1)	1~2
12	Sequences	(§3.2)	1~2
13	Summations	(§3.2)	1
14	Countability	(§3.2)	1~2
15	Inductive Proofs	(§3.3)	1~2
16	Recursion	(§3.4-5)	2
17	Program verification	(§3.6)	1
18	Combinatorics	(ch. 4)	3~4	期末考包含此部分再加上期中考範圍
19	Probability	(ch. 5)	?
20	Recurrences	(§6.1-3)	2
21	Relations	(ch. 7)	2
22	Graph Theory	(chs. 8+9)	5
23	Boolean Algebra	(ch. 10)	?
24	Computing Theory	(ch.11)	5

	Probability (ch. 5) 你將在機率論(或機率與統計)課程中學習
	Boolean circuits (ch. 10) 你將在數位邏輯課程中學習
	Linear algebra 你將在線性代數課程中學習
	Abstract algebra 內容有Groups, rings, fields, etc.有興趣可至應數系選修

參考書目

書名	作者	出版社	年代	條碼號	備註
Mathematical structure for computer science	Judith L. Gersting	W.H.Freeman and Company	2003	0716743582	全華科技圖書代理
Discrete Mathematics with proof	Eric Gossett	Prentice Hall	2003	0130669482	高立圖書公司代理
Discrete mathematics with combinatorics	James A. Anderson	Prentice Hall	2004	0130457914	開發圖書公司代理
Discrete and Combinatorial Mathematics - An Applied Introduction	Ralph P. Grimaldi	Addison Wesley	1999	0201304244	新月圖書公司代理
Discrete mathematics for computer scientists	J.K. Truss	Addison Wesley	1991	021175649	新月圖書公司代理
Logic and discrete mathematics-A computer science perspective	Winfried K. Grassmann and Jean-Paul Tremblay	Prentice Hall	1996	0132090082	全華科技圖書代理

評分標準

	期中考 30% (Tentative Date: November 24, 2004)
	期末考 30% (Tentative Date: January 19, 2005)
	作業及平時考核 40%

晤談時間

時間

週二下午 3:00 ～ 5:00

週三上午 8:00 ～ 10:00

地點

資工館二樓(A20-209)