This illuminating textbook provides a concise review of the core concepts in mathematics essential to computer scientists. Emphasis is placed on the practical computing applications enabled by seemingly abstract mathematical ideas, presented within their historical context. The text spans a broad selection of key topics, ranging from the use of finite field theory to correct code and the role of number theory in cryptography, to the value of graph theory when modelling networks and the importance of formal methods for safety critical systems. This fully updated new edition has been expanded with a more comprehensive treatment of algorithms, logic, automata theory, model checking, software reliability and dependability, algebra, sequences and series, and mathematical induction. Topics and features: includes numerous pedagogical features, such as chapter-opening key topics, chapter introductions and summaries, review questions, and a glossary; describes the historical contributions of such prominent figures as Leibniz, Babbage, Boole, and von Neumann; introduces the fundamental mathematical concepts of sets, relations and functions, along with the basics of number theory, algebra, algorithms, and matrices; explores arithmetic and geometric sequences and series, mathematical induction and recursion, graph theory, computability and decidability, and automata theory; reviews the core issues of coding theory, language theory, software engineering, and software reliability, as well as formal methods and model checking; covers key topics on logic, from ancient Greek contributions to modern applications in AI, and discusses the nature of mathematical proof and theorem proving; presents a short introduction to probability and statistics, complex numbers and quaternions, and calculus. This engaging and easy-to-understand book will appeal to students of computer science wishing for an overview of the mathematics used in computing, and to mathematicians curious about how their subject is applied in the field of computer science. The book will also capture the interest of the motivated general reader.
Author(s): Gerard O’Regan
Series: Undergraduate Topics In Computer Science
Edition: 2nd Edition
Publisher: Springer
Year: 2020
Language: English
Pages: 468
Tags: Mathematical Applications In Computer Science
Organization and Features......Page 7
Audience......Page 10
Acknowledgements......Page 11
Contents......Page 12
List of Figures......Page 21
1.1 Introduction......Page 25
1.2 Analog Computers......Page 26
1.3.1 Vacuum Tubes......Page 28
1.3.3 Integrated Circuits......Page 29
1.3.4 Microprocessors......Page 31
1.4 von Neumann Architecture......Page 32
1.5 Hardware and Software......Page 33
1.7 Summary......Page 34
References......Page 35
2.1 Introduction......Page 36
2.2 Step Reckoner Calculating Machine......Page 37
2.3 Binary Numbers......Page 38
2.4 The Difference Engine......Page 40
2.5 The Analytic Engine—Vision of a Computer......Page 42
2.5.1 Applications of Analytic Engine......Page 44
2.6 Boole’s Symbolic Logic......Page 45
2.6.1 Switching Circuits and Boolean Algebra......Page 48
2.7 Application of Symbolic Logic to Digital Computing......Page 50
2.9 Summary......Page 51
References......Page 52
3.1 Introduction......Page 53
3.2 Set Theory......Page 54
3.2.1 Set-Theoretical Operations......Page 57
3.2.2 Properties of Set-Theoretical Operations......Page 59
3.2.3 Russell’s Paradox......Page 60
3.2.4 Computer Representation of Sets......Page 62
3.3 Relations......Page 63
3.3.1 Reflexive, Symmetric and Transitive Relations......Page 64
3.3.2 Composition of Relations......Page 66
3.3.3 Binary Relations......Page 68
3.3.4 Applications of Relations to Databases......Page 69
3.4 Functions......Page 71
3.5 Application of Functions to Functional Programming......Page 75
3.5.1 Miranda......Page 76
3.6 Number Theory......Page 78
3.7 Automata Theory......Page 79
3.9 Computability and Decidability......Page 80
3.10 Review Questions......Page 81
References......Page 82
4.1 Introduction......Page 83
4.2 Early Algorithms......Page 84
4.2.2 Euclid’s Greatest Common Divisor Algorithm......Page 85
4.2.3 Sieve of Eratosthenes Algorithm......Page 87
4.2.4 Early Cipher Algorithms......Page 88
4.3 Sorting Algorithms......Page 90
4.4 Binary Trees and Graph Theory......Page 93
4.5 Modern Cryptographic Algorithms......Page 94
4.6 Computational Complexity......Page 95
4.8 Summary......Page 96
References......Page 97
5.1 Introduction......Page 98
5.2 Elementary Number Theory......Page 100
5.3 Prime Number Theory......Page 105
5.3.1 Greatest Common Divisors (GCD)......Page 107
5.3.2 Least Common Multiple (LCM)......Page 108
5.3.3 Euclid’s Algorithm......Page 109
5.3.4 Distribution of Primes......Page 110
5.4 Theory of Congruences......Page 113
5.5 Binary System and Computer Representation of Numbers......Page 116
5.6 Review Questions......Page 117
5.7 Summary......Page 118
References......Page 119
6.1 Introduction......Page 120
6.2 Simple and Simultaneous Equations......Page 121
6.3 Quadratic Equations......Page 124
6.4 Indices and Logarithms......Page 127
6.5 Horner’s Method for Polynomials......Page 128
6.6.1 Monoids and Groups......Page 129
6.6.2 Rings......Page 131
6.6.3 Fields......Page 132
6.6.4 Vector Spaces......Page 133
6.8 Summary......Page 135
7.1 Introduction......Page 137
7.2 Sequences and Series......Page 138
7.3 Arithmetic and Geometric Sequences......Page 139
7.4 Arithmetic and Geometric Series......Page 140
7.5 Simple and Compound Interest......Page 141
7.6 Time Value of Money and Annuities......Page 143
7.7 Permutations and Combinations......Page 144
7.8 Review Questions......Page 148
7.9 Summary......Page 149
8.1 Introduction......Page 151
8.2 Strong Induction......Page 154
8.3 Recursion......Page 156
8.4 Structural Induction......Page 158
8.6 Summary......Page 159
Reference......Page 160
9.1 Introduction......Page 161
9.2 Undirected Graphs......Page 163
9.2.1 Hamiltonian Paths......Page 167
9.3 Trees......Page 168
9.3.1 Binary Trees......Page 169
9.5 Graph Colouring and Four-Colour Problem......Page 170
9.7 Summary......Page 172
Reference......Page 173
10.1 Introduction......Page 174
10.2 Breaking the Enigma Codes......Page 176
10.3 Cryptographic Systems......Page 179
10.4 Symmetric-Key Systems......Page 180
10.5 Public-Key Systems......Page 185
10.5.1 RSA Public-Key Cryptosystem......Page 187
10.6 Review Questions......Page 188
References......Page 189
11.1 Introduction......Page 190
11.2 Mathematical Foundations......Page 191
11.3 Simple Channel Code......Page 192
11.4 Block Codes......Page 193
11.4.1 Error Detection and Correction......Page 195
11.5 Linear Block Codes......Page 196
11.5.2 Binary Hamming Code......Page 199
11.7 Review Questions......Page 201
References......Page 202
12.1 Introduction......Page 203
12.2 Alphabets and Words......Page 204
12.3 Grammars......Page 205
12.3.1 Backus–Naur Form......Page 208
12.3.2 Parse Trees and Derivations......Page 209
12.4.1 Axiomatic Semantics......Page 211
12.4.2 Operational Semantics......Page 213
12.4.3 Denotational Semantics......Page 214
12.5 Lambda Calculus......Page 215
12.6.1 Partially Ordered Sets......Page 217
12.6.2 Lattices......Page 219
12.6.3 Complete Partial Orders......Page 221
12.6.4 Recursion......Page 222
References......Page 224
13.1 Introduction......Page 226
13.2 Logicism and Formalism......Page 227
13.3 Decidability......Page 230
13.4 Computability......Page 232
13.5 Computational Complexity......Page 235
13.7 Summary......Page 236
Reference......Page 237
14.1 Introduction......Page 238
14.2 Two × Two Matrices......Page 240
14.3 Matrix Operations......Page 242
14.4 Determinants......Page 245
14.6 Gaussian Elimination......Page 247
14.8 Summary......Page 249
Reference......Page 250
15.1 Introduction......Page 251
15.2 Syllogistic Logic......Page 252
15.3 Paradoxes and Fallacies......Page 254
15.4 Stoic Logic......Page 256
15.5 Boole’s Symbolic Logic......Page 257
15.5.1 Switching Circuits and Boolean Algebra......Page 258
15.6 Frege......Page 259
15.7 Review Questions......Page 260
References......Page 261
16.1 Introduction......Page 262
16.2 Propositional Logic......Page 263
16.2.1 Truth Tables......Page 265
16.2.2 Properties of Propositional Calculus......Page 267
16.2.3 Proof in Propositional Calculus......Page 268
16.2.4 Semantic Tableaux in Propositional Logic......Page 271
16.2.5 Natural Deduction......Page 273
16.2.6 Sketch of Formalization of Propositional Calculus......Page 274
16.2.7 Applications of Propositional Calculus......Page 276
16.2.8 Limitations of Propositional Calculus......Page 277
16.3 Predicate Calculus......Page 278
16.3.1 Sketch of Formalization of Predicate Calculus......Page 280
16.3.2 Interpretation and Valuation Functions......Page 282
16.3.4 Applications of Predicate Calculus......Page 283
16.3.5 Semantic Tableaux in Predicate Calculus......Page 284
16.4 Review Questions......Page 286
16.5 Summary......Page 287
References......Page 288
17.1 Introduction......Page 289
17.2 Fuzzy Logic......Page 290
17.3 Temporal Logic......Page 291
17.4 Intuitionistic Logic......Page 293
17.5.1 Logic of Partial Functions......Page 295
17.5.2 Parnas Logic......Page 297
17.5.3 Dijkstra and Undefinedness......Page 298
17.6 Logic and AI......Page 300
17.8 Summary......Page 304
References......Page 305
18.1 Introduction......Page 306
18.2 Early Automation of Proof......Page 309
18.3 Interactive Theorem Provers......Page 311
18.6 Summary......Page 313
References......Page 315
19.1 Introduction......Page 316
19.2 What Is Software Engineering?......Page 319
19.3 Early Software Engineering Mathematics......Page 324
19.4 Mathematics in Software Engineering......Page 327
19.5 Software Inspections and Testing......Page 328
19.6 Process Maturity Models......Page 329
19.8 Summary......Page 330
References......Page 331
20.1 Introduction......Page 332
20.2 Software Reliability......Page 333
20.2.1 Software Reliability and Defects......Page 334
20.2.2 Cleanroom Methodology......Page 336
20.2.3 Software Reliability Models......Page 337
20.3 Dependability......Page 340
20.4 Computer Security......Page 342
20.6 Safety-Critical Systems......Page 343
20.8 Summary......Page 344
References......Page 345
21.1 Introduction......Page 346
21.2 Why Should We Use Formal Methods?......Page 348
21.3 Industrial Applications of Formal Methods......Page 350
21.4 Industrial Tools for Formal Methods......Page 351
21.5.1 Model-Oriented Approach......Page 352
21.6 Proof and Formal Methods......Page 354
21.7 Mathematics in Software Engineering......Page 355
21.8 The Vienna Development Method......Page 356
21.9 VDM♣, the Irish School of VDM......Page 357
21.10 The Z Specification Language......Page 358
21.11 The B-Method......Page 359
21.12 Predicate Transformers and Weakest Preconditions......Page 360
21.13 The Process Calculi......Page 361
21.14 Finite-State Machines......Page 362
21.16 Model Checking......Page 363
21.17 Usability of Formal Methods......Page 364
21.18 Review Questions......Page 365
21.19 Summary......Page 366
References......Page 367
22.1 Introduction......Page 368
22.2 Sets......Page 371
22.3 Relations......Page 372
22.4 Functions......Page 374
22.5 Sequences......Page 375
22.6 Bags......Page 376
22.7 Schemas and Schema Composition......Page 377
22.8 Reification and Decomposition......Page 380
22.9 Proof in Z......Page 381
22.10 Industrial Applications of Z......Page 382
22.12 Summary......Page 383
Reference......Page 384
23.1 Introduction......Page 385
23.2 Finite-State Machines......Page 386
23.3 Pushdown Automata......Page 389
23.4 Turing Machines......Page 391
23.5 Review Questions......Page 393
Reference......Page 394
24.1 Introduction......Page 395
24.2 Modelling Concurrent Systems......Page 399
24.3 Linear Temporal Logic......Page 400
24.4 Computational Tree Logic......Page 401
24.6 Industrial Applications of Model Checking......Page 402
24.8 Summary......Page 403
References......Page 404
25.1 Introduction......Page 405
25.2 Probability Theory......Page 406
25.2.1 Laws of Probability......Page 407
25.2.2 Random Variables......Page 408
25.3.1 Abuse of Statistics......Page 412
25.3.2 Statistical Sampling......Page 413
25.3.3 Averages in a Sample......Page 414
25.3.5 Bell-Shaped (Normal) Distribution......Page 415
25.3.6 Frequency Tables, Histograms and Pie Charts......Page 418
25.3.7 Hypothesis Testing......Page 419
25.5 Summary......Page 421
Reference......Page 422
26.1 Introduction......Page 423
26.2 Complex Numbers......Page 424
26.3 Quaternions......Page 429
26.3.1 Quaternion Algebra......Page 430
26.3.2 Quaternions and Rotations......Page 434
26.4 Review Questions......Page 435
26.5 Summary......Page 436
27.1 Introduction......Page 437
27.2 Differentiation......Page 441
27.2.1 Rules of Differentiation......Page 443
27.3 Integration......Page 444
27.3.1 Definite Integrals......Page 446
27.4 Numerical Analysis......Page 449
27.5 Fourier Series......Page 451
27.6 The Laplace Transform......Page 453
27.7 Differential Equations......Page 454
27.8 Review Questions......Page 455
Reference......Page 456
28 Epilogue......Page 457
Glossary......Page 461
Bibliography......Page 464
Index......Page 465
