Lehman E., Leighton F.T., Meyer A.R. Mathematics for Computer Science

Revised Edition. — MIT, 2012. — 829 p.This text explains how to use mathematical models and methods to analyze problems that arise in computer science. The subject offers an introduction to Discrete Mathematics oriented toward Computer Science and Engineering, adnd covers: Fundamental concepts of Mathematics: definitions, proofs, sets, functions, relations; Discrete structures: graphs, state machines, modular arithmetic, counting; Discrete probability theory.
Readers will be able
- to reason mathematically about basic data types and structures used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.
- to model and analyze computational processes using analytic and combinatorial methods.
- to apply principles of discrete probability to calculate probabilities and expectations of simple random processes.Proofs
What is a Proof?
The Well Ordering Principle
Logical Formulas
Mathematical Data Types
Induction
Recursive Data Types
Infinite Sets
Number Theory
Structures
Directed graphs & Partial Orders
Communication Networks
Simple Graphs
Planar Graphs
Counting
Sums and Asymptotics
Cardinality Rules
Generating Functions
Probability
Events and Probability Spaces
Random Variables
Deviation from the Mean
Random Processes
Recurrences