MIT OpenCourseWare


» 進階搜尋
課程首頁
教學大綱
教學時程
相關閱讀資料
課堂講稿
作業
測驗
討論群組

教學時程


本頁翻譯進度

燈號說明

審定：林道通(Daw-Tung Dalton Lin)(簡介並寄信)
審定簡介：
中華大學工學院院長/資訊工程系
國立交通大學學士美國馬里蘭大學電機工程碩士
美國馬里蘭大學電機工程博士
研究領域:
類神經網路理論與應用
智慧型數位監控
醫學影像電腦輔助診斷與類神經網路、模糊理論系統之整合
生物資訊：蛋白質電泳圖分析


翻譯：簡明山(簡介並寄信) 編輯：朱學恒(簡介並寄信)
這個行事曆顯示了課程的每週計畫表，每星期通常有三次講課和一堂小組解題課。每一個星期的閱讀材料都出自教科書，《離散數學與其應用》(Discrete Mathematics and its Applications)第四版，Kenneth H. Rosen 著。行事曆中還提供了課堂講稿（投影片）、課堂問題、講課投影片、課堂講義、習題、測驗與考試與其他相關資料的連結。除了回家作業外，學生可以透過線上教學系統來完成閱讀問題與當週的指定閱讀。目前這個網站無法提供線上教學的資料，想要獲得線上教學資料的老師請與麻省理工學院開放式課程小組連絡。

第一週

主題：課程概述、基本證明方法、命題邏輯

第二週

主題：量數(Quantifier)、歸納(Induction)、強歸納(Strong Induction)
  • 閱讀：課堂講義 2 (PDF)；Rosen課本：3.2節、3.3到範例6。
  • 本週工作：習題 2 (PDF)，解答 (PDF)，閱讀問題 2（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五

第三週

主題：關係式(Relations)
  • 閱讀：課堂講義 3 (PDF)；Rosen課本：6.1節、6.3-6.6節（略過Warshall演算法與點陣）。
  • 本週工作：習題 3 (PDF)，解答 (PDF)，閱讀問題 3（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五

第四週

主題：圖論(Graphs)
  • 閱讀：課堂講義 4 (PDF)；額外補充（選讀）Rosen課本：7.1-7.4節、7.8節、8.1節。
  • 本週工作：習題 4 (PDF)，解答 (PDF)，閱讀問題 4（線上教學）
  • 星期三
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 四色定理的歷史與證明。
  • 維吉尼亞大學發表的「Kevin Bacon的神喻」，你是否可以找出一個演員與Bacon的關係數大於4？
    (朱註：這是一個統計上的著名例子，簡介可參考：《連結》一書的簡介。)

第五週

主題：狀態機(State Machine)：不變量(Invariant)和結束狀態(Termination)
  • 閱讀：課堂講義 5 (PDF - 1.0 MB)
  • 本週工作：習題 5 (PDF)，解答 (PDF)，閱讀問題 5（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第六週

主題：遞迴(Recursive)的定義和結構化歸納(Structural Induction)
  • 閱讀：課堂講義 6 (PDF)；選讀：Rosen課本：3.3節。
  • 沒有閱讀問題。
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第七週

