離散數學

📚 內容概要

一門針對數學與電腦科學專業學生的離散數學入門課程。內容涵蓋邏輯、集合、證明技巧、演算法、數論、組合數學、圖論及自動機等基礎主題。本課程強調數學推理與解決問題的能力，為電腦科學的進階學習奠定必要基礎。

掌握構成電腦科學基石的邏輯與結構。

作者： Richard Johnsonbaugh

致謝： 审稿人包括 Venkata Dinavahi、Matthew Elsey、Christophe Giraud-Carrier、Yevgeniy Kovchegov、Filix Maisch、Tyler McMillen、Christopher Storm、Donald Vestal 及 Guanghua Zhao。Pearson 團隊的支持人員：Deirdre Lynch、Jeff Weidenaar、Lauren Morse 等。

🎯 學習目標

1. 進行集合運算，包括差集與補集，並利用文氏圖與定理 1.1.22 驗證集合恆等式。
2. 建構並評估包含否定、析取與條件語句的命題之真值表。
3. 應用推論規則與歸納推理，判斷邏輯論證的有效性。
4. 定義並應用數學系統的各項元件，包括公設、定義與定理。
5. 為代數與集合論命題建構直接證明、反證法與分類討論證明。
6. 使用數學歸納法原理與強歸納法，證明恆等式、可整除性性質與演算法正確性。
7. 定義並分類函數（單射、滿射、雙射），並執行合成與反函數等運算。
8. 應用序列符號、字串接合與遞迴規則，以模擬離散資料集。
9. 利用有向圖與矩陣表示法，分析二元關係的自反性、對稱性與傳遞性等性質。
10. 定義一個演算法，並驗證其七項核心特性（輸入、輸出、明確性、決定性、有限性、正確性與普遍性）。

🔹 第一課：邏輯與集合論基礎

概述： 本課建立離散數學的基本架構，聚焦於集合的嚴謹操作與邏輯的形式結構。學生將從集合運算與恆等式，進展至邏輯論證的建構、條件命題的評估，以及嵌套量詞的分析。這些概念為演算法設計、資料庫理論與電腦科學與工程中的形式化驗證提供了基本框架。

學習成果：

• 進行集合運算，包括差集與補集，並利用文氏圖與定理 1.1.22 驗證集合恆等式。
• 建構並評估包含否定、析取與條件語句的命題之真值表。
• 應用推論規則與歸納推理，判斷邏輯論證的有效性。

🔹 第二課：數學證明技巧

概述： 本課介紹用以確立數學陳述有效性之正式方法，以及電腦科學與數學中所需的邏輯嚴謹性。學生將從基礎數學系統與直接證明，進展至高階技術，如歸結證明、數學歸納法（含強歸納法），以及在演算法驗證中應用迴圈不變式。

學習成果：

• 定義並應用數學系統的各項元件，包括公設、定義與定理。
• 為代數與集合論命題建構直接證明、反證法與分類討論證明。
• 使用數學歸納法原理與強歸納法，證明恆等式、可整除性性質與演算法正確性。

🔹 第三課：函數、序列與關係

概述： 本課探討電腦科學中用以模擬資料與流程的基礎數學結構。內容從函數的定義及其各種類型（單射、滿射、雙射），延伸至序列、字串與二元關係的正式性質。學生將探索實務應用，例如雜湊函數、國際標準書號檢查數位、透過偏序進行任務排程，以及利用矩陣與資料庫表示關係。

學習成果：

• 定義並分類函數（單射、滿射、雙射），並執行合成與反函數等運算。
• 應用序列符號、字串接合與遞迴規則，以模擬離散資料集。
• 利用有向圖與矩陣表示法，分析二元關係的自反性、對稱性與傳遞性等性質。

🔹 第四課：演算法分析與複雜度

概述： 本課探討演算法的基本定義與特性，其在搜尋與排序（特別是文字搜尋與插入排序）中的實現，以及用以分析效率的嚴謹數學框架。學生將深入研究漸近符號、函數增長率，以及遞迴解題的機制，包括分治策略如棋盤鋪磚與費波那契數列。

學習成果：

• 定義一個演算法，並驗證其七項核心特性（輸入、輸出、明確性、決定性、有限性、正確性與普遍性）。
• 應用大 O、歐米伽與希塔符號，表達演算法的時間與空間複雜度。
• 使用重複半分法與多項式排序等技術，分析最佳、最壞與平均情況。

🔹 第五課：數論與密碼學導論

概述： 本課探討數論的基礎原則，從除數與質數的基本性質，到支撐現代安全通訊的複雜演算法。學生將掌握最大公因數（GCD）、進位轉換與模指數運算的數學機制，以理解並實作 RSA 公開金鑰加密系統。

學習成果：

• 定義並應用可整除性、質性與算術基本定理的概念。
• 有效執行十進位、二進位與十六進位之間的轉換。
• 執行歐幾里得演算法及其擴展形式，以求得最大公因數與線性組合（sa + tb）。

