#concept-pamphlet #class #todo: fill in the terms for the rest
Source Syllabus
-
Discrete Mathematics
- Set Theory, The Limits of Computing
- Direct Proofs
- Proof by Contradiction, Proof by Contrapositive
- Propositional Logic
- First-Order Logic
- Binary Relations, Equivalence Relations
- Proving things with Binary Relations, Orders
- Functions, Injections, Surjections, Bijections
- Cardinality, Diagonalization
- Graphs
- The Pigeonhole Principle
- Mathematical Induction
- Formal Language Theory, DFAs, NFAs
- Regular Expressions, Equivalence of Regular Expressions and NFAs
- Nonregular Languages, The Myhill-Nerode Theorem
- Context-Free Grammars, Context-Free Languages
- Turing Machines, Designing Turing Machines
- The Church-Turing Thesis
- R and RE Languages, The Universal Turing Machine
- Self-Reference, Undecidability
- Verifiers, Unrecognizability
-
Computability Theory
- Formal Language Theory
- DFAs and NFAs
- Regular Expressions and NFAs
- Nonregular Languages
- Context-Free Languages
- Turing Machines and The Church-Turing Thesis
- R and RE Languages, Universal Turing Machines
- Self-Reference and Undecidability
- Verifiers and Unrecognizability
-
Complexity Theory
- The P versus NP Question
- NP-Completeness
-
Set Theory
- Study of sets, which are collections of objects. It includes operations such as union and intersection, and covers concepts such as infinite sets and their implications on computing.
-
Direct Proof
- A method of proving mathematical theorems by assuming a set of axioms and logically deducing a theorem directly from them.
- if P then Q
-
Proof by Contradiction
- Proof by contradiction involves assuming the opposite of what needs to be proved and showing that this assumption leads to a contradiction
- if not Q then contradiction
-
Proof by Contrapositive
- if not Q then not P