主題：總和(Sums)與級數(Series)、乘積(Products)、Stirling公式、漸近級數(Asymptotics)
  • 閱讀：課堂講義 7 (PDF)；選讀：Rosen課本：1.7-1.8節、由Stirling公式整理出的一頁(Romik, D. 「Stirling對 n! 的概算：超短證明？」(Stirling's Approximation for n!: the Ultimate Short Proof?)，《美國數學月刊》(American Mathematical Monthly), 107 (2000)第556-557頁。)
  • 本週工作：習題 6-7 (PDF) ，解答 (PDF)，閱讀問題 7（線上教學）
    • 習題6-7問題1的附註：
      • glb ::= 「最大下界」與 lub ::= 「最小上界」，可參考Rosen課本第423頁。
      • 勝負樹(payoff tree)與其最大值的一個例子：(PDF)
  • 星期三
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第八週

主題：匹配(Matching)計數，鴿籠原理(Pigeonhole)、集合的和與積(Sum and Product Rules)、容斥原則、(Inclusion/Exclusion)、排列(Permutation)
  • 閱讀：課堂講義 8 (PDF)；選讀：Rosen課本：4.1-4.2節。
  • 本週工作：習題 8 (PDF)，解答 (PDF)，閱讀問題 8（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第九週

主題：集合的除法(Division Rule)、組合(Combination)、重覆計數(Counting with Repetitions)
  • 閱讀：課堂講義 9（附加一段談論魔術技巧的章節）(PDF - 1.1 MB)；選讀：Rosen課本：4.3節、4.6節。
  • 本週工作：習題 9 (PDF)，解答 (PDF)，閱讀問題 9（線上教學）
  • 星期一
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第十週

主題：介紹機率、條件機率(Conditional Probability)、獨立事件(Independence)
  • 閱讀：
    • 閱讀問題與週三/週五講義：完整的課堂講義 10 (PDF - 1.4 MB); 選讀：Rosen課本：4.4節、4.5節到範例9，第274頁。
    • 習題 10 (PDF)與隨堂考2只需要閱讀部分教材：課堂講義 10 第1節-第9節 (PDF - 1.4 MB)；選讀：Rosen課本：4.4節、4.5節到範例4，第271頁。
  • 本週工作：一個簡短習題 10 (PDF)，解答 (PDF)，閱讀問題 10（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第十一週

主題：介紹隨機變數：分布(Random Variables: Distribution)
  • 隨堂考 2 (PDF)，附錄 (PDF)，解答 (PDF)
  • 星期五閱讀：課堂講義 11-12 (PDF - 1.4 MB) 第1節-第4節。
  • 沒有閱讀問題。
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第十二週

主題：隨機變數：期望值(Random Variables: Expectation)
  • 閱讀：課堂講義 11-12 (PDF - 1.4 MB)；選讀：Rosen課本：4.5節到範例18。
  • 本週工作：習題 11-12, (PDF)，解答 (PDF)，閱讀問題 11-12（線上教學）
  • 星期一
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第十三週

主題：變異數(Variance)、離均差(Deviation from the Mean)、弱大數法則(Weak Law of Large Numbers)
  • 閱讀：課堂講義 13-14 (PDF - 1.6 MB) 第1節-第6.2節
  • 本週工作：習題 13-14 (PDF)，解答 (PDF)，閱讀問題 13（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第十四週

主題：弱大數法則(Weak Law of Large Numbers)、取樣(Sampling)、信賴水準(Confidence)、隨機漫步(Random Walk)、Chernoff係數(Chernoff Bound)
  • 閱讀：課堂講義 13-14 (PDF - 1.6 MB) 第6.3節-第18節
  • 本週工作：閱讀問題 14（線上教學）
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期五
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)

第十五週

主題：中央極限定理(Central Limit Theorem)、Poisson分布(Poisson Distribution)、強大數法則(Strong Law of Large Numbers)
  • 閱讀：課堂講義 15 (PDF)
  • 星期一
    • 課堂講稿 (PDF)
    • 課堂問題 (PDF)，解答 (PDF)
  • 星期三
    • 期末考附錄： (PDF)
    • 課程自我評量表 (PDF)

第十六週

期末考
  • 修正後的考題： (PDF)，附錄 (PDF)
  • 解答草稿： (PDF)
  • 考試時使用的原稿 (PDF)

This calendar shows the weekly schedule for the course, which usually includes three lecture and group problem solving sessions per week. The readings for each week are from the course textbook, Discrete Mathematics and its Applications, Fourth Edition, by Kenneth H. Rosen, and the course notes. This calendar provides links to lecture slides, class problems, course notes, problem sets, quizzes and exams, and relevant links of interest. In addition to problem sets, reading problems, related to the reading assignments for the week, are completed by students using an online tutor. The online tutor is currently not available through this site. Instructors who are interested in obtaining online tutor materials can contact MIT OpenCourseWare with their requests.

Week 1

Topics: Course Overview, Basic Proof Methods, Propositional Logic
  • Reading: Syllabus, Course Notes 1 (PDF), Rosen: 1.1-6, 2.3, 2.4 through Lemma 1, 3.1 through Example 26.
  • Due this week: Problem Set 1 (PDF), Solutions (PDF), Reading Problems 1 (Online Tutor)
  • Wednesday (First day of class)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 2

Topics: Quantifiers, Induction, Strong Induction
  • Reading: Course Notes 2 (PDF); Rosen: 3.2, 3.3 through Example 6.
  • Due this week: Problem Set 2 (PDF), Solutions (PDF), Reading Problems 2 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday

Week 3

Topics: Relations
  • Reading: Course Notes 3 (PDF); Rosen: 6.1, 6.3-6.6 (ignore Warshall's algorithm and lattices).
  • Due this week: Problem Set 3 (PDF), Solutions (PDF), Reading Problems 3 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday

Week 4

Topics: Graphs
  • Reading: Course Notes 4 (PDF); Supplementary (optional) Rosen: 7.1-7.4, 7.8, 8.1.
  • Due this week: Problem Set 4 (PDF), Solutions (PDF), Reading Problems 4 (Online Tutor)
  • Wednesday
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • The Four Color Theorem history and proof.
  • The Oracle of Bacon at Virginia. Can you find an actor with a Bacon number higher than 4?

Week 5

Topics: State Machines, Invariants and Termination
  • Reading: Course Notes 5 (PDF - 1.0 MB)
  • Due this week: Problem Set 5 (PDF), Solutions (PDF), Reading Problems 5 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 6

Topics: Recursive Definitions and Structural Induction
  • Reading: Course Notes 6 (PDF); Optional: Rosen 3.3
  • No Reading Problems.
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 7

Topics: Sums and Series, Products, Stirling's Formula, Asymptotics
  • Reading: Course Notes 7 (PDF); Optional: Rosen 1.7-8; a one-page derivation of Stirling's Formula (Romik, D. "Stirling's Approximation for n!: the Ultimate Short Proof?," American Mathematical Monthly, 107 (2000), 556-557.)
  • Due this week: Problem Set 6-7 (PDF) , Solutions (PDF), Reading Problems 7 (Online Tutor)
    • Notes on PS6-7, Problem 1:
      • glb ::= "greatest-lower-bound'' and lub ::= "least-upper-bound'', cf. Rosen, p. 423.
      • An example payoff tree and its max-value: (PDF)
  • Wednesday
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 8

Topics: Counting by Matching, Pigeonhole, Sum and Product Rules, Inclusion/Exclusion, Permutations
  • Reading: Course Notes 8 (PDF); Optional: Rosen 4.1-2
  • Due this week: Problem Set 8 (PDF), Solutions (PDF), Reading Problems 8 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 9

Topics: Division Rule, Combinations, Counting with Repetitions
  • Reading: Course Notes 9 (A section on the Magic Trick has been added) (PDF - 1.1 MB); Optional: Rosen 4.3, 4.6
  • Due this week: Problem Set 9 (PDF), Solutions (PDF), Reading Problems 9 (Online Tutor)
  • Monday
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 10

Topics: Introduction to Probability, Conditional Probability, Independence
  • Reading:
    • For Reading Problems and Wed-Fri Lectures: Complete Course Notes 10 (PDF - 1.4 MB); Optional: Rosen 4.4, and 4.5 through Example 9, p. 274.
    • For Problem Set 10 (PDF) and Quiz 2 only part of the reading is necessary: Course Notes 10, sections 1--9 (PDF - 1.4 MB); Optional: Rosen 4.4, and 4.5 through Example 4, p.271.
  • Due this week: a short Problem Set 10 (PDF), Solutions (PDF), Reading Problems 10 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 11

Topics: Introduction to Random Variables: Distributions
  • Quiz 2 (PDF), Appendix (PDF), Solutions (PDF)
  • Reading For Friday Lecture: Course Notes 11-12 (PDF - 1.4 MB), Sections 1--4.
  • No Reading Problems.
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 12

Topics: Random Variables: Expectation
  • Reading: Course Notes 11-12 (PDF - 1.4 MB); Optional: Rosen 4.5 thru Example 18.
  • Due this week: Problem Set 11-12, (PDF), Solutions (PDF), Reading Problems 11-12 (Online Tutor)
  • Monday
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 13

Topics: Variance, Deviation from the Mean, Weak Law of Large Numbers
  • Reading: Course Notes 13-14 (PDF - 1.6 MB), Sections 1--6.2
  • Due this week: Problem Set 13-14 (PDF), Solutions (PDF), Reading Problems 13 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 14

Topics: Weak Law of Large Numbers, Sampling, Confidence, Random Walks, Chernoff Bound
  • Reading: Course Notes 13-14 (PDF - 1.6 MB), Sections 6.3--18
  • Due this week: Reading Problems 14 (Online Tutor)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Friday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)

Week 15

Topics: Central Limit Theorem, Poisson Distribution, Strong Law of Large Numbers
  • Reading: Lecture Notes 15 (PDF)
  • Monday
    • Lecture Slides (PDF)
    • Class Problems (PDF), Solutions (PDF)
  • Wednesday
    • Final Exam Appendix: (PDF)
    • Exit Self-Assessment (PDF)

Week 16

Final Exam
  • with corrections (PDF), Appendix (PDF),
  • draft solution (PDF)
  • original as used (PDF)


MIT Home
Massachusetts Institute of Technology Terms of Use Privacy