🔹 第六課：計數方法與離散機率

概述： 本課探討計數有限結構的基本技巧，並應用於離散機率。學生將從基本的加法與乘法原理，進展至高階概念如卡塔蘭數、史特林數與二項式定理。課程最後以鴿巢原理及其各種形式結束，提供一個嚴謹的框架，用以證明離散系統中特定配置的存在性。

學習成果：

• 應用加法、乘法與包含-排除原理，解決複雜的計數問題。
• 辨別並計算排列與組合，包含相同物件與重複的情況。
• 使用字典序的生成演算法，計算排列與組合。

🔹 第七課：遞迴關係

概述： 本課探討遞迴關係在數學與電腦科學中的理論與應用。學生將學習使用迭代法與特徵方程式，求解齊次與非齊次形式的遞迴關係。此外，本課展示遞迴關係如何成為分析選擇排序、二分搜尋與合併排序等遞迴演算法時間複雜度的重要工具。

學習成果：

• 使用迭代法與特徵方程式（針對相異與相等根）求解遞迴關係。
• 建模並解決經典數學問題，包括漢諾塔、費波那契數列（黃金比例）與錯位排列。
• 使用遞迴關係分析遞迴演算法的最壞情況時間複雜度。

🔹 第八課：圖論與最短路徑演算法

概述： 本課探討圖論的基礎原則，從簡單圖與加權圖的基本定義，延伸至複雜的最短路徑與環識別演算法解法。學生將檢視平面性、連通性與同構等結構性質，並應用這些概念於經典問題，如柯尼斯堡橋問題、旅行推銷員問題（TSP）與即時瘋狂拼圖。

學習成果：

• 定義並區分不同類型的圖，包括簡單圖、加權圖、完全圖、二分圖與 n-立方體。
• 分析圖的連通性，以辨識歐拉環、哈密頓環，並使用迪克斯特拉演算法找出最短路徑。
• 應用矩陣表示法（鄰接矩陣與關聯矩陣）與圖不變量，驗證同構與平面性。

🔹 第九課：樹與搜尋演算法

概述： 本課探討樹在電腦科學與數學中的基本性質、特徵與應用。學生將探索根樹與二元樹、廣度優先與深度優先搜尋的生成樹演算法、用於最小生成樹的普里姆演算法等優化技術，以及回溯法、淘汰賽排序與使用極小化極大程序的遊戲樹等決策框架。

學習成果：

• 定義並辨識根樹，及其層級、高度與現實世界系統中的階層結構。
• 根據連通性、無環性與邊數與頂點數的比例來特徵化樹。
• 實作並追蹤生成樹（BFS、DFS）、最小生成樹（普里姆演算法）與二元搜尋樹建構的演算法。

🔹 第十課：網路模型與流量最佳化

概述： 本課探討運輸網路的數學建模，專注於資源（流量）如何透過有向圖從源點流向匯點。內容詳述流量守恆規則、最大化吞吐量的演算法步驟、網路切割與流量容量的關係，並應用這些原理解決二分圖中的匹配問題。

學習成果：

• 定義並驗證運輸網路與合法流量分配的特性。
• 執行最大流量演算法（演算法 10.2.4），以找到最佳吞吐量。
• 應用最大流-最小割定理，透過網路分割證明流量的最優性。

🔹 第十一課：布林代數與邏輯電路

概述： 本課探討數位邏輯的數學基礎，著重於布林代數如何提供一種形式語言，用以設計與簡化組合電路。學生將學習在邏輯閘、切換電路與布林表達式之間轉譯，最終應用這些工具合成複雜函數，並建構加法器與二補數邏輯等基本運算元件。

學習成果：

• 使用標準邏輯閘（AND、OR、NOT）與切換配置，設計與分析組合電路。
• 應用布林代數律與對偶定理，證明電路等價性並簡化表達式。
• 從真值表合成布林函數為「析取範式」（DNF）與「合取範式」（CNF）。

🔹 第十二課：自動機、語法與形式語言

概述： 本課探討計算的數學基礎，從具備內部記憶（以單位時間延遲為模型）的順序電路與有限狀態機開始。內容涵蓋短語結構語法（類型 1、2 與 3）的正式定義與分類、巴科斯正規式（BNF）的應用，以及用於分形產生的林登邁爾語法的特殊用途。最後，建立確定性與非確定性有限狀態自動機之間的關鍵關係，以及它們所接受的形式語言。

學習成果：

• 使用轉移圖與狀態函數，分析與設計有限狀態機（FSM）與自動機（FSA/NFA）。
• 在喬姆斯基層級中分類語法，並使用產生規則與 BNF 符號衍生字串。
• 使用林登邁爾語法與同時取代規則，模擬自相似結構，如馮·寇赫雪片。