MATHEMATICS FOR COMPUTER SCIENTISTS : a practice -oriented approach

This textbook contains the mathematics needed to study computer science in application-oriented computer science courses. The content is based on the author's many years of teaching experience. The translation of the original German 7 th edition Mathematik für Informatiker by Peter Hartmann was done with the help of artificial intelligence. A subsequent human revision was done primarily in terms of content. Textbook Features You will always find applications to computer science in this book. Not only will you learn mathematical methods, you will gain insights into the ways of mathematical thinking to form a foundation for understanding computer science. Proofs are given when they help you learn something, not for the sake of proving. Mathematics is initially a necessary evil for many students. The author explains in each lesson how students can apply what they have learned by giving many real world examples, and by constantly cross-referencing math and computer science. Students will see how math is not only useful, but can be interesting and sometimes fun. The Content Sets, logic, number theory, algebraic structures, cryptography, vector spaces, matrices, linear equations and mappings, eigenvalues, graph theory. Sequences and series, continuous functions, differential and integral calculus, differential equations, numerics. Probability theory and statistics. The Target Audiences Students in all computer science-related coursework, and independent learners. Preface Contents Part I Discrete Mathematics and Linear Algebra 1 Sets and Mappings Abstract 1.1 Set Theory Relationships between Sets Operations with Sets Calculation Rules for Set Operations The Cartesian Product of Sets 1.2 Relations Equivalence Relations Order Relations 1.3 Mappings The Cardinality of Sets 1.4 Comprehension Questions and Exercises Anchor 14 2 Logic Abstract 2.1 Propositions and Propositional Variables Compound Propositions Boolean Algebras Evaluation of Propositional Formulas in a Program 2.2 Proof Principles The Direct Proof The Proof of Equivalence The Proof by Contradiction 2.3 Predicate Logic (First-Order Logic) Negation of Quantified Predicates 2.4 Logic and Testing of Programs 2.5 Comprehension Questions and Exercises Anchor 15 3 Natural Numbers, Mathematical Induction, Recursion Abstract 3.1 The Axioms of Natural Numbers 3.2 The Mathematical Induction 3.3 Recursive Functions Recursions of Higher Order Runtime Calculations for Recursive Algorithms 3.4 Comprehension Questions and Exercises Anchor 9 4 Some Number Theory Abstract 4.1 Combinatorics 4.2 Divisibility and Euclidean Algorithm 4.3 Modular Arithmetic Calculating with Residue Classes 4.4 Hashing Hash Functions Collision Resolution 4.5 Comprehension Questions and Exercises Anchor 11 5 Algebraic Structures Abstract 5.1 Groups Permutation groups 5.2 Rings Polynomial Rings 5.3 Fields The Field of Complex Numbers The Field 5.4 Polynomial Division Horner’s Method Residue Classes in the Polynomial Ring, The Field ) Using Polynomial Division for Error Detection 5.5 Elliptic Curves Elliptic Curves over the Field of Real Numbers Elliptic Curves Over Finite Fields 5.6 Homomorphisms 5.7 Cryptography Encryption with Secret Keys Encryption with Public Keys The RSA Algorithm The Diffie-Hellman Algorithm The Diffie-Hellman Algorithm with Elliptic Curves Key Generation Random Numbers 5.8 Comprehension Questions and Exercises Anchor 27 6 Vector Spaces Abstract 6.1 The Vector Spaces , and 6.2 Vector Spaces 6.3 Linear Mappings 6.4 Linear Independence 6.5 Basis and Dimension of Vector Spaces 6.6 Coordinates and Linear Mappings 6.7 Comprehension Questions and Exercises Anchor 10 7 Matrices Abstract 7.1 Matrices and Linear Mappings in Composition of linear mappings 7.2 Matrices and Linear Mappings from Kn → Km Matrix multiplication and composition of linear mappings 7.3 The Rank of a Matrix 7.4 Comprehension Questions and Exercises Anchor 9 8 Gaussian Algorithm and Linear Equations Abstract 8.1 The Gaussian Algorithm 8.2 Calculating the Inverse of a Matrix 8.3 Systems of Linear Equations Geometrical Interpretation of Systems of Linear Equations Ray Tracing, Part 1 Solution of Systems of Linear Equations Using the Gaussian Algorithm 8.4 Comprehension Questions and Exercises Anchor 10 9 Eigenvalues, Eigenvectors and Change of Basis Abstract 9.1 Determinants 9.2 Eigenvalues and Eigenvectors 9.3 Change of Basis Orientation of Vector Spaces Ray Tracing, Part 2 9.4 Comprehension Questions and Exercises Anchor 9 10 Dot Product and Orthogonal Mappings Abstract 10.1 Dot Product Where Does the Mouse Click? 10.2 Orthogonal Mappings The orthogonal linear mappings in and 10.3 Homogeneous Coordinates Basis Transitions in Robotics 10.4 Comprehension Questions and Exercises Anchor 10 11 Graph Theory Abstract 11.1 Basic Concepts of Graph Theory Paths in Graphs Centrality of Nodes—Who is the Most Important? 11.2 Trees Rooted Trees Search Trees The Huffman Code 11.3 Traversing Graphs Shortest Paths 11.4 Directed Graphs 11.5 Comprehension Questions and Exercises Anchor 14 Part II Analysis 12 The Real Numbers Abstract 12.1 The Axioms of Real Numbers The Order Axioms The Completeness Axiom 12.2 Topology 12.3 Comprehension Questions and Exercises Anchor 8 13 Sequences and Series Abstract 13.1 Sequences of Numbers Convergent Sequences The Big O Notation Monotonic Sequences 13.2 Series Convergence Tests for Series 13.3 Representation of Real Numbers in Numeral Systems 13.4 Comprehension Questions and Exercises Anchor 11 14 Continuous Functions Abstract 14.1 Continuity Functions of several variables 14.2 Elementary Functions 14.3 Properties of Continuous Functions Theorems About Continuous Functions Logarithm and General Exponential Function The Trigonometric Functions Numerical Calculation of Trigonometric Functions Radian and polar coordinates 14.4 Comprehension Questions and Exercises Anchor 13 15 Differential Calculus Abstract 15.1 Differentiable Functions Differentiation Rules Calculation of Extrema 15.2 Power Series 15.3 Taylor Series 15.4 Differential Calculus of Functions of Several Variables Extrema The Regression Line 15.5 Comprehension Questions and Exercises Anchor 12 16 Integral Calculus Abstract 16.1 The Integral of Piecewise Continuous Functions Integration Rules 16.2 Applications of the Integral Volumes of Shapes The Arc of a Curve Improper Integrals 16.3 Fourier Series Discrete Fourier Transform 16.4 Comprehension Questions and Exercises Anchor 12 17 Differential Equations Abstract 17.1 What are Differential Equations? 17.2 First Order Differential Equations Separable Differential Equations First Order Linear Differential Equations 17.3 nth Order Linear Differential Equations Linear Differential Equations with Constant Coefficients Inhomogeneous Linear Differential Equations 17.4 Comprehension Questions and Exercises Anchor 11 18 Numerical Methods Abstract 18.1 Problems with Numerical Calculations Real Numbers in the Computer Propagation of Errors Calculation Errors in Systems of Linear Equations 18.2 Nonlinear Equations Calculation of Fixed Points Calculation of Zeros 18.3 Splines Cubic Splines Parametric Splines 18.4 Numerical Integration 18.5 Numerical Solution of Differential Equations 18.6 Comprehension Questions and Exercises Anchor 16 Part III Probability and Statistics 19 Probability Spaces Abstract 19.1 Problems in Statistics and Probability Theory The Election Poll Quality Checking Determining Estimates Testing a Hypothesis Random Events Over Time Probabilistic Algorithms Monte Carlo Methods Distributions 19.2 The Concept of Probability Random Events Probability Spaces Uniform Probability on Finite Spaces Geometric Probabilities 19.3 Conditional Probability and Independent Events Independent Events 19.4 Bernoulli Processes and Urn Problems 19.5 Urn Problems 19.6 Comprehension Questions and Exercises Anchor 22 20 Random Variables Abstract 20.1 Random Variables and Probabilty Distributions Discrete Random Variable Continuous Random Variables Sets of Random Variables Independent Random Variables 20.2 Expected Value and Variance of Random Variables Sums and Products of Random Variables A Short Excursion into Information Theory 20.3 Comprehension Questions and Exercises Anchor 12 21 Important Distributions, Stochastic Processes Abstract 21.1 Discrete Probability Distributions The Discrete Uniform Distribution The Binomial Distribution The Hypergeometric Distribution The Geometric Distribution The Poisson Distribution 21.2 Continuous Probability Distributions, The Normal Distribution The Continuos Uniform Distribution The Standard Normal Distribution The General Normal Distribution The Exponential Distribution The Chi-Square Distribution 21.3 Stochastic Processes The Poisson Process Markov Chains Queues 21.4 Comprehension Questions and Exercises Anchor 20 22 Statistical Methods Abstract 22.1 Parameter Estimation Samples Estimators Estimator for the Probability in a Bernoulli Process Estimators for the Expected Value and Variance of a Random Variable 22.2 Principal Component Analysis 22.3 Confidence Intervals 22.4 Hypothesis Testing Parameter Testing Pearson’s Chi-Squared Test 22.5 Comprehension Questions and Exercises Anchor 14 23 Appendix 23.1 The Greek Alphabet 23.2 The Standard Normal Distribution Bibliography