nach oben

2020 | Buch

Kapitel lesen Erstes Kapitel lesen

The Discrete Math Workbook

A Companion Manual Using Python

verfasst von: Prof. Dr. Sergei Kurgalin, Dr. Sergei Borzunov

Verlag: Springer International Publishing

Buchreihe : Texts in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This practically-focused study guide introduces the fundamentals of discrete mathematics through an extensive set of classroom-tested problems. Each chapter presents a concise introduction to the relevant theory, followed by a detailed account of common challenges and methods for overcoming these. The reader is then encouraged to practice solving such problems for themselves, by tackling a varied selection of questions and assignments of different levels of complexity.

This updated second edition now covers the design and analysis of algorithms using Python, and features more than 50 new problems, complete with solutions.

Topics and features: provides a substantial collection of problems and examples of varying levels of difficulty, suitable for both laboratory practical training and self-study; offers detailed solutions to each problem, applying commonly-used methods and computational schemes; introduces the fundamentals of mathematical logic, the theory of algorithms, Boolean algebra, graph theory, sets, relations, functions, and combinatorics; presents more advanced material on the design and analysis of algorithms, including Turing machines, asymptotic analysis, and parallel algorithms; includes reference lists of trigonometric and finite summation formulae in an appendix, together with basic rules for differential and integral calculus.

This hands-on workbook is an invaluable resource for undergraduate students of computer science, informatics, and electronic engineering. Suitable for use in a one- or two-semester course on discrete mathematics, the text emphasizes the skills required to develop and implement an algorithm in a specific programming language.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Fundamentals of Mathematical Logic

Abstract

The chapter gives an idea of mathematical logic, a science that studies mathematical proofs. Subjects of mathematical logic are mathematical proofs, methods, and means for their construction. The simplest division of mathematical logic is the propositional logic. Proposition is a statement that has a value of truth, i.e. it can be true or false. The respective values of truth will be denoted by T or F. Compound proposition can be built out of atomic propositions using logical operations and brackets. The most common logical operations are and (conjunction or logical multiplication), or (disjunction or logical addition), if ... then (logical consequence or implication, this operation is also denoted as “$\Rightarrow $”), and not (negation). Statements about properties of variable x are called predicates and are denoted by P(x), Q(x); ... Truth domain of a predicate is a collection of all x, for which the given predicate becomes a true proposition. The predicate properties are studied by predicate logic. For construction of compound logical expressions, we use quantifiers: $\forall $ (for all) is the universal quantifier and $\exists $ (exists) is the existential quantifier. Quantifier is a logical operation that, by predicate P(x), constructs a proposition that characterizes the truth domain of P(x). In this chapter, the main proof methods are described:

forward reasoning;

backward reasoning;

method “by contradiction”.

Examples are considered to illustrate a powerful method for proving the truth of statements with respect to all natural numbers, the method of mathematical induction.

Sergei Kurgalin, Sergei Borzunov

Chapter 2. Set Theory

Abstract

One of the fundamental concepts of mathematics is the notion of a set. A set is a collection of objects which we conceive as a whole [37, 75]. These objects are called elements of a set. The belonging of some element a to the set A can be denoted as follows: $a\in A$. This record reads as follows: “a is an element of the set A” or “element a belongs to the set A”. If a does not belong to A, then we write $a\notin A$. There are several ways to denote which elements belong to a set; the most common are the following: 1. enumerating the elements. The elements of the set A are enclosed in braces and separated by commas; 2. using the characteristic predicate.

Sergei Kurgalin, Sergei Borzunov

Chapter 3. Relations and Functions

Abstract

