離散數學

作品

書籍

課程

程式集

小說集

論文集

散文集

影片集

編輯雜誌

程式人

電子書

JavaScript

計算語言學

微積分

Blender 動畫

C# 語言

系統程式

高等 C 語言

Java

Android

Verilog

Wikidot

R 統計軟體

機率統計

計算機數學

組合語言

人工智慧

開放原始碼

網路資源運用

計算機結構

相關訊息

常用工具

友站連結

在家教育

RSS

最新修改

網頁列表

簡體版

English

教科書

課程大綱

離散數學乃是電腦的數學基礎,主要探討的對象是『資料』與『程式』,主要內容如下。

  1. 背景知識, [[Background.ppt]], 基本的數學與符號。
  2. 為何學數學, [[Math.ppt]], 數學理論與用途。
  3. 離散數學簡介, [[Introduction.ppt]], 介紹離散數學的主題 - 邏輯推論、演算法與圖形理論。
  4. 邏輯簡介, [[LogicIntroduction.ppt]], 邏輯的基礎、布林邏輯與真值表。
  5. 邏輯式的相等, [[LogicalEquivalence.ppt]], 不同的邏輯式可能是相等的。
  6. 邏輯推論, [[LogicalReasoning.ppt]], 布林邏輯的推論方式。
  7. 一階邏輯, [[FirstOrderLogic.ppt]], 一階邏輯的推論方式。
  8. 布林代數, [[BooleanAlgebra.ppt]], 以代數的角度來看布林邏輯。
  9. 演算法, , 演算法是資訊科學的核心研究領域,是程式設計的抽象化表達方法。
  10. 計算理論, , 計算理論包含Grammar、Turing Machine、Computability與 NP-Complete 等議題。
  11. 圖形理論, , 圖形理論在管理領域、排程與作業研究上有大量的應用,並且是資料結構的核心。
  12. 樹狀結構, , 樹狀結構是最常用到的資料結構,用在排序、搜尋與文法剖析上。
  13. 整數理論, , 整數論被大量應用在密碼學上。
  14. 代數結構, , 代數結構包含群、體、環等結構,探討封閉性、結合性、單位元素、反元素等特性。
  15. 排列組合, , 排列組合是機率理論的基礎。
  16. 機率理論, , 機率理論是統計學的基礎。

資料導向分類法

以資料為導向的主題、可分為『邏輯資料』、『數字資料』、『字串資料』等三類。

  1. 數字, 整數論 (Number Theory)、代數結構 (Algebra)、排列組合 (Combinations)、機率理論 (Probability)
  2. 符號, 集合論 (Set Theory)、關係 (Relation)、圖形理論 (Graph Theory)、樹狀結構 (Trees)
  3. 邏輯(0與1), 布林邏輯 (Boolean Logic)、洪氏邏輯 (Horn Logic)、一階邏輯 (First-Order Logic)

程式導向分類法

以程式為導向的主題、可分為『迴圈式』、『遞迴式』、『推理式』等三類。

  1. 迴圈式, 演算法 (Algorithm)
  2. 遞迴式, 遞歸函數 (Recursive Function)
  3. 推理式, 邏輯推論 (Reasoning)

線上資源

  1. MIT OCW 6-042 : http://www.twocw.net/mit/Electrical-Engineering-and-Computer-Science/6-042JMathematics-for-Computer-ScienceFall2002/Calendar/index.htm
  2. CSIS1118A Homepage: Lecture Notes - http://i.cs.hku.hk/~c1118a/lecture_notes.php

補充

Polya 定理

Polya theorem

Generating Function (Euler)
Theorem : Σ( 1/i^2 ) = Pi^2/6
Proof :
sin(x) = x/1! - x^3/3! + x^5/5! - x^7/7! +… — by Taylor's expension formula
because sin(x) = 0 has the following infinite root
0, Pi, -Pi, 2Pi, -2Pi, 3Pi, -3Pi, …. then
sin(x)/x = 1 - x^2/3! + x^4/5! … — with root Pi, -Pi, 2Pi, -2Pi,…
= (1-x^2/Pi^2)(1-x^2/4Pi^2)(1-x^2/9Pi^2)…
1/3! = 1/Pi^2 + 1/4Pi^2 + 1/9Pi^2 …
so 1+1/4+1/9+… = Pi^2/6

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License