This clearly written and enlightening textbook provides a concise, introductory guide to the key mathematical concepts and techniques used by computer scientists. Topics and features: ideal for self-study, offering many pedagogical features such as chapter-opening key topics, chapter introductions and summaries, review questions, and a glossary; places our current state of knowledge within the context of the contributions made by early civilizations, such as the ancient Babylonians, Egyptians and Greeks; examines the building blocks of mathematics, including sets, relations and functions; presents an introduction to logic, formal methods and software engineering; explains the fundamentals of number theory, and its application in cryptography; describes the basics of coding theory, language theory, and graph theory; discusses the concept of computability and decideability; includes concise coverage of calculus, probability and statistics, matrices, complex numbers and quaternions.
Author(s): Gerard O’Regan
Edition: 1
Publisher: Springer
Year: 2012
Language: English
Pages: 308
City: London
Tags: Calculus; Coding Theory; Cryptography; Discrete Mathematics; Formal Methods; Graph Theory; Group Theory; Ring Theory; Mathematics History; Matrix Theory; Number Theory; Probability; Statistics; Software Engineering; Software Reliability; Z Specification Language; Sets; Functions; Logic
Preface
Overview
Organization and Features
Audience
Acknowledgments
Contents
List of Figures
Chapter
1 Mathematics in Civilization
1.1 Introduction
1.2 The Babylonians
1.3 The Egyptians
1.4 The Greeks
1.5 The Romans
1.6 Islamic Influence
1.7 Chinese and Indian Mathematics
1.9 Review Questions
1.9 Summary
Chapter 2 Sets, Relations and Functions
2.1 Introduction
2.2 Set Theory
2.2.1 Set Theoretical Operations
2.2.2 Properties of Set Theoretical Operations
2.2.3 Russell's Paradox
2.3 Relations
2.3.1 Reflexive, Symmetric and Transitive Relations
2.3.2 Composition of Relations
2.3.3 Binary Relations
2.4 Functions
2.5 Review Questions
2.6 Summary
Chapter 3 Logic
3.1 Introduction
3.2 Propositional Logic
3.2.1 Truth Tables
3.2.2 Properties of Propositional Calculus
3.2.3 Proof in Propositional Calculus
3.2.4 Applications of Propositional Calculus
3.2.5 Limitations of Propositional Calculus
3.3 Predicate Calculus
3.3.1 Formalisation of Predicate Calculus
3.3.2 Interpretation and Valuation Functions
3.3.3 Properties of Predicate Calculus
3.3.4 Applications of Predicate Calculus
3.4 Undefined Values
3.4.1 Logic of Partial Functions
3.4.2 Parnas Logic
3.4.3 Dijkstra and Undefinedness
3.5 Other Logics
3.6 Tools for Logic
3.7 Review Questions
3.8 Summary
Chapter 4 Software Engineering
4.1 Introduction
4.2 What is Software Engineering?
4.3 Early Software Engineering
4.4 Software Engineering Mathematics
4.5 Formal Methods
4.6 Software Inspections and Testing
4.7 Process Maturity Models
4.8 Review Questions
4.9 Summary
Chapter 5 Formal Methods
5.1 Introduction
5.2 Why Should We Use Formal Methods?
5.3 Applications of Formal Methods
5.4 Tools for Formal Methods
5.5 Approaches to Formal Methods
5.5.1 Model-Oriented Approach
5.5.2 Axiomatic Approach
5.6 Proof and Formal Methods
5.7 The Future of Formal Methods
5.8 The Vienna Development Method
5.9 VDM, the Irish School of Vienna Development Method (VDM)
5.10 The Z Specification Language
5.11 The B-Method
5.12 Predicate Transformers and Weakest Pre-Conditions
5.13 The Process Calculi
5.14 Finite State Machines
5.15 The Parnas Way
5.16 Usability of Formal Methods
5.16.1 Why Are Formal Methods Difficult?
5.16.2 Characteristics of a Usable Formal Method
5.17 Review Questions
5.18 Summary
Chapter 6 Z Formal Specification Language
6.1 Introduction
6.2 Sets
6.3 Relations
6.4 Functions
6.5 Sequences
6.6 Bags
6.7 Schemas and Schema Composition
6.8 Reification and Decomposition
6.9 Proof in Z
6.10 Review Questions
6.11 Summary
Chapter 7 Number Theory
7.1 Introduction
7.2 Elementary Number Theory
7.3 Prime Number Theory
7.3.1 Greatest Common Divisors (GCD)
7.3.2 Least Common Multiple (LCM)
7.3.3 Euclid's Algorithm
7.3.4 Distribution of Primes
7.4 Theory of Congruences
7.5 Review Questions
7.6 Summary
Chapter 8 Cryptography
8.1 Introduction
8.2 Breaking the Enigma Codes
8.3 Cryptographic Systems
8.4 Symmetric Key Systems
8.5 Public Key Systems
8.5.1 RSA Public Key Cryptosystem
8.5.2 Digital Signatures
8.6 Review Questions
8.7 Summary
Chapter 9 Coding Theory
9.1 Introduction
9.2 Mathematical Foundations
9.2.1 Groups
9.2.2 Rings
9.2.3 Fields
9.2.4 Vector Spaces
9.3 Simple Channel Code
9.4 Block Codes
9.4.1 Error Detection and Correction
9.5 Linear Block Codes
9.5.1 Parity-Check Matrix
9.5.2 Binary Hamming Code
9.5.3 Binary Parity-Check Code
9.6 Miscellaneous Codes in Use
9.7 Review Questions
9.8 Summary
Chapter 10 Language Theory and Semantics
10.1 Introduction
10.2 Alphabets and Words
10.3 Grammars
10.3.1 Backus Naur Form
10.3.2 Parse Trees and Derivations
10.4 Programming Language Semantics
10.4.1 Axiomatic Semantics
10.4.2 Operational Semantics
10.4.3 Denotational Semantics
10.5 Lambda Calculus
10.6 Lattices and Order
10.6.1 Partially Ordered Sets
10.6.2 Lattices
10.6.3 Complete Partial Orders
10.6.4 Recursion
10.7 Review Questions
10.8 Summary
Chapter 11 Computability and Decidability
11.1 Introduction
11.2 Formalism
11.3 Decidability
11.4 Computability
11.5 Computational Complexity
11.6 Review Questions
11.7 Summary
Chapter 12 Probability, Statistics and Software Reliability
12.1 Introduction
12.2 Probability Theory
12.2.1 Laws of Probability
12.2.2 Random Variables
12.3 Statistics
12.3.1 Abuse of Statistics
12.3.2 Statistical Sampling
12.3.3 Averages in a Sample
12.3.4 Variance and Standard Deviation
12.3.5 Bell-shaped (Normal) Distribution
12.3.6 Frequency Tables, Histograms and Pie Charts
12.3.7 Hypothesis Testing
12.4 Software Reliability
12.4.1 Software Reliability and Defects
12.4.2 Cleanroom Methodology
12.4.3 Software Reliability Models
12.5 Review Questions
12.6 Summary
Chapter 13 Matrix Theory
13.1 Introduction
13.1.1 2 2Matrices
13.2 Matrix Operations
13.3 Determinants
13.4 Eigenvectors and Eigenvalues
13.5 Gaussian Elimination
13.6 Review Questions
13.7 Summary
Chapter 14 Complex Numbers and Quaternions
14.1 Introduction
14.2 Complex Numbers
14.3 Quaternions
14.3.1 Quaternion Algebra
14.3.2 Quaternions and Rotations
14.4 Review Questions
14.5 Summary
Chapter 15 Calculus
15.1 Introduction
15.2 Differentiation
15.2.1 Rules of Differentiation
15.3 Integration
15.3.1 Definite Integrals
15.3.2 Fundamental Theorems of Integral Calculus
15.4 Numerical Analysis
15.5 Fourier Series
15.6 The Laplace Transform
15.7 Differential Equations
15.8 Review Questions
15.9 Summary
Chapter 16 Graph Theory
16.1 Introduction
16.2 Undirected Graphs
16.2.1 Hamiltonian Paths
16.3 Trees
16.3.1 Binary Trees
16.4 Graph Algorithms
16.5 Review Questions
16.6 Summary
References
Glossary
Index
