## 2016-11-03

### Mathematics for Computer Science (Spring 2015) by Albert R. Meyer at MIT

# click the upper-left icon to select videos from the playlist

source: MIT OpenCourseWare     2016年9月12日
MIT 6.042J Mathematics for Computer Science, Spring 2015
View the complete course: http://ocw.mit.edu/6-042JS15
More courses at http://ocw.mit.edu
This subject offers an interactive introduction to discrete mathematics oriented toward computer science and engineering. The subject coverage divides roughly into thirds:
1) Fundamental concepts of mathematics: Definitions, proofs, sets, functions, relations.
2) Discrete structures: graphs, state machines, modular arithmetic, counting.
3) Discrete probability theory.
On completion of 6.042J, students will be able to explain and apply the basic methods of discrete (noncontinuous) mathematics in computer science. They will be able to use these methods in subsequent courses in the design and analysis of algorithms, computability theory, software engineering, and computer systems.

1.1.1 Welcome to 6.042 2:15
1.1.2 Intro to Proofs: Part 1 9:31
1.1.3 Intro to Proofs: Part 2 7:08
1.2.3 Proof by Cases 6:54
1.3.1 Well Ordering Principle 1: Video 5:38
1.3.3 Well Ordering Principle 2: Video 5:24
1.3.5 Well Ordering Principle 3: Video 6:03
1.4.1 Propositional Operators: Video 9:21
1.4.3 Digital Logic: Video 10:03
1.4.4 Truth Tables: Video 12:57
1.5.1 Predicate Logic 1: Video 12:35
1.5.2 Predicate Logic 2: Video 12:00
1.5.4 Predicate Logic 3: Video 8:30
1.6.1 Sets Definitions: Video 12:00
1.6.2 Sets Operations: Video 9:15
1.7.1 Relations: Video 25:13
1.7.3 Relational Mappings: Video 8:53
1.7.5 Finite Cardinality: Video 10:58
1.8.1 Induction: Video 21:42
1.8.2 Bogus Induction: Video 5:03
1.8.4 Strong Induction: Video 10:03
1.8.6 WOP vs Induction: Video [optional] 7:53
1.9.3 Derived Variables: Video 6:24
1.10.1 Recursive Data: Video 12:42
1.10.4 Structural Induction: Video 6:16
1.10.7 Recursive Functions: Video 14:04
1.11.1 Cardinality: Video 12:56
1.11.3 Countable Sets: Video 9:46
1.11.4 Cantor's Theorem: Video 20:23
1.11.7 The Halting Problem: Video [Optional] 16:02
1.11.11 Set Theory Axioms: Video [Optional] 9:20
2.1.1 GCDs & Linear Combinations: Video 9:42
2.1.2 Euclidean Algorithm: Video 9:30
2.1.4 Pulverizer: Video 11:49
2.1.6 Revisiting Die Hard: Video 5:17
2.1.7 Prime Factorization: Video 7:48
2.2.1 Congruence mod n: Video 13:12
2.2.3 Inverses mod n: Video 4:17
2.3.1 Modular Exponentiation Euler's Function: Video 6:13
2.3.3 The Ring Z: Video 16:51
2.4.1 RSA Public Key Encryption: Video 21:45
2.4.3 Reducing Factoring To SAT: Video 7:10
2.5.1 Digraphs: Walks & Paths: Video 3:45
2.5.3 Digraphs: Connected Vertices: Video 6:55
2.6.1 DAGs: Video 11:22
2.6.3 Scheduling: Video 13:17
2.6.5 Time versus Processors: Video 9:45
2.7.1 Partial Orders: Video 10:33
2.7.3 Representing Partial Orders As Subset Relations: Video 6:58
2.7.4 Equivalence Relations: Video 7:12
2.8.1 Degree: Video 11:18
2.8.3 Isomorphism: Video 11:04
2.9.1 Coloring: Video 16:21
2.9.3 Connectivity: Video 3:09
2.9.4 k-Connectivity: Video 8:14
2.10.1 Trees: Video 8:07
2.10.3 Tree Coloring: Video 2:04
2.10.5 Spanning Trees: Video 10:39
2.11.1 Stable Matching: Video 11:20
2.11.2 Matching Ritual: Video 9:18
2.11.5 Optimal Stable Matching: Video 9:06
2.11.7 Bipartite Matching 4:02
2.11.9 Hall's Theorem 15:31
3.1.1 Arithmetic Sums: Video 3:59
3.1.3 Geometric Sums: Video 10:36
3.1.5 Book Stacking: Video 7:41
3.1.7 Integral Method: Video 9:35
3.1.9 Stirling's Formula: Video 5:51
3.2.1 Asymptotic Notation: Video 7:43
3.2.3 Asymptotic Properties: Video 10:12
3.2.6 Asymptotic Blunders 4:33
3.3.1 Sum And Product Rules: Video 7:28
3.3.3 Counting with Bijections: Video 11:43
3.4.1 Generalized Counting Rules: Video 10:06
3.4.3 Two Pair Poker Hands: Video 7:46
3.4.4 Binomial Theorem: Video 5:42
3.4.5 Multinomial Theorem: Video 7:51
3.5.1 The Pigeonhole Principle: Video 4:14
3.5.3 Inclusion-Exclusion Example: Video 13:10
3.5.4 Inclusion-Exclusion 2 Sets: Video 7:10
4.1.1 Tree Model: Video 25:24
4.1.3 Simplified Monty Hall Tree: Video 7:41
4.1.5 Sample Spaces: Video 9:46
4.2.1 Conditional Probability Definitions: Video 12:19
4.2.3 Law of Total Probability: Video 3:33
4.2.5 Bayes' Theorem: Video 11:39
4.2.7 Monty Hall Problem: Video 8:42
4.3.1 Independence: Video 3:36
4.3.3 Mutual Independence: Video 8:19
4.4.1 Bigger Number Game: Video 12:19
4.4.2 Random Variables: Independence: Video 15:31
4.4.4 Random Variables: Uniform & Binomial: Video 11:33
4.5.1 Expectation: Video 18:53
4.5.3 Expected Number Of Heads: Video 4:39
4.5.5 Total Expectation: Video 4:18
4.5.7 Mean Time to Failure: Video 11:25
4.5.9 Linearity of Expectation: Video 18:30
4.6.1 Deviation From The Mean: Video 7:47
4.6.3 Markov Bounds: Video 8:48
4.6.5 Chebyshev Bounds: Video 10:22
4.6.7 Variance: Video 14:35
4.7.1 Law Of Large Numbers: Video 13:49
4.7.3 Independent Sampling Theorem: Video 6:52
4.7.5 Birthday Matching: Video 12:19
4.7.7 Sampling & Confidence: Video 12:57
4.8.1 Random Walks: Video 10:34
4.8.2 Stationary Distributions: Video 16:01
4.8.3 Page Rank: Video 10:59