Binary relation between the elements of the sets A and B is the subset R of the direct product $A\times B$. It is said that R is the relation on A, if $A=B$. If R is some binary relation, then instead of notation $(x,y)\in R$ designation $x\;R\;y$ is often used. Let $A=\{x_1, x_2, \dots , x_n\}$, $B=\{y_1, y_2, \dots , y_m\}$. Logical matrix of the relation R on $A\times B$ is defined as matrix M of size $n\times m$, whose elements $M_{ij}=\text {T}$, if $(x_i,y_j)\in R$, and $M_{ij}=\text {F}$, if $(x_i,y_j)\notin R$. A binary relationship between elements of finite sets can be represented by a listing of ordered pairs, using suitable predicates, as well as in the form of a logical matrix or a directed graph (digraph, see chapter “Graphs”). If at least one of the sets A or B is not finite, the relation $R\subseteq A\times B$ can be specified with the help of predicates. In this chapter, the equivalence relations of partial and linear order are considered. An important special case of relations are functions. Function from a set A to a set B is a binary relation, for which each element from A is associated with the only element from the set B. An idea of the types of functions is given as

injection,

surjection, and

bijection.

The pigeonhole principle is formulated.

Sergei Kurgalin, Sergei Borzunov

Chapter 4. Combinatorics

Abstract

Combinatorics solves the problems of counting the number of various configurations (for example, permutations), formed by the elements of finite sets, on which various restrictions can be imposed [4]. The number of configurations formed by the elements of the set is counted in accordance with the sum rule and the product rule [4, 30]. The Newton’s binomial and polynomial expansion are considered.

Sergei Kurgalin, Sergei Borzunov

Chapter 5. Graphs

Abstract

Graph is a pair $G=\left( V,\;E\right) $, where V is a set of vertices (nodes) , and E is a set of edges (arcs) , connecting some pairs of vertices (nodes) [18, 31, 60, 89]. A graph is said to be simple if it contains no loops (edges beginning and ending at the same vertex) and multiple edges (several edges are called multiple if they connect the same pair of vertices), and the sets V and E are finite. The figure where the graph vertices are shown as points, and edges are shown as segments or arcs, is called a diagram of a graph.

Sergei Kurgalin, Sergei Borzunov

Chapter 6. Boolean Algebra

Abstract

Boolean is a set $\mathbb {B}=\{0,1\}$ with defined on it operations of disjunction ($\vee $), conjunction ($\wedge $), and negation ($\overline{\phantom {a}}$). Boolean variable p can take the values 0 or 1 (and only them), $p\in \mathbb {B}$. Boolean expression is formed by Boolean variables with the help of operations $\vee $, $\wedge $, $\overline{\phantom {a}}$ and brackets. The function $f:\mathbb {B}^n\rightarrow \mathbb {B}$, where $f(x_1,\dots ,x_n)$ is Boolean expression, is called Boolean function. The most important classes of Boolean functions are considered:

Functions that preserve constants 0 and 1.
Self-dual functions.
Linear functions.
Monotone functions.

Sergei Kurgalin, Sergei Borzunov

Chapter 7. Complex Numbers

Abstract

Complex number z is an ordered pair of real numbers (a, b), where $a,b\in \mathbb {R}$. The first number a is called the real part of the complex number $z=(a,b)$ and is denoted by symbol $\mathrm{Re}z$, while the second number of the pair b is called the imaginary part z and is denoted $\mathrm{Im}z$ [23]. A complex number of the form (a, 0), where the imaginary part is zero, is identified with the real number a, i. e. $(a,0)\equiv a$. This allows considering the set of all real numbers $\mathbb {R}$ as s subset of set of complex numbers $\mathbb {C}$.

Sergei Kurgalin, Sergei Borzunov

Chapter 8. Recurrence Relations

Abstract

Recurrence relation (from Latin recurrere—to return) is the method of specifying the function f(n), $n\in \mathbb {N}$, for which [52, 65]:

values of the function f(n) for some subset

$$\begin{aligned} N_m=\{1,2,\dots ,m\}\subset \mathbb {N} \end{aligned}$$

are specified in an explicit form:

$$\begin{aligned} f(1)=a_1, \; f(2)=a_2,\; \dots , \; f(m)=a_m; \end{aligned}$$

