2020 | Book

# Mathematics in Computing

## An Accessible Guide to Historical, Foundational and Application Contexts

Author: Dr. Gerard O’Regan

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

2020 | Book

Author: Dr. Gerard O’Regan

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

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.

Advertisement

Abstract

The first chapter introduces the computing field, where a computer is a programmable electronic device that can process, store and retrieve data. It processes data according to a set of instructions (or program), and all computers consist of two basic parts, namely, hardware and software. There are two distinct families of computing devices, namely, digital computers and the historical analog computer. These two types of computer operate on quite different principles, and the earliest computers were analog. We discuss the von Neumann architecture, which is the fundamental architecture underlying a digital computer.

Abstract

This chapter discusses the foundations of computing, including the binary number system and the step reckoner calculating machine, which were invented by Leibniz. The difference engine was designed by Babbage to evaluate polynomials and to produce accurate mathematical tables. Babbage’s design of the analytic engine provided the vision of a modern computer, and he envisaged that it would be analogous to the operation of the Jacquard loom, which is designed to weave (i.e. execute on the loom) a design pattern represented by a set of cards. Boole’s symbolic logic provides the foundation for digital computing.

Abstract

This chapter provides an introduction to fundamental building blocks in mathematics including sets, relations and functions. A set is a collection of well-defined objects, and it may be finite or infinite. A relation between two sets A and B indicates a relationship between members of the two sets and is a subset of the Cartesian product of the two sets. A function is a special type of relation such that for each element in A there is at most one element in the co-domain B. Functions may be partial or total and injective, surjective or bijective.

Abstract

This chapter presents a short introduction to algorithms, where an algorithm is a well-defined procedure for solving a problem. It consists of a sequence of steps that takes a set of values as input and produces a set of values as output. An algorithm is an exact specification of how to solve the problem, and it may be implemented by a computer program written in some programming language.

Abstract

This chapter presents the fundamentals of number theory, where number theory is the branch of mathematics that is concerned with the mathematical properties of the natural numbers and integers. We discuss prime number theory where prime numbers are fundamental in arithmetic where every integer can be factored as a product of primes. Euclid’s algorithm may be employed to determine the greatest common divisor of two numbers. There are many applications of number theory including the field of cryptography.

Abstract

This chapter discusses algebra, and we discuss simple and simultaneous equations, including the method of elimination and the method of substitution to solve simultaneous equations. We show how quadratic equations may be solved by factorization, completing the square or using the quadratic formula. We present the laws of logarithms and indices. We discuss several structures used in abstract algebra, including monoids, groups, rings, integral domains, fields and vector spaces.

Abstract

This chapter discusses sequences, series and permutations and combinations. Arithmetic and geometric sequences and series are discussed, and we discuss applications of geometric sequences and series to the calculation of compound interest and annuities.

Abstract

This chapter discusses mathematical induction and recursion. Induction is a common proof technique in mathematics, and there are two parts to a proof by induction (the base case and the inductive step). We discuss strong and weak induction, and we discuss how recursion is used to define sets, sequences and functions. This leads us to structural induction, which is used to prove properties of recursively defined structures.

Abstract

This chapter discusses graph theory where a graph G = (V, E) consists of vertices and edges. It is a practical branch of mathematics that deals with the arrangement of vertices and edges between them, and it has been applied to practical problems such as the modelling of computer networks, determining the shortest driving route between two cities and the travelling salesman problem.

Abstract

This chapter discusses cryptography, which is an important application of number theory. The codebreaking work done at Bletchley Park in England during the Second World War is discussed, and the fundamentals of cryptography, including private and public-key cryptosystems, are discussed.

Abstract

This chapter presents coding theory and is concerned with error detection and error correction codes. The underlying mathematics includes abstract mathematics such as group theory, rings, fields and vector spaces.

Abstract

This chapter discusses language theory and includes a discussion on grammar, parse trees and derivations from grammar. The important area of programming language semantics is discussed, including axiomatic, denotational and operational semantics.

Abstract

This chapter discusses computability and decidability. The Church–Turing thesis states that anything that is computable is computable by a Turing machine. Church and Turing showed that mathematics is not decidable. In other words, there is no mechanical procedure (i.e. algorithm) to determine whether an arbitrary mathematical proposition is true or false, and so the only way to determine the truth or falsity of a statement is trying to solve the problem.

Abstract

