Mathematics in computing : an accessible guide to historical, foundational and application contexts

Cover......Page 1
Organization and Features......Page 6
Acknowledgements......Page 8
Contents......Page 9
List of Figures......Page 15
1.1 Introduction......Page 18
1.2 The Babylonians......Page 20
1.3 The Egyptians......Page 23
1.4 The Greeks......Page 25
1.5 The Romans......Page 33
1.6 Islamic Influence......Page 36
1.7 Chinese and Indian Mathematics......Page 37
1.9 Summary......Page 38
2.1 Introduction......Page 40
2.2 Set Theory......Page 41
2.2.1 Set Theoretical Operations......Page 43
2.2.2 Properties of Set Theoretical Operations......Page 45
2.2.3 Russell's Paradox......Page 46
2.3 Relations......Page 47
2.3.1 Reflexive, Symmetric and Transitive Relations......Page 49
2.3.2 Composition of Relations......Page 51
2.3.3 Binary Relations......Page 52
2.4 Functions......Page 53
2.5 Review Questions......Page 57
2.6 Summary......Page 58
3.1 Introduction......Page 59
3.2 Propositional Logic......Page 61
3.2.1 Truth Tables......Page 63
3.2.2 Properties of Propositional Calculus......Page 65
3.2.3 Proof in Propositional Calculus......Page 66
3.2.4 Applications of Propositional Calculus......Page 70
3.3 Predicate Calculus......Page 71
3.3.1 Formalisation of Predicate Calculus......Page 74
3.3.2 Interpretation and Valuation Functions......Page 75
3.3.4 Applications of Predicate Calculus......Page 76
3.4 Undefined Values......Page 77
3.4.1 Logic of Partial Functions......Page 78
3.4.2 Parnas Logic......Page 79
3.4.3 Dijkstra and Undefinedness......Page 81
3.5 Other Logics......Page 82
3.6 Tools for Logic......Page 84
3.8 Summary......Page 85
4.1 Introduction......Page 87
4.2 What is Software Engineering?......Page 89
4.3 Early Software Engineering......Page 94
4.4 Software Engineering Mathematics......Page 97
4.5 Formal Methods......Page 98
4.6 Software Inspections and Testing......Page 99
4.7 Process Maturity Models......Page 101
4.9 Summary......Page 102
5.1 Introduction......Page 104
5.2 Why Should We Use Formal Methods?......Page 106
5.3 Applications of Formal Methods......Page 107
5.4 Tools for Formal Methods......Page 108
5.5.1 Model-Oriented Approach......Page 109
5.6 Proof and Formal Methods......Page 110
5.7 The Future of Formal Methods......Page 111
5.8 The Vienna Development Method......Page 112
5.9 VDM, the Irish School of Vienna Development Method (VDM)......Page 113
5.10 The Z Specification Language......Page 114
5.11 The B-Method......Page 115
5.12 Predicate Transformers and Weakest Pre-Conditions......Page 116
5.13 The Process Calculi......Page 117
5.14 Finite State Machines......Page 118
5.15 The Parnas Way......Page 119
5.16.1 Why Are Formal Methods Difficult?......Page 120
5.16.2 Characteristics of a Usable Formal Method......Page 121
5.18 Summary......Page 122
6.1 Introduction......Page 124
6.2 Sets......Page 126
6.3 Relations......Page 127
6.4 Functions......Page 129
6.5 Sequences......Page 130
6.6 Bags......Page 131
6.7 Schemas and Schema Composition......Page 132
6.8 Reification and Decomposition......Page 135
6.10 Review Questions......Page 136
6.11 Summary......Page 137
7.1 Introduction......Page 138
7.2 Elementary Number Theory......Page 140
7.3 Prime Number Theory......Page 144
7.3.1 Greatest Common Divisors (GCD)......Page 146
7.3.3 Euclid's Algorithm......Page 147
7.3.4 Distribution of Primes......Page 149
7.4 Theory of Congruences......Page 152
7.6 Summary......Page 155
8.1 Introduction......Page 156
8.2 Breaking the Enigma Codes......Page 158
8.3 Cryptographic Systems......Page 160
8.4 Symmetric Key Systems......Page 161
8.5 Public Key Systems......Page 165
8.5.1 RSA Public Key Cryptosystem......Page 167
8.5.2 Digital Signatures......Page 168
8.7 Summary......Page 169
9.1 Introduction......Page 170
9.2.1 Groups......Page 171
9.2.2 Rings......Page 172
9.2.3 Fields......Page 173
9.2.4 Vector Spaces......Page 174
9.3 Simple Channel Code......Page 176
9.4 Block Codes......Page 177
9.4.1 Error Detection and Correction......Page 178
9.5 Linear Block Codes......Page 179
9.5.1 Parity-Check Matrix......Page 181
9.5.2 Binary Hamming Code......Page 182
9.6 Miscellaneous Codes in Use......Page 183
9.8 Summary......Page 184
10.1 Introduction......Page 185
10.2 Alphabets and Words......Page 186
10.3 Grammars......Page 187
10.3.1 Backus Naur Form......Page 188
10.3.2 Parse Trees and Derivations......Page 190
10.4 Programming Language Semantics......Page 192
10.4.1 Axiomatic Semantics......Page 193
10.4.2 Operational Semantics......Page 194
10.4.3 Denotational Semantics......Page 195
10.5 Lambda Calculus......Page 196
10.6.1 Partially Ordered Sets......Page 198
10.6.3 Complete Partial Orders......Page 200
10.6.4 Recursion......Page 201
10.8 Summary......Page 203
11.1 Introduction......Page 204
11.2 Formalism......Page 205
11.3 Decidability......Page 207
11.4 Computability......Page 209
11.6 Review Questions......Page 212
11.7 Summary......Page 213
12.1 Introduction......Page 214
12.2 Probability Theory......Page 215
12.2.1 Laws of Probability......Page 216
12.2.2 Random Variables......Page 217
12.3.2 Statistical Sampling......Page 220
12.3.3 Averages in a Sample......Page 221
12.3.4 Variance and Standard Deviation......Page 222
12.3.5 Bell-shaped (Normal) Distribution......Page 223
12.3.6 Frequency Tables, Histograms and Pie Charts......Page 225
12.3.7 Hypothesis Testing......Page 226
12.4 Software Reliability......Page 227
12.4.1 Software Reliability and Defects......Page 228
12.4.2 Cleanroom Methodology......Page 230
12.4.3 Software Reliability Models......Page 231
12.6 Summary......Page 233
13.1 Introduction......Page 235
13.1.1 2 2Matrices......Page 236
13.2 Matrix Operations......Page 239
13.3 Determinants......Page 240
13.4 Eigenvectors and Eigenvalues......Page 242
13.5 Gaussian Elimination......Page 243
13.6 Review Questions......Page 244
13.7 Summary......Page 245
14.1 Introduction......Page 246
14.2 Complex Numbers......Page 247
14.3 Quaternions......Page 251
14.3.1 Quaternion Algebra......Page 253
14.3.2 Quaternions and Rotations......Page 256
14.5 Summary......Page 257
15.1 Introduction......Page 258
15.2 Differentiation......Page 261
15.2.1 Rules of Differentiation......Page 263
15.3 Integration......Page 265
15.3.1 Definite Integrals......Page 266
15.3.2 Fundamental Theorems of Integral Calculus......Page 268
15.4 Numerical Analysis......Page 269
15.5 Fourier Series......Page 272
15.6 The Laplace Transform......Page 273
15.7 Differential Equations......Page 274
15.9 Summary......Page 275
16.1 Introduction......Page 277
16.2 Undirected Graphs......Page 278
16.2.1 Hamiltonian Paths......Page 282
16.3.1 Binary Trees......Page 283
16.6 Summary......Page 284
References......Page 285
References......Page 286
Glossary......Page 289
Index......Page 291