Mathematical Structures for Computer Science - Judith Gersting

. .

Résumé :
1.? Formal Logic?????????

1.1? Statements, Symbolic Representation, and Tautologies???
Connectives and Truth Values??????
Tautologies?????????
Logical Connectives in the Real World?????
An Algorithm????????
Special Interest Page - Can And Ever Be Or?
Section 1.1 Review?
Exercises 1.1?????????1.2? Propositional Logic????????
Valid Arguments????????
Derivation Rules for Propositional Logic?????
Deduction Method and Other Rules?????
Verbal Arguments????????
Section 1.2 Review?
Exercises 1.2?????????1.3? Quantifiers, Predicates, and Validity??????
Quantifiers and Predicates???????
Translation?????????
Validity?????????
Section 1.3 Review?
Exercises 1.3?????????1.4? Predicate Logic????????
Derivation Rules for Predicate Logic?????
Universal Instantiation??????
Existential Instantiation??????
Universal Generalization??????
Existential Generalization??????
More Work with Rules???????
Verbal Arguments????????
Conclusion?????????
Section 1.4 Review?
Exercises 1.4?????????1.5? Logic Programming????????
Prolog?????????
Horn Clauses and Resolution??????
Recursion?????????
Expert Systems????????
Section 1.5 Review?
Exercises 1.5?????????1.6? Proof of Correctness????????
Assertions?????????
Assignment Rule????????
Conditional Rule????????
Section 1.6 Review?
Exercises 1.6?????????Chapter 1 Review?????????
On the Computer?????????2.? Proofs, Induction, and Number Theory??????

2.1? Proof Techniques????????
Theorems and Informal Proofs??????
To Prove or Not to Prove???????
Exhaustive Proof????????
Direct Proof????????
Contraposition????????
Contradiction????????
Serendipity?????????
Common Definitions???????
Section 2.1 Review?
Exercises 2.1?????????2.2? Induction???????????
First Principle of Induction???
Proofs by Mathematical Induction?
Second Principle of Induction?
Section 2.2 Review?
Exercises 2.2?2.3? More on Proof of Correctness?
Loop Rule?
Euclidean Algorithm?
Special Interest Page - Making Safer Software?
Section 2.3 Review?
Exercises 2.32.4? Number Theory?
The Fundamental Theorem of Arithmetic??
More on Prime Numbers?
Euler Phi Function
Section 2.4 Review?
Exercises 2.4?Chapter 2 Review?
On the Computer3.? Recursion, Recurrence Relations, and Analysis of Algorithms

3.1? Recursive Definitions?
Recursively Defined Sequences?
Recursively Defined Sets?
Recursively Defined Operations?
Recursively Defined Algorithms
Section 3.1 Review
Exercises 3.1?3.2? Recurrence Relations??
Linear First-Order Recurrence Relations?
Expand, Guess, and Verify?
A Solution Formula?
Linear Second-Order Recurrence Relations?
Divide-and-Conquer Recurrence Relations?
Section 3.2 Review
Exercises 3.2?3.3? Analysis of Algorithms?
The General Idea?
Analysis Using Recurrence Relations??
Upper Bound (Euclidean Algorithm)?
Special Interest Page - Of Trees ... and Pancakes
Section 3.3 Review
Exercises 3.3?Chapter 3 Review?
On the Computer?4.? Sets, Combinatorics, and Probability???

4.1? Sets??
Notation?
Relationships between Sets?
Sets of Sets?
Binary and Unary Operations?
Operations on Sets?
Set Identities?
Countable and Uncountable Sets?
Section 4.1 Review
Exercises 4.1?4.2? Counting?
Multiplication Principle?
Addition Principle?
Using the Principles Together?
Decision Trees?
Section 4.2 Review
Exercises 4.2?
??
4.3? Principle of Inclusion and Exclusion...

Sommaire:
Pigeonhole Principle?
Principle of Inclusion and Exclusion?
Pigeonhole Principle?
Section 4.3 Review?
Exercises 4.3?4.4? Permutations and Combinations?
Permutations?
Combinations?
Eliminating Duplicates?
Permutations and Combinations with Repetitions
Generating Permutations and Combinations
Special Interest Page - Archimedes and the Stomachion?
Section 4.4 Review
Exercises 4.4?4.5 Binomial Theorem?
Pascals Triangle?
Binomial Theorem and Its Proof?
Applying the Binomial Theorem?
Section 4.5 Review
Exercises 4.54.6?? Probability?
Introduction to Finite Probability?
Probability Distributions?
Conditional Probability
Bayes Theorem?
Expected Value?
Binomial Distribution?
Average Case Analysis of Algorithms
Section 4.5 Review
Exercises 4.6?Chapter 4 Review?
On the Computer ?5.? Relations, Functions, and Matrices?

5.1? Relations?
Binary Relations?
Properties of Relations?
Closures of Relations?
Partial Orderings?
Equivalence Relations?
Section 5.1 Review
Exercises 5.1?5.2? Topological Sorting?
Section 5.2 Review
Exercises 5.2?5.3? Relations and Databases?
Entity-Relationship Model?
Relational Model?
Operations on Relations?
Null Values and Three-Valued Logic?
Database Integrity?
Section 5.3 Review
Exercises 5.3?5.4? Functions?
Definition?
Properties of Functions?
Onto Functions?
One-to-One Functions?
Bijections?
Composition of Functions?
Inverse Functions?
Permutation Functions?
How Many Functions?
Equivalent Sets??
Section 5.4 Review
Exercises 5.4?5.5? Order of Magnitude
Function Growth
More on Analysis of Algorithms?
The Master Theorem
Proof of the Master Theorem
Section 5.5 Review
Exercises 5.55.6? The Mighty Mod Function?
Hashing?
Computer Security??
Cryptography?
Hashing for Password Encryption?
Miscellaneous Applications?
Identification Codes?
Generating and Decomposing Integers?
Modular Arithmetic Designs?
Section 5.6 Review?
Exercises 5.6?
????
5.7 Matrices?
Terminology?
Matrix Operations
Gaussian Elimination?
Boolean Matrices
Special Interest Page - Solve Millions of Equations, Faster than Gauss
Section 5.7 Review
Exercises 5.7?
?
Chapter 5 Review?
On the Computer ?6.? Graphs and Trees??

6.1? Graphs and their Representations?
Definitions of a Graph?
Applications of Graphs?
Graph Terminology?
Isomorphic Graphs?
Planar Graphs?
Computer Representation of Graphs?
Adjacency Matrix?
Adjacency List
Special Interest Page - Isomorphic Protein Graphs?
Section 6.1 Review
Exercises 6.1?6.2? Trees and their Representations?
Tree Terminology?
Applications of Trees?
Binary Tree Representation?
Tree Traversal Algorithms?
Results About Trees?
Section 6.2 Review
Exercises 6.2??
??
6.3? Decision Trees?
Searching?
Lower Bounds on Searching?
Binary Tree Search?
Sorting?
Section 6.3 Review
Exercises 6.3?6.4? Huffman Codes?
Problem and Trial Solution?
Huffman Encoding Algorithm?
Justification?
Application of Huffman Codes
Section 6.4 Review
Exercises 6.4?
?
Chapter 6 Review?
On the Computer ?7.? Graph Algorithms?

7.1? Directed Graphs and Binary Relations...