values of the function for the arguments $k\in \mathbb {N}\setminus N_m$ are expressed by the values f(i), where $i=1,2,\dots ,k-1$, in accordance with a specified rule.

Sergei Kurgalin, Sergei Borzunov

Chapter 9. Concept of an Algorithm. Correctness of Algorithms

Abstract

Algorithm is an exact prescription determining the computation process, leading from the varying source data to the sought result (data is the ordered set of characters). In other words, an algorithm describes the certain computation procedure, with the help of which the computation problem is solved. As a rule, an algorithm is used for solving some class of problems, rather than one certain problem. Concept of an algorithm belongs to the basic, fundamental notions of mathematics. Many researchers use different wordings for the definition of an algorithm. However, all wordings explicitly or implicitly mean the following algorithm properties.

Sergei Kurgalin, Sergei Borzunov

Chapter 10. Turing Machine

Abstract

In order to formalize the concept of an algorithm, Turing suggested a mathematical model of a computing machine [71]. Turing Machine is an abstract computing device consisting of a tape, a reading and printing head and a control device. The Turing machine is not the only way to formalize the concept of an algorithm. Similar approaches are known, leading to equivalent results, among which we should mention the Post machine and the Markov normal algorithm.

Sergei Kurgalin, Sergei Borzunov

Chapter 11. Asymptotic Analysis

Abstract

An important task of algorithm analysis is the estimation of the number of operations executed by the algorithm over a certain class of input data. The exact value of the number of elementary operations does not play any considerable role here, since it depends on the software implementation of the algorithm, the computer’s architecture, and other factors. This is why the algorithm’s performance indicator is the growth rate of this value with the growth of the input data volume. For analysis of the algorithm’s efficiency, it is necessary to estimate the operation time of the computer that solves the set problem, as well as the volume of memory used. The estimate of the computation system operation time is usually obtained by calculating the elementary operations performed during calculations (such operations are referred to as basic). In a supposition that one elementary operation is executed within a strictly defined period of time, the function f(n), defined as the number of operations when calculating over the input data of size n, is called a time-complexity function. Universal method of estimating the growth rate of functions, based on the Master Theorem, is given.

Sergei Kurgalin, Sergei Borzunov

Chapter 12. Basic Algorithms

Abstract

Recursive is an algorithm that calls itself [66]. Such algorithms are usually easy to understand and convenient for implementation. The following algorithms are considered in detail:

search algorithms (sequential, binary, Fibonaccian, interpolation search);

sorting algorithms (insertion, bubble, shaker, selection, Shellsort, quicksort);

algorithms for determining order statistics.

Sergei Kurgalin, Sergei Borzunov

Chapter 13. Parallel Algorithms

Abstract

A chapter is dedicated to parallel algorithms. Multiprocessor computing systems are extensively used at present for solving tasks on mathematical and computer modeling, management of database and complex software packages, etc. Furthermore, the majority of modern computing systems back up parallel computations on a hardware level. From this perspective, questions connected with the construction and analysis of parallel algorithms are becoming increasingly relevant. It should be pointed out that in many cases, developing an effective parallel algorithm of solution of some task requires attraction of new ideas and methods compared to creating sequential algorithms. These are, for instance, practically important problems of searching a target element in data structures, evaluation of an algebraic expression, etc. The theoretical part of this chapter takes a relatively bigger place in comparison with other chapters, as it deals with more complex issues of applied aspects of parallel programming, rather difficult when first studied. This chapter requires a good command of methods of problem solution described in the previous chapters.

Sergei Kurgalin, Sergei Borzunov

Backmatter

Titel: The Discrete Math Workbook
verfasst von: Prof. Dr. Sergei Kurgalin
Dr. Sergei Borzunov
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-42221-9
Print ISBN: 978-3-030-42220-2
DOI: https://doi.org/10.1007/978-3-030-42221-9