This chapter discusses matrices including 2 × 2 and general n × m matrices. Various operations such as the addition and multiplication of matrices are considered, and the determinant and inverse of a square matrix are discussed. The application of matrices to solving a set of linear equations using Gaussian elimination is considered.

Abstract

This chapter presents a short history of logic, and we discuss Greek contributions to syllogistic logic, stoic logic, fallacies and paradoxes. Boole’s symbolic logic and its application to digital computing are discussed, and we consider Frege’s work on predicate logic.

Abstract

This chapter provides an introduction to propositional and predicate logic. Propositional logic may be used to encode simple arguments that are expressed in natural language, and to determine their validity. The nature of mathematical proof is discussed, and we present proof by truth tables, semantic tableaux and natural deduction. Predicate logic allows complex facts about the world to be represented, and new facts may be determined via deductive reasoning. Predicate calculus includes predicates, variables and quantifiers, and a predicate is a characteristic or property that the subject of a statement can have.

Abstract

This chapter presents some advanced topics in logic including fuzzy logic, temporal logic, intuitionistic logic, undefined values, theorem provers and the applications of logic to AI. Fuzzy logic is an extension of classical logic that acts as a mathematical model for vagueness. Temporal logic is concerned with the expression of properties that have time dependencies, and it allows temporal properties about the past, present and future to be expressed. Intuitionism was a controversial theory on the foundations of mathematics based on a rejection of the law of the excluded middle, and an insistence on constructive existence. We discuss three approaches to deal with undefined values, including the logic of partial functions; Dijkstra’s approach with his cand and cor operators and Parnas’s approach which preserves a classical two-valued logic.

Abstract

This chapter discusses the nature of proof and theorem proving, and we discuss automated and interactive theorem provers. We discuss the nature of rigorous mathematical proof and formal mathematical proof.

Abstract

Chapter 19 discusses software engineering and the mathematics to support software engineering. We discuss traditional software engineering including the activities in the waterfall lifecycle model. We discuss early mathematical work in software engineering including Floyd’s work on assertions which influenced C. A. R. Hoare.

Abstract

This chapter discusses introduction to the important area of software reliability and dependability, and it discusses important topics in software engineering such as software reliability; software availability; software reliability models; the cleanroom methodology; dependability and its various dimensions; security engineering; and safety-critical systems.

Abstract

This chapter discusses formal methods, which consist of a set of mathematical techniques to rigorously specify and derive a program from its specification. Formal methods may be employed to rigorously state the requirements of the proposed system; they may be employed to derive a program from its mathematical specification; and they may provide a rigorous proof that the implemented program satisfies its specification. They have been mainly applied to the safety-critical field.

Abstract

This chapter presents the Z specification language, which is one of the most widely used formal methods. Z is a formal specification language based on Zermelo set theory. It was developed at the Programming Research Group at Oxford University in the early 1980s. Z specifications are mathematical and employ a classical two-valued logic. The use of mathematics ensures precision and allows inconsistencies and gaps in the specification to be identified. Theorem provers may be employed to demonstrate that the software implementation meets its specification.

Abstract

This chapter discusses automata theory, including finite-state machines, pushdown automata and Turing machines. Finite-state machines are abstract machines that are in only one state at a time, and the input symbol causes a transition from the current state to the next state. Pushdown automata have greater computational power, and they contain extra memory in the form of a stack from which symbols may be pushed or popped. The Turing machine is the most powerful model for computation, and this theoretical machine is equivalent to an actual computer in the sense that it can compute exactly the same set of functions.

Abstract

This chapter discusses model checking, which is an automated technique such that given a finite-state model of a system and a formal property, then it systematically checks whether the property is true or false in a given state in the model. It is an effective technique to identify potential design errors, and it increases the confidence in the correctness of the system design.

Abstract

This chapter discusses probability and statistics and includes a discussion on discrete and continuous random variables; probability distributions; sample spaces; sampling; the abuse of statistics; variance and standard deviation; and hypothesis testing.

Abstract

This chapter discusses complex numbers and quaternions. Complex numbers are of the form a + bi where a and b are real numbers, and i^{2} = −1. Quaternions are a generalization of complex numbers to quadruples that satisfy the quaternion formula i^{2} = j^{2} = k^{2} = −1.

Abstract

This chapter provides a very short introduction to calculus and provides a high-level overview of limits, continuity, differentiation, integration, numerical analysis, Fourier series, Laplace transforms and differential equations.

Abstract

This chapter is the concluding chapter in which we summarize the journey that we have travelled in this book.