- Practical Discrete Mathematics
- Why subscribe?
- Contributors
- About the authors
- About the reviewer
- Packt is searching for authors like you
- Preface
- Who this book is for
- What this book covers
- Part I – Basic Concepts of Discrete Math
- Part II – Implementing Discrete Mathematics in Data and Computer Science
- Part III – Real-World Applications of Discrete Mathematics
- To get the most out of this book
- Download the example code files
- Download the color images
- Conventions used
- Get in touch
- Reviews
- Part I – Basic Concepts of Discrete Math
- Chapter 1: Key Concepts, Notation, Set Theory, Relations, and Functions
- What is discrete mathematics?
- Elementary set theory
- Definition–Sets and set notation
- Definition: Elements of sets
- Definition: The empty set
- Example: Some examples of sets
- Definition: Subsets and supersets
- Definition: Set-builder notation
- Example: Using set-builder notation
- Definition: Basic set operations
- Definition: Disjoint sets
- Example: Even and odd numbers
- Theorem: De Morgan's laws
- Example: De Morgan's Law
- Definition: Cardinality
- Example: Cardinality
- Functions and relations
- Definition: Relations, domains, and ranges
- Definition: Functions
- Examples: Relations versus functions
- Example: Functions in elementary algebra
- Example: Python functions versus mathematical functions
- Summary
- Chapter 2: Formal Logic and Constructing Mathematical Proofs
- Formal Logic and Proofs by Truth Tables
- Basic Terminology for Formal Logic
- Example – an invalid argument
- Example – all penguins live in South Africa!
- Cores Ideas in Formal Logic
- Truth Tables
- Example – The Converse
- Example – Transitivity Law of Conditional Logic
- Example – De Morgan's Laws
- Example – The Contrapositive
- Direct Mathematical Proofs
- Example – Products of Even and Odd Integers
- Example – roots of even numbers
- Shortcut – The Contrapositive
- Proof by Contradiction
- Example – is there a smallest positive rational number?
- Example – Prove is an Irrational Number
- Example – How Many Prime Numbers Are There?
- Proof by mathematical induction
- Example – Adding 1 + 2 + … + n
- Example – Space-Filling Shapes
- Example – exponential versus factorial growth
- Summary
- Chapter 3: Computing with Base-n Numbers
- Understanding base-n numbers
- Example – Decimal numbers
- Definition – Base-n numbers
- Converting between bases
- Converting base-n numbers to decimal numbers
- Example – Decimal value of a base-6 number
- Base-n to decimal conversion
- Example – Decimal to base-2 (binary) conversion
- Example – Decimal to binary and hexadecimal conversions in Python
- Binary numbers and their applications
- Boolean algebra
- Example – Netflix users
- Hexadecimal numbers and their application
- Example – Defining locations in computer memory
- Example – Displaying error messages
- Example – Media Access Control (MAC) addresses
- Example – Defining colors on the web
- Summary
- Chapter 4: Combinatorics Using SciPy
- The fundamental counting rule
- Definition – the Cartesian product
- Theorem – the cardinality of Cartesian products of finite sets
- Definition – the Cartesian product (for n sets)
- Theorem – the fundamental counting rule
- Example – bytes
- Example – colors on computers
- Counting permutations and combinations of objects
- Definition – permutation
- Example – permutations of a simple set
- Theorem – permutations of a set
- Example – playlists
- Growth of factorials
- Theorem – k-permutations of a set
- Definition – combination
- Example – combinations versus permutation for a simple set
- Theorem – combinations of a set
- Binomial coefficients
- Example – teambuilding
- Example – combinations of balls
- Applications to memory allocation
- Example – pre-allocating memory
- Efficacy of brute-force algorithms
- Example – Caesar cipher
- Example – the traveling salesman problem
- Summary
- Chapter 5: Elements of Discrete Probability
- The basics of discrete probability
- Definition – random experiment
- Definitions – outcomes, events, and sample spaces
- Example – tossing coins
- Example – tossing multiple coins
- Definition – probability measure
- Theorem – elementary properties of probability
- Example – sports
- Theorem – Monotonicity
- Theorem – Principle of Inclusion-Exclusion
- Definition – Laplacian probability
- Theorem – calculating Laplacian probabilities
- Example – tossing multiple coins
- Definition – independent events
- Example – tossing many coins
- Conditional probability and Bayes' theorem
- Definition – conditional probability
- Example – temperatures and precipitation
- Theorem – multiplication rules
- Theorem – the Law of Total Probability
- Theorem – Bayes' theorem
- Bayesian spam filtering
- Random variables, means, and variance
- Definition – random variable
- Example – data transfer errors
- Example – empirical random variable
- Definition – expectation
- Example – empirical random variable
- Definition – variance and standard deviation
- Theorem – practical calculation of variance
- Example – empirical random variable
- Google PageRank I
- Summary
- Part II – Implementing Discrete Mathematics in Data and Computer Science
- Chapter 6: Computational Algorithms in Linear Algebra
- Understanding linear systems of equations
- Definition – Linear equations in two variables
- Definition – The Cartesian coordinate plane
- Example – A linear equation
- Definition – System of two linear equations in two variables
- Definition – Systems of linear equations and their solutions
- Definition – Consistent, inconsistent, and dependent systems
- Matrices and matrix representations of linear systems
- Definition – Matrices and vectors
- Definition – Matrix addition and subtraction
- Definition – Scalar multiplication
- Definition – Transpose of a matrix
- Definition – Dot product of vectors
- Definition – Matrix multiplication
- Example – Multiplying matrices by hand and with NumPy
- Solving small linear systems with Gaussian elimination
- Definition – Leading coefficient (pivot)
- Definition – Reduced row echelon form
- Algorithm – Gaussian elimination
- Example – 3-by-3 linear system
- Solving large linear systems with NumPy
- Example – A 3-by-3 linear system (with NumPy)
- Example – Inconsistent and dependent systems with NumPy
- Example – A 10-by-10 linear system (with NumPy)
- Summary
- Chapter 7: Computational Requirements for Algorithms
- Computational complexity of algorithms
- Understanding Big-O Notation
- Complexity of algorithms with fundamental control structures
- Sequential flow
- Selection flow
- Repetitive flow
- Complexity of common search algorithms
- Linear search algorithm
- Binary search algorithm
- Common classes of computational complexity
- Summary
- References
- Chapter 8: Storage and Feature Extraction of Graphs, Trees, and Networks
- Understanding graphs, trees, and networks
- Definition: graph
- Definition: degree of a vertex
- Definition: paths
- Definition: cycles
- Definition: trees or acyclic graphs
- Definition: networks
- Definition: directed graphs
- Definition: directed networks
- Definition: adjacent vertices
- Definition: connected graphs and connected components
- Using graphs, trees, and networks
- Storage of graphs and networks
- Definition: adjacency list
- Definition: adjacency matrix
- Definition: adjacency matrix for a directed graph
- Efficient storage of adjacency data
- Definition: weight matrix of a network
- Definition: weight matrix of a directed network
- Feature extraction of graphs
- Degrees of vertices in a graph
- The number of paths between vertices of a specified length
- Theorem: powers of adjacency matrices
- Matrix powers in Python
- Theorem: minimum-edge paths between vi and vj
- Summary
- Chapter 9: Searching Data Structures and Finding Shortest Paths
- Searching Graph and Tree data structures
- Depth-first search (DFS)
- A Python implementation of DFS
- The shortest path problem and variations of the problem
- Shortest paths on networks
- Beyond Shortest-Distance Paths
- Shortest Path Problem Statement
- Checking whether Solutions Exist
- Finding Shortest Paths with Brute Force
- Dijkstra's Algorithm for Finding Shortest Paths
- Dijkstra's algorithm
- Applying Dijkstra's Algorithm to a Small Problem
- Python Implementation of Dijkstra's Algorithm
- Example – shortest paths
- Example – A network that is not connected
- Summary
- Part III – Real-World Applications of Discrete Mathematics
- Chapter 10: Regression Analysis with NumPy and Scikit-Learn
- Chapter 11: Web Searches with PageRank
- Chapter 12: Principal Component Analysis with Scikit-Learn
- Other Books You May Enjoy
Part III – Real-World Applications of Discrete Mathematics
Here you will learn how to apply discrete math to real-world, large-scale problems, including machine learning—in the shape of regression analysis for building predictive models and principal component analysis for dimensionality reduction—and modern web searches.
This part comprises the following chapters:
- Chapter 10, Regression Analysis with NumPy
- Chapter 11, Web Searches with PageRank
- Chapter 12, Principal Component Analysis with Scikit-Learn
-
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.