Discrete Mathematics

請修課同學於學期間務必隨時查看課程網頁,以免錯失重要訊息。
  • 2014-06-9:
    第二次期中考考卷有問題的同學,請於這星期三至星期五 (6/11 ~ 6/13) 的下午 15:30 ~ 18:00 至德田館 442-2 實驗室找助教說明問題。
  • 2014-06-5:
    下次上課 (6/12) 將不舉行小考。
  • 2014-05-28:
    第二次期中考參考解答已公佈,請想核對答案的同學先行參考。未來考卷發放時將參照第一次期中考時的模式,故建議同學先行查閱參考解答以利未來考卷發放。
  • 2014-05-22:

    本學期課程將於 6/12 結束,期末考將在 6/20 18:30 舉行,請同學們提早準備,學號單數R102,雙數R104。

  • 2014-05-19:
    5/15 小考考卷有人沒寫名字,快來認領啊!
  • 2014-05-12:
    Quiz 6, 7, 9 已批改完畢,批改原則與參考解答已公佈於課程網頁上,想知道 Quiz 6, 7, 9 成績的同學請於 5/29 日之前來 442-2 領回自己的考卷,如有疑問者請當場提出,考卷攜回或超過期限後不得要求更改分數。
  • 2014-05-01:
    第二次期中考將在 5/16 18:30 舉行,請同學們提早準備,學號單數R102,雙數R104。
  • 2014-04-23:
    因助教臨時有事,今天修改分數時間延後半小時 (16:00) 開始。
  • 2014-04-18:
    第一次期中考考卷有問題的同學,請於下星期三 (4/23) 15:30 ~ 18:00 至德田館 442-2 實驗室找助教說明問題。另外關於第 7, 8, 12題答案中n範圍沒寫的同學,老師決定不予扣分,所以也請此部分被扣分的同學於同一時間帶考卷到德田館 442-2 實驗室找助教修改分數(已交回考卷者直接過來即可)。
  • 2014-04-09:
    第一次期中考參考解答已公佈,請想核對答案的同學先行參考。
  • 2014-04-09:
    Quiz 3, 4, 5 已批改完畢,批改原則與參考解答已公佈於課程網頁上,想知道 Quiz 3, 4, 5 成績的同學請於 4/24 日之前來 442-2 領回自己的考卷,如有疑問者請當場提出,考卷攜回或超過期限後不得要求更改分數。
  • 2014-03-21:
    有同學提問期中考會考多久,經詢問老師知至少兩個小時,助教可再視情況延長時間,故不需擔心寫不完的問題。另外,若期中考因故無法參加者,請親自到教授辦公室 (德田館427) 與老師洽談。
  • 2014-03-20:
    下週 (3/27) 隨堂小考會照常舉行,請同學們記得事先準備。
  • 2014-03-13:
    請同學們下週上課 (3/20) 前先自行閱讀 "Logic" (Part 2 Algebra) P.1 ~ P.13。
  • 2014-03-06:
    Quiz 2 已批改完畢,批改原則與參考解答已公佈於課程網頁上,請想知道 Quiz 2 成績的同學於 3/26 日之前來 442-2 領回自己的考卷,如有疑問者請當場提出,考卷攜回或超過期限後不得要求更改分數。
  • 2014-03-06:
    第一次期中考將在 3/28 18:30 舉行,請同學們提早準備,學號單數R101,雙數R104。
  • 2014-03-03:
    Quiz 1 已批改完畢,批改原則與參考解答已公佈於課程網頁上,請想知道 Quiz 1 成績的同學於 3/19 日之前來 442-2 領回自己的考卷,如有疑問者請當場提出,考卷攜回或超過期限後不得要求更改分數。
  • 2014-02-20:
    今天早上有拿到白色加簽單但無法加選的同學,請於明天(2/21)下午15:00~17:00至R432找助教換取新的授權碼。
  • 2014-02-19:
    自第二週起,每次上課結束時會有10分鐘的隨堂考(13:00~13:10),考試地點在原教室R102(學號為單號者)以及R104(學號為雙號者),考試範圍為前一週的上課內容。
  1. Textbook:

    Discrete and Combinatorial Mathematics, Ralph P. Grimaldi, Addison Wesley, Fifth Edition (新月出版社)
    http://www.amazon.com/Discrete-Combinatorial-Mathematics-Applied-Introduction/dp/0201726343/ref=sr_1_1?ie=UTF8&s=books&qid=1221710038&sr=1-1

  2. 課程大綱:

    Part I: Combinatorics:
    • Principle of Inclusion and Exclusion
    • Generating Functions
    • Recurrence Relation
    投影片下載: Combinatorics

    Part II: Algebra:
    • Logic
    • Relations
    • Boolean Algebra
    • Rings
    • Groups
    投影片下載: Algebra

    Part III: Graph Theory:
    • Preliminaries
    • Spanning Trees and Connectivity
    • Paths
    • Miscellaneous Topics
      • Planar Graphs
      • Matching
      • Cliques, Independent Sets, and Vertex Covers
      • Maximum Flow and Minimum Cut
      • Coloring, Chromatic Numbers, and Chromatic Polynomial
    投影片下載: Graph Theory

  3. 預估每位修課同學每週須花費5~10小時課後複習與練習,另須花費10~20小時準備每次期中(末)考。

    1. Combinatorics
      1. Exercise 1: 範圍: P.1 ~ P.44 (pdf)
        Solution 1: (pdf)
      2. Exercise 2: 範圍: P.45 ~ P.81 (pdf)
        Solution 2: (pdf)
      3. Exercise 3: 範圍: P.82 ~ P.104 (pdf)
        Solution 3: (pdf)
      4. Exercise 4: 範圍: P.105 ~ P.146 (pdf)
        Solution 4: (pdf)

    2. Algebra
      1. Exercise 5: 範圍: P.1 ~ P.54 (pdf)
        Solution 5: (pdf)
      2. Exercise 6: 範圍: P.55 ~ P.94 (pdf)
        Solution 6: (pdf)
      3. Exercise 7: 範圍: P.95 ~ P.137 (pdf)
        Solution 7: (pdf)
      4. Exercise 8: 範圍: P.138 ~ P.173 (pdf)
        Solution 8: (pdf)

    3. Graph Theory
      1. Exercise 9: 範圍: P.1 ~ P.22 (pdf)
        Solution 9: (pdf)
      2. Exercise 10: 範圍: P.23 ~ P.62 (pdf)
        Solution 10: (pdf)
      3. Exercise 11: 範圍: P.63 ~ P.90 (pdf)
        Solution 11: (pdf)
      4. Exercise 12: 範圍: P.91 ~ P.146 (pdf)
        Solution 12: (pdf)
  1. 自第二週起,每次上課結束時(約13:00)有隨堂考,考試範圍為前一週的上課內容。
  2. 本課程有兩次期中考和一次期末考,範圍分別是 Combinatorics, Algebra 與 Graph Theory。期中考於考試範圍教完後之下週五晚上18:30~21:00舉行。期末考依照校定時間舉行。
  3. Quiz 1 參考解答
  4. Quiz 2 參考解答
  5. Quiz 3 參考解答
  6. Quiz 4 參考解答
  7. Quiz 5 參考解答
  8. 第一次期中考 參考解答
  9. Quiz 6 參考解答
  10. Quiz 7 參考解答
  11. Quiz 8 參考解答
  12. Quiz 9 參考解答
  13. Quiz 10 參考解答
  14. 第二次期中考 參考解答
  15. Quiz 11 參考解答
  16. Quiz 12 參考解答
  17. Quiz 13 參考解答
  1. 隨堂考佔30%。
  2. 期中期末考佔60%(每次各佔20%)。
  3. 學習態度與出席狀況佔10%。
  4. 考卷發回時,若對分數有異議,請先行將考卷交回助教保管,並與助教約定時間討論。考卷攜回後,不得要求更改分數。
  5. Quiz 1 批改原則:
    • 寫出解題想法且方向正確者,得1分。
      • Ex:排容、生成函數、暴力法...
    • 寫出想法且想法公式列舉正確者,得5分。
      • Ex: 列出排容符號與式子、生成函數式子求某項係數、暴力法列舉完畢...
    • 寫出想法且想法公式與計算皆正確者,得10分。
    • 非以上三者,得0分。
  6. Quiz 2 批改原則:
    • 解題想法正確但沒後續或後續助教看不懂 或 解題想法錯誤但後面有掙扎的計算過程 或 使用暴力法卻算錯者,得3分。
    • 解題想法正確且助教後面看得懂(不含暴力法),可惜推導過程有誤者,無論答案是否正確,得5分。
    • 加減乘除計算過程失誤,其餘觀念皆正確者,得8分。
    • 觀念正確且全對者,得10分。
    • 非以上四者,得0分。
  7. Quiz 3 批改原則:
    • 想法錯誤或起始假設錯誤,得3分。
    • 觀念正確,推導過程有誤者,,得5分。
    • 觀念正確,最後答案計算錯誤,得8分。
    • 觀念正確且全對者,得10分。
    • 非以上四者,得0分。
  8. Quiz 4 批改原則:
    • 有寫東西者,得3分。
    • particular解和homogeneous解有一者寫對者,得5分。
    • particular解和homogeneous解皆寫對者,得7分。
    • 全對者,得10分。
    • 非以上四者,得0分。
  9. Quiz 5 批改原則:
    • 想法錯誤或起始假設錯誤,得3分。
    • 觀念正確,證明過程有瑕疵,得7分。
    • 觀念正確且全對者,得10分。
    • 非以上四者,得0分。
  10. Quiz 6 批改原則:
    • 少寫一個Relation扣一分,多寫一個Relation也扣一分
  11. Quiz 7 批改原則:
    • 非白卷,得3分。
    • 證對一者,得7分。
    • 全對,得10分。
    • 非以上三者,得0分。
  12. Quiz 9 批改原則:
    • 非白卷,得3分。
    • 計算錯誤者,得5分。
    • 計算正確,卻沒寫[5],得8分。 (未寫in Z_72者此次小考不扣分,但有寫才是正確的。)
    • 全對,得10分。
    • 非以上四者,得0分。
林蔚茵 上課內容諮詢;考卷批改 R432 r97079@csie.ntu.edu.tw
TA hour: 週一 16:00 ~ 17:00
TA hour: 週三 16:00 ~ 17:00
謝政佑 課前教具準備;考卷批改;事項公告;網頁維護

R442-2 r01922114@ntu.edu.tw
陳冠綸 課前教具準備;考卷批改;事項公告;網頁維護 R442-2 r01944029@ntu.edu.tw