Nguồn ngoài

Mathematics for Computer Science

This text serves as an introduction to discrete mathematics, probability, and mathematical thinking for computer scientists with an interactive introduction to discrete mathematics oriented toward computer science and engineering. The subject coverage divides roughly into thirds: (1) Fundamental concepts of mathematics including definitions, proofs, sets, functions, relations. (2) Discrete structures: graphs, state machines, modular arithmetic, counting and (3) Discrete probability theory.

Computer Science Engineering

Tác giả: Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Nhà xuất bản: Google and Massachusetts Institute of Technology
Nguồn: LibreTexts
Giấy phép: CC BY-NC-SA
Ngôn ngữ: EN
Danh mục: Công nghệ thông tin

Đọc trực tuyến Tải PDF (nguồn mở)

Mục lục· 167 mục

01: Proofs
01: Intro to Proofs
1.01: Propositions
1.02: Predicates
1.03: The Axiomatic Method
1.04: Our Axioms
1.05: Proving an Implication
1.06: Proving an If and Only If
1.07: Proof by Cases
1.08: Proof by Contradiction
1.09: Good Proofs in Practice
02: Well Ordering Principle
2.01: Well Ordering Proofs
2.02: Template for Well Ordering Proofs
2.03: Factoring into Primes
2.04: Well Ordered Sets
03: Logical Formulas
3.01: Propositions from Propositions
3.02: Propositional Logic in Computer Programs
3.03: Equivalence and Validity
3.04: The Algebra of Propositions
3.05: The SAT Problem
3.06: Predicate Formulas
04: Mathematical Data Types
4.01: Sets
4.02: Sequences
4.03: Functions
4.04: Binary Relations
4.05: Finite Cardinality
05: Induction
5.01: Ordinary Induction
5.02: Strong Induction
5.03: Strong Induction vs. Induction vs. Well Ordering
5.04: State Machines
06: Recursive Data Types
6.01: Recursive Definitions and Structural Induction
6.02: Strings of Matched Brackets
6.03: Recursive Functions on Nonnegative Integers
6.04: Arithmetic Expressions
6.05: Induction in Computer Science
07: Infinite Sets
7.01: Infinite Cardinality
7.02: The Halting Problem
7.03: The Logic of Sets
7.04: Does All This Really Work
02: Structures
08: Number Theory
8.01: Divisibility
8.02: The Greatest Common Divisor
8.03: Prime Mysteries
8.04: The Fundamental Theorem of Arithmetic
8.05: Alan Turing
8.06: Modular Arithmetic
8.07: Remainder Arithmetic
8.08: Turings Code (Version 2.0)
8.09: Multiplicative Inverses and Cancelling
8.10: Euler's Theorem
8.11: RSA Public Key Encryption
8.12: What has SAT got to do with it
09: Directed graphs and Partial Orders
9.01: Vertex Degrees
9.02: Walks and Paths
9.03: Adjacency Matrices
9.04: Walk Relations
9.05: Directed Acyclic Graphs and Scheduling
9.06: Partial Orders
9.07: Representing Partial Orders by Set Containment
9.08: Linear Orders
9.09: Product Orders
9.10: Equivalence Relations
9.11: Summary of Relational Properties
10: Communication Networks
10.01: Complete Binary Tree
10.02: Routing Problems
10.03: Network Diameter
10.04: Switch Count
10.05: Network Latency
10.06: Congestion
10.07: 2-D Array
10.08: Butterfly
10.09: Benes Network
11: Simple Graphs
11.01: Vertex Adjacency and Degrees
11.02: Sexual Demographics in America
11.03: Some Common Graphs
11.04: Isomorphism
11.05: Bipartite Graphs and Matchings
11.06: The Stable Marriage Problem
11.07: Coloring
11.08: Simple Walks
11.09: Connectivity
11.10: Forests and Trees
12: Planar Graphs
12.01: Drawing Graphs in the Plane
12.02: Definitions of Planar Graphs
12.03: Eulers Formula
12.04: Bounding the Number of Edges in a Planar Graph
12.05: Returning to K5 and K33
12.06: Coloring Planar Graphs
12.07: Classifying Polyhedra
12.08: Another Characterization for Planar Graphs
03: Counting
13: Sums and Asymptotics
13.01: The Value of an Annuity
13.02: Sums of Powers
13.03: Approximating Sums
13.04: Hanging Out Over the Edge
13.05: Products
13.06: Double Trouble
13.07: Asymptotic Notation
14: Cardinality Rules
14.01: Counting One Thing by Counting Another
14.02: Counting Sequences
14.03: The Generalized Product Rule
14.04: The Division Rule
14.05: Counting Subsets
14.06: Sequences with Repetitions
14.07: Counting Practice - Poker Hands
14.08: The Pigeonhole Principle
14.09: Inclusion-Exclusion
14.10: Combinatorial Proofs
15: Generating Functions
15.01: Infinite Series
15.02: Counting with Generating Functions
15.03: Partial Fractions
15.04: Solving Linear Recurrences
15.05: Formal Power Series
04: Probability
16: Events and Probability Spaces
16.01: Let's Make a Deal
16.02: The Four Step Method
16.03: Strange Dice
16.04: The Birthday Principle
16.05: Set Theory and Probability
17: Conditional Probability
17.01: Monty Hall Confusion
17.02: Definition and Notation
17.03: The Four-Step Method for Conditional Probability
17.04: Why Tree Diagrams Work
17.05: The Law of Total Probability
17.06: Simpsons Paradox
17.07: Independence
17.08: Mutual Independence
18: Random Variables
18.01: Random Variable Examples
18.02: Independence
18.03: Distribution Functions
18.04: Great Expectations
18.05: Linearity of Expectation
19: Deviation from the Mean
19.01: Markovs Theorem
19.02: Chebyshevs Theorem
19.03: Properties of Variance
19.04: Estimation by Random Sampling
19.05: Confidence versus Probability
19.06: Sums of Random Variables
19.07: Really Great Expectations
20: Random Walks
20.01: Gamblers Ruin
20.02: Random Walks on Graphs
05: Recurrences
21: Recurrences
21.01: The Towers of Hanoi
21.02: Merge Sort
21.03: Linear Recurrences
21.04: Divide-and-Conquer Recurrences
21.05: A Feel for